loading page

Incremental Subgradient Algorithms with Dynamic Step Sizes for Separable Convex Optimizations
  • Dan Yang,
  • Xiangmei Wang
Dan Yang
Guizhou University
Author Profile
Xiangmei Wang
Guizhou University
Author Profile

Peer review status:UNDER REVIEW

28 Jul 2020Submitted to Mathematical Methods in the Applied Sciences
30 Jul 2020Assigned to Editor
30 Jul 2020Submission Checks Completed
03 Aug 2020Reviewer(s) Assigned


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.