Skip to yearly menu bar Skip to main content


Poster

An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints

Mehmet Fatih Sahin · Armin eftekhari · Ahmet Alacaoglu · Fabian Latorre · Volkan Cevher

East Exhibition Hall B, C #208

Keywords: [ Non-Convex Optimization ] [ Optimization ]


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^3)$ 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. These complexity results match the known theoretical results 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.

Live content is unavailable. Log in and register to view live content