loading page

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

Corresponding Author:[email protected]

Author Profile
Xiangmei Wang
Guizhou University
Author Profile

Abstract

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.

28 Jul 2020Submitted to Mathematical Methods in the Applied Sciences
30 Jul 2020Submission Checks Completed
30 Jul 2020Assigned to Editor
03 Aug 2020Reviewer(s) Assigned
04 Jul 2022Review(s) Completed, Editorial Evaluation Pending
04 Jul 2022Editorial Decision: Revise Major
27 Sep 20221st Revision Received
28 Sep 2022Submission Checks Completed
28 Sep 2022Assigned to Editor
28 Sep 2022Reviewer(s) Assigned
11 Nov 2022Review(s) Completed, Editorial Evaluation Pending
20 Nov 2022Editorial Decision: Revise Minor
22 Nov 20222nd Revision Received
22 Nov 2022Submission Checks Completed
22 Nov 2022Assigned to Editor
22 Nov 2022Review(s) Completed, Editorial Evaluation Pending
28 Nov 2022Editorial Decision: Accept