  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.
