Philippe L. Toint

On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , , , ,

    The (optimal) function/gradient evaluations worst-case complexity analysis available for the Adaptive Regularizations algorithms with Cubics (ARC) for nonconvex smooth unconstrained optimization is extended to finite-difference versions of this algorithm, yielding complexity bounds for first-order and derivative free methods applied on the same problem class. A comparison with the results obtained for derivative-free methods by Vicente … Read more

    Using approximate secant equations in limited memory methods for multilevel unconstrained optimization

  • Serge Gratton
  • Vincent Malmedy
  • Philippe L. Toint
    • Categories Optimization of Systems modeled by PDEs, Unconstrained Optimization Tags , , , ,

    The properties of multilevel optimization problems defined on a hierarchy of discretization grids can be used to define approximate secant equations, which describe the second-order behaviour of the objective function. Following earlier work by Gratton and Toint (2009), we introduce a quasi-Newton method (with a linesearch) and a nonlinear conjugate gradient method that both take … Read more

    On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization

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

    It is shown that the steepest descent and Newton’s method for unconstrained nonconvex optimization under standard assumptions may be both require a number of iterations and function evaluations arbitrarily close to O(epsilon^{-2}) to drive the norm of the gradient below epsilon. This shows that the upper bound of O(epsilon^{-2}) evaluations known for the steepest descent … Read more

    Stopping rules and backward error analysis for bound-constrained optimization

  • Serge Gratton
  • Philippe L. Toint
  • Mélodie Mouffe
    • Categories Bound-constrained Optimization, Optimization Software Design Principles Tags , , , ,

    Termination criteria for the iterative solution of bound-constrained optimization problems are examined in the light of backward error analysis. It is shown that the problem of determining a suitable perturbation on the problem’s data corresponding to the definition of the backward error is analytically solvable under mild assumptions. Moreover, a link between existing termination criteria … Read more

    An adaptive cubic regularisation algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity

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

    The adaptive cubic overestimation algorithm described in Cartis, Gould and Toint (2007) is adapted to the problem of minimizing a nonlinear, possibly nonconvex, smooth objective function over a convex domain. Convergence to first-order critical points is shown under standard assumptions, but without any Lipschitz continuity requirement on the objective’s Hessian. A worst-case complexity analysis in … Read more

    Self-correcting geometry in model-based algorithms for derivative-free unconstrained optimization

  • Katya Scheinberg
  • Philippe L. Toint
    • Categories Optimization of Simulated Systems, Unconstrained Optimization Tags , ,

    Several efficient methods for derivative-free optimization (DFO) are based on the construction and maintenance of an interpolation model for the objective function. Most of these algorithms use special “geometry-improving” iterations, where the geometry (poisedness) of the underlying interpolation set is made better at the cost of one or more function evaluations. We show that such … Read more

    Approximating Hessians in multilevel unconstrained optimization

  • Vincent Malmedy
  • Philippe L. Toint
    • Categories Optimization of Systems modeled by PDEs, Unconstrained Optimization Tags , , , ,

    We consider Hessian approximation schemes for large-scale multilevel unconstrained optimization problems, which typically present a sparsity and partial separability structure. This allows iterative quasi-Newton methods to solve them despite of their size. Structured finite-difference methods and updating schemes based on the secant equation are presented and compared numerically inside the multilevel trust-region algorithm proposed by … Read more

    Nonlinear Stepsize Control, Trust Regions and Regularizations for Unconstrained Optimization

  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , ,

    A general class of algorithms for unconstrained optimization is introduced, which subsumes the classical trust-region algorithm and two of its newer variants, as well as the cubic and quadratic regularization methods. A unified theory of global convergence to first-order critical points is then described for this class. An extension to projection-based trust-region algorithms for nonlinear … Read more

    Numerical Experience with a Recursive Trust-Region Method for Multilevel Nonlinear Optimization

  • Serge Gratton
  • Annick Sartenaer
  • Philippe L. Toint
  • Mélodie Mouffe
  • Dimitri Tomanos
    • Categories Bound-constrained Optimization, Distributed Control, Optimization of Systems modeled by PDEs Tags , , , , ,

    We consider an implementation of the recursive multilevel trust-region algorithm proposed by Gratton, Mouffe, Toint, Weber (2008) for bound-constrained nonlinear problems, and provide numerical experience on multilevel test problems. A suitable choice of the algorithm’s parameters is identified on these problems, yielding a satisfactory compromise between reliability and efficiency. The resulting default algorithm is then … Read more