Incremental subgradient algorithms with dynamic step sizes for separable convex optimizations

Autor: Xiangmei Wang, Dan Yang
Rok vydání: 2022
Předmět:
Zdroj: Mathematical Methods in the Applied Sciences. 46:7108-7124
ISSN: 1099-1476
0170-4214
Popis: We consider the incremental subgradient algorithm employing dynamic step sizes for minimizing the sum of a large number of component convex functions. The dynamic step size rule was firstly introduced by Goffin and Kiwiel [Math. Program., 1999, 85(1): 207-211] for the subgradient algorithm, soon later, for the incremental subgradient algorithm by Nedic and Bertsekas in [SIAM J. Optim., 2001, 12(1): 109-138]. It was observed experimentally that the incremental approach has been very successful in solving large separable optimizations, and that the dynamic step sizes generally have better computational performance than others in the literature. In the present paper, we propose two modified dynamic step size rules for the incremental subgradient algorithm and analyse the convergence properties of them. At last, the assignment problem is considered and the incremental subgradient algorithms employing different kinds of dynamic step sizes are applied to solve the problem. The computational experiments show that the two modified ones converges dramatically faster and stabler than the corresponding one in [SIAM J. Optim., 2001, 12(1): 109-138]. Particularly, for solving large separable convex optimizations, we strongly recommend the second one (see Algorithm 3.3 in the paper) since it has interesting computational performance and is the simplest one.
Databáze: OpenAIRE
Externí odkaz: