Optimization Online


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

Yue Xie (xie86***at***wisc.edu)
Stephen Wright (swright***at***cs.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 )


Download: [PDF]

Entry Submitted: 07/31/2019
Entry Accepted: 08/01/2019
Entry Last Modified: 10/11/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society