worst-case complexity

A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimization

  • Michael J. O'Neill
  • Clément W. Royer
  • Stephen Wright
    • Categories Unconstrained Optimization Tags , , ,

    We consider minimization of a smooth nonconvex objective function using an iterative algorithm based on Newton’s method and linear conjugate gradient, with explicit detection and use of negative curvature directions for the Hessian of the objective function. The algorithm tracks Newton-conjugate gradient procedures developed in the 1980s closely, but includes enhancements that allow worst-case complexity … Read more

    A derivative-free Gauss-Newton method

  • Coralia Cartis
  • Lindon Roberts
    • Categories Nonlinear Optimization Tags , , , , ,

    We present DFO-GN, a derivative-free version of the Gauss-Newton method for solving nonlinear least-squares problems. As is common in derivative-free optimization, DFO-GN uses interpolation of function values to build a model of the objective, which is then used within a trust-region framework to give a globally-convergent algorithm requiring $O(\epsilon^{-2})$ iterations to reach approximate first-order criticality … Read more

    A Line-Search Algorithm Inspired by the Adaptive Cubic Regularization Framework and Complexity Analysis

  • Elhoucine Bergou
  • Youssef Diouane
  • Serge Gratton
    • Categories Unconstrained Optimization Tags , , , , ,

    Adaptive regularized framework using cubics has emerged as an alternative to line-search and trust-region algorithms for smooth nonconvex optimization, with an optimal complexity amongst second-order methods. In this paper, we propose and analyze the use of an iteration dependent scaled norm in the adaptive regularized framework using cubics. Within such scaled norm, the obtained method … Read more

    A decoupled first/second-order steps technique for nonconvex nonlinear unconstrained optimization with improved complexity bounds

  • Serge Gratton
  • Clément W. Royer
  • Luis Nunes Vicente
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , , ,

    In order to be provably convergent towards a second-order stationary point, optimization methods applied to nonconvex problems must necessarily exploit both first and second-order information. However, as revealed by recent complexity analyzes of some of these methods, the overall effort to reach second-order points is significantly larger when compared to the one of approaching first-order … Read more

    Complexity and global rates of trust-region methods based on probabilistic models

  • Serge Gratton
  • Clément W. Royer
  • Luis Nunes Vicente
  • Z. Zhang
    • Categories Stochastic Programming, Unconstrained Optimization Tags , , ,

    Trust-region algorithms have been proved to globally converge with probability one when the accuracy of the trust-region models is imposed with a certain probability conditioning on the iteration history. In this paper, we study their complexity, providing global rates and worst case complexity bounds on the number of iterations (with overwhelmingly high probability), for both … Read more

    A second-order globally convergent direct-search method and its worst-case complexity

  • Serge Gratton
  • Clément W. Royer
  • Luis Nunes Vicente
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    Direct-search algorithms form one of the main classes of algorithms for smooth unconstrained derivative-free optimization, due to their simplicity and their well-established convergence results. They proceed by iteratively looking for improvement along some vectors or directions. In the presence of smoothness, first-order global convergence comes from the ability of the vectors to approximate the steepest … Read more

    Trust-region methods without using derivatives: Worst case complexity and the non-smooth case

  • R. Garmanjani
  • Luis Nunes Vicente
  • Diogo Júdice
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , , ,

    Trust-region methods are a broad class of methods for continuous optimization that found application in a variety of problems and contexts. In particular, they have been studied and applied for problems without using derivatives. The analysis of trust-region derivative-free methods has focused on global convergence, and they have been proved to generate a sequence of … Read more

    On the optimal order of worst case complexity of direct search

  • M. Dodangeh
  • Luis Nunes Vicente
  • Z. Zhang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , ,

    The worst case complexity of direct-search methods has been recently analyzed when they use positive spanning sets and impose a sufficient decrease condition to accept new iterates. Assuming that the objective function is smooth, it is now known that such methods require at most O(n^2 epsilon^{-2}) function evaluations to compute a gradient of norm below … Read more

    On the use of iterative methods in cubic regularization for unconstrained optimization

  • Tommaso Bianconcini
  • Giampaolo Liuzzi
  • Benedetta Morini
  • Marco Sciandrone
    • Categories Nonlinear Optimization Tags , , ,

    In this paper we consider the problem of minimizing a smooth function by using the Adaptive Cubic Regularized framework (ARC). We focus on the computation of the trial step as a suitable approximate minimizer of the cubic model and discuss the use of matrix-free iterative methods. Our approach is alternative to the implementation proposed in … Read more

    Worst case complexity of direct search under convexity

  • M. Dodangeh
  • Luis Nunes Vicente
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    In this paper we prove that the broad class of direct-search methods of directional type, based on imposing sufficient decrease to accept new iterates, exhibits the same global rate or worst case complexity bound of the gradient method for the unconstrained minimization of a convex and smooth function. More precisely, it will be shown that … Read more