On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization

Abstract

In this paper we study the worst-case complexity of an inexact Augmented Lagrangian method for nonconvex constrained problems. Assuming that the penalty parameters are bounded, we prove a complexity bound of $\mathcal{O}(|\log (\epsilon )|)$ outer iterations for the referred algorithm to generate an $\epsilon$-approximate KKT point, for $\epsilon \in (0,1)$. When the penalty parameters are unbounded, we prove an outer iteration complexity bound of $\mathcal{O}\left({\epsilon }^{-2/(\alpha -1)}\right)$, where $\alpha >1$ controls the rate of increase of the penalty parameters. For linearly constrained problems, these bounds yield to evaluation complexity bounds of $\mathcal{O}(|\log (\epsilon ){|}^2{\epsilon }^{-2})$ and $\mathcal{O}\left({\epsilon }^{-\left(\frac{2(2+\alpha )}{\alpha -1}+2\right)}\right)$, respectively, when appropriate first-order methods ($p=1$) are used to approximately solve the unconstrained subproblems at each iteration. In the case of problems having only linear equality constraints, the latter bounds are improved to $\mathcal{O}(|\log (\epsilon ){|}^2{\epsilon }^{-(p+1)/p})$ and $\mathcal{O}\left({\epsilon }^{-\left(\frac{4}{\alpha -1}+\frac{p+1}{p}\right)}\right)$, respectively, when appropriate $p$-order methods ($p\ge 2$) are used as inner solvers.

References in corpus (2)

• Complexity and performance of an Augmented Lagrangian algorithm
• Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints

Cited by in corpus (11)

• Complexity and performance of an Augmented Lagrangian algorithm
• Constrained composite optimization and augmented Lagrangian methods
• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• WeMix: How to Better Utilize Data Augmentation
• MR.CAP: Multi-Robot Joint Control and Planning for Object Transport
• Neural Network Training as an Optimal Control Problem: An Augmented Lagrangian Approach
• Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints
• Lasry-Lions Envelopes and Nonconvex Optimization: A Homotopy Approach
• Implicit augmented Lagrangian and generalized optimization
• Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems
• A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees