An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints

Abstract

We propose a practical inexact augmented Lagrangian method (iALM) for nonconvex problems with nonlinear constraints. We characterize the total computational complexity of our method subject to a verifiable geometric condition, which is closely related to the Polyak-Lojasiewicz and Mangasarian-Fromowitz conditions. In particular, when a first-order solver is used for the inner iterates, we prove that iALM finds a first-order stationary point with $\tilde{\mathcal{O}}(1/{\epsilon }^4)$ calls to the first-order oracle. If, in addition, the problem is smooth and a second-order solver is used for the inner iterates, iALM finds a second-order stationary point with $\tilde{\mathcal{O}}(1/{\epsilon }^5)$ calls to the second-order oracle, which matches the known theoretical complexity result in the literature. We also provide strong numerical evidence on large-scale machine learning problems, including the Burer-Monteiro factorization of semidefinite programs, and a novel nonconvex relaxation of the standard basis pursuit template. For these examples, we also show how to verify our geometric condition.

References in corpus (5)

• The Robust Manifold Defense: Adversarial Training using Generative Models
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• Clustering is semidefinitely not that hard: Nonnegative SDP for manifold disentangling

Cited by in corpus (5)

• Dual Descent ALM and ADMM
• 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
• A Decomposition Augmented Lagrangian Method for Low-rank Semidefinite Programming
• Nearly Minimal Over-Parametrization of Shallow Neural Networks