cubic regularization

Evaluation complexity of adaptive cubic regularization methods for convex unconstrained optimization

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

    The adaptive cubic regularization algorithms described in Cartis, Gould & Toint (2009, 2010) for unconstrained (nonconvex) optimization are shown to have improved worst-case efficiency in terms of the function- and gradient-evaluation count when applied to convex and strongly convex objectives. In particular, our complexity upper bounds match in order (as a function of the accuracy … 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