On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization

DOI10.1093/IMANUM/DRAA021MaRDI QIDQ6320451arXivFDO

Authors Geovani Nunes Grapiglia, Yaxiang Yuan

Publication date 13 June 2019

Published in arXiv

Full work available at URL https://doi.org/10.1093/IMANUM/DRAA021

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26)

arXiv classification

math.OC

Abstract: In this paper we study the worst-case complexity of an inexact Augmented Lagrangian method for nonconvex constrained problems. Assuming that the penalty parameters are bounded, we prove a complexity bound of $mathcalO(|log(epsilon)|)$ outer iterations for the referred algorithm to generate an $epsilon$-approximate KKT point, for $epsilonin(0,1)$. When the penalty parameters are unbounded, we prove an outer iteration complexity bound of $mathcalOleft(epsilo{n}^{-2/(alpha-1)}ight)$, where $alpha>1$ controls the rate of increase of the penalty parameters. For linearly constrained problems, these bounds yield to evaluation complexity bounds of $mathcalO(|log(epsilon){|}^{2}epsilo{n}^{-2})$ and $mathcalOleft(epsilo{n}^{-left(frac2(2+alpha)alpha-1+2ight)}ight)$, respectively, when appropriate first-order methods ($p=1$) are used to approximately solve the unconstrained subproblems at each iteration. In the case of problems having only linear equality constraints, the latter bounds are improved to $mathcalO(|log(epsilon){|}^{2}epsilo{n}^{-(p+1)/p})$ and $mathcalOleft(epsilo{n}^{-left(frac4alpha-1+fracp+1pight)}ight)$, respectively, when appropriate $p$-order methods ($pgeq2$) are used as inner solvers.

This page was built for publication: On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320451)