Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization

Abstract

First-order methods have been studied for nonlinear constrained optimization within the framework of the augmented Lagrangian method (ALM) or penalty method. We propose an improved inexact ALM (iALM) and conduct a unified analysis for nonconvex problems with either affine equality or nonconvex constraints. Under certain regularity conditions (that are also assumed by existing works), we show an $\tilde{O}({\epsilon }^{-\frac{5}{2}})$ complexity result for a problem with a nonconvex objective and affine equality constraints and an $\tilde{O}({\epsilon }^{-3})$ complexity result for a problem with a nonconvex objective and nonconvex constraints, where the complexity is measured by the number of first-order oracles to yield an $\epsilon$-KKT solution. Both results are the best known. The same-order complexity results have been achieved by penalty methods. However, two different analysis techniques are used to obtain the results, and more importantly, the penalty methods generally perform significantly worse than iALM in practice. Our improved iALM and analysis close the gap between theory and practice. Numerical experiments on nonconvex problems with affine equality or nonconvex constraints are provided to demonstrate the effectiveness of our proposed method.

arXiv commentAISTATS 2021

References in corpus (8)

• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Near-Optimal Algorithms for Minimax Optimization
• An Augmented Lagrangian Method for Conic Convex Programming
• First-order methods for constrained convex programming based on linearized augmented Lagrangian function
• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• Iteration complexity of first-order augmented Lagrangian methods for convex conic programming
• Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems
• A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization

Cited by in corpus (4)

• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems
• Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold
• An Accelerated Inexact Dampened Augmented Lagrangian Method for Linearly-Constrained Nonconvex Composite Optimization Problems