{
  "id": "2103.15989",
  "version": "v1",
  "published": "2021-03-29T23:43:44.000Z",
  "updated": "2021-03-29T23:43:44.000Z",
  "title": "Complexity of Projected Newton Methods for Bound-constrained Optimization",
  "authors": [
    "Yue Xie",
    "Stephen J. Wright"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "We analyze the iteration complexity of two methods based on the projected gradient and Newton methods for solving bound-constrained optimization problems. The first method is a scaled variant of Bertsekas's two-metric projection method, which can be shown to output an $\\epsilon$-approximate first-order point in $\\mathcal{O}(\\epsilon^{-2})$ iterations. The second is a projected Newton-Conjugate Gradient (CG) method, which locates an $\\epsilon$-approximate second-order point with high probability in $\\mathcal{O}(\\epsilon^{-3/2})$ iterations, at a cost of $\\mathcal{O}(\\epsilon^{-7/4})$ gradient evaluations or Hessian-vector products (omitting logarithmic factors). Besides having good complexity properties, both methods are appealing from a practical point of view, as we show using some illustrative numerical results.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-03-29T23:43:44.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "49M15",
      "68Q25",
      "90C06",
      "90C30",
      "90C60"
    ],
    "keywords": [
      "projected newton methods",
      "complexity",
      "bertsekass two-metric projection method",
      "approximate first-order point",
      "approximate second-order point"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}