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 O(1/ ε2 - η) outer iterations (where η is a user-defined parameter with η∈[0,2] for the first-order result and η ∈ [1,2] for the second-order result) when the proximal term coefficient β and penalty parameter ρ satisfy β = O(εη) and ρ = Omega (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.