global complexity bounds

Optimal Newton-type methods for nonconvex smooth optimization problems

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Nonlinear Optimization Tags , ,

    We consider a general class of second-order iterations for unconstrained optimization that includes regularization and trust-region variants of Newton’s method. For each method in this class, we exhibit a smooth, bounded-below objective function, whose gradient is globally Lipschitz continuous within an open convex set containing any iterates encountered and whose Hessian is $\alpha-$Holder continuous (for … Read more

    Cubic regularization of Newton’s method for convex problems with constraints

  • Yurii Nesterov
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In this paper we derive the efficiency estimates of the regularized Newton’s method as applied to constrained convex minimization problems and to variational inequalities. We study a one-step Newton’s method and its multistep accelerated version, which converges on smooth convex problems as $O({1 \over k^3})$, where $k$ is the iteration counter. We derive also the … Read more