Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems

Abstract

This paper proposes and establishes the iteration-complexity of an inexact proximal accelerated augmented Lagrangian (IPAAL) method for solving linearly constrained smooth nonconvex composite optimization problems. Each IPAAL iteration consists of inexactly solving a proximal augmented Lagrangian subproblem by an accelerated composite gradient (ACG) method followed by a suitable Lagrange multiplier update. It is shown that IPAAL generates an approximate stationary solution in at most $\mathcal{O}(\log (1/\rho )/{\rho }^3)$ ACG iterations, where $\rho >0$ is the given tolerance. It is also shown that the previous complexity bound can be sharpened to $\mathcal{O}(\log (1/\rho )/{\rho }^{2.5})$ under additional mildly stronger assumptions. The above bounds are derived assuming that the initial point is neither feasible nor the domain of the composite term of the objective function is bounded. Some preliminary numerical results are presented to illustrate the performance of the IPAAL method.

References in corpus (5)

• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$
• Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems
• Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications
• An accelerated inexact proximal point method for solving nonconvex-concave min-max problems
• Iteration complexity of first-order augmented Lagrangian methods for convex conic programming

Cited by in corpus (6)

• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization
• Dual Descent ALM and ADMM
• Algorithms for Difference-of-Convex (DC) Programs Based on Difference-of-Moreau-Envelopes Smoothing
• Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems
• An Accelerated Inexact Dampened Augmented Lagrangian Method for Linearly-Constrained Nonconvex Composite Optimization Problems