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
in Optimization -- Non-Convex Optimization »
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.
Keywords: Optimization -> Non-Convex Optimization ·

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