- Complexity of proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints Yue Xie (xie86wisc.edu) Stephen Wright (swrightcs.wisc.edu) Abstract: We analyze worst-case complexity of a proximal augmented Lagrangian (proximal AL) framework for nonconvex optimization with nonlinear equality constraints. When a first-order (second-order) optimal point is obtained in the subproblem, an $\epsilon$ first-order (second-order) optimal point for the original problem can be guaranteed within $\mathcal{O}(1/ \epsilon^{2 - \eta})$ outer iterations (where $\eta$ is a user-defined parameter with $\eta\in[0,2]$ for the first-order result and $\eta \in [1,2]$ for the second-order result) when the proximal term coefficient $\beta$ and penalty parameter $\rho$ satisfy $\beta = \mathcal{O}(\epsilon^\eta)$ and $\rho = \mathcal{O}(1/\epsilon^\eta)$, respectively. Further, when the subproblems are solved inexactly, the same order of complexity can be recovered by imposing certain verifiable conditions on the error sequence. We also investigate the total iteration complexity and operation complexity when a Newton-conjugate-gradient algorithm is used to solve the subproblems. Keywords: Nonconvex optimization with nonlinear equality constraints; Proximal augmented Lagrangian; Complexity analysis; Newton-conjugate-gradient Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization ) Citation: Download: [PDF]Entry Submitted: 07/31/2019Entry Accepted: 08/01/2019Entry Last Modified: 10/11/2019Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.