Poster
An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints
Mehmet Fatih Sahin · Armin eftekhari · Ahmet Alacaoglu · Fabian Latorre · Volkan Cevher

Thu Dec 12th 05:00 -- 07:00 PM @ East Exhibition Hall B + C #208
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.

Author Information

Mehmet Fatih Sahin (École Polytechnique Fédérale de Lausanne)
Armin eftekhari (EPFL)
Ahmet Alacaoglu (EPFL)
Fabian Latorre (EPFL)
Volkan Cevher (EPFL)

More from the Same Authors