Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints

We analyze worst-case complexity of a Proximal augmented Lagrangian (Proximal AL) framework for nonconvex optimization with nonlinear equality constraints. When an approximate first-order (second-order) optimal point is obtained in the subproblem, an $ε$ first-order (second-order) optimal point for the original problem can be guaranteed within $\mathcal{O}(1/ ε^{2 - η})$ outer iterations (where $η$ is a user-defined parameter with $η\in[0,2]$ for the first-order result and $η\in [1,2]$ for the second-order result) when the proximal term coefficient $β$ and penalty parameter $ρ$ satisfy $β= \mathcal{O}(ε^η)$ and $ρ= Ω(1/ε^η)$, respectively. We also investigate the total iteration complexity and operation complexity when a Newton-conjugate-gradient algorithm is used to solve the subproblems. Finally, we discuss an adaptive scheme for determining a value of the parameter $ρ$ that satisfies the requirements of the analysis.

No reviews yet.

No comments yet.