Complexity of Projected Newton Methods for Bound-constrained Optimization

Yue Xie, Stephen J. Wright

Published 2021-03-29Version 1

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.