{
  "id": "1906.05622",
  "version": "v1",
  "published": "2019-06-13T12:07:25.000Z",
  "updated": "2019-06-13T12:07:25.000Z",
  "title": "On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization",
  "authors": [
    "Geovani N. Grapiglia",
    "Ya-xiang Yuan"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "In this paper we study the worst-case complexity of an inexact Augmented Lagrangian method for nonconvex inequality-constrained problems. Assuming that the penalty parameters are bounded, we prove a complexity bound of $\\mathcal{O}(|\\log(\\epsilon)|)$ iterations for the referred algorithm generate an $\\epsilon$-approximate KKT point, for $\\epsilon\\in (0,1)$. When the penalty parameters are unbounded, we prove an iteration complexity bound of $\\mathcal{O}\\left(\\epsilon^{-2/(\\alpha-1)}\\right)$, where $\\alpha>1$ controls the rate of increase of the penalty parameters. For linearly constrained problems, these bounds yield to evaluation complexity bounds of $\\mathcal{O}(|\\log(\\epsilon)|^{2}\\epsilon^{-(p+1)/p})$ and $\\mathcal{O}\\left(\\epsilon^{-\\left(\\frac{4}{\\alpha-1}+\\frac{p+1}{p}\\right)}\\right)$, respectively, when suitable $p$-order methods ($p\\geq 2$) are used to approximately solve the unconstrained subproblems at each iteration of our Augmented Lagrangian scheme.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-06-13T12:07:25.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "nonconvex optimization",
      "penalty parameters",
      "approximate kkt point",
      "iteration complexity bound",
      "evaluation complexity bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}