Philippe L. Toint

Convergence properties of an Objective-Function-Free Optimization regularization algorithm, including an $\mathcal{O}(\epsilon^{-3/2})$ complexity bound

  • Serge Gratton
  • Sadok Jerad
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , ,

    An adaptive regularization algorithm for unconstrained nonconvex optimization is presented in which the objective function is never evaluated, but only derivatives are used. This algorithm belongs to the class of adaptive regularization methods, for which optimal worst-case complexity results are known for the standard framework where the objective function is evaluated. It is shown in … Read more

    OFFO minimization algorithms for second-order optimality and their complexity

  • Serge Gratton
  • Philippe L. Toint
    • Categories Unconstrained Optimization Tags , , , ,

    An Adagrad-inspired class of algorithms for smooth unconstrained optimization is presented in which the objective function is never evaluated and yet the gradient norms decrease at least as fast as O(1/\sqrt{k+1}) while second-order optimality measures converge to zero at least as fast as O(1/(k+1)^{1/3}). This latter rate of convergence is shown to be essentially sharp … Read more

    Parametric complexity analysis for a class of first-order Adagrad-like algorithms

  • Serge Gratton
  • Sadok Jerad
  • Philippe L. Toint
    • Categories Stochastic Programming, Unconstrained Optimization Tags , , , , ,

    A class of algorithms for optimization in the presence of noise is presented, that does not require the evaluation of the objective function. This class generalizes the well-known Adagrad method. The complexity of this class is then analyzed as a function of its parameters, and it is shown that some methods of the class enjoy … Read more

    First-Order Objective-Function-Free Optimization Algorithms and Their Complexity

  • Serge Gratton
  • Sadok Jerad
  • Philippe L. Toint
    • Categories Unconstrained Optimization Tags , , , , ,

    A class of algorithms for unconstrained nonconvex optimization is considered where the value of the objective function is never computed. The class contains a deterministic version of the first-order Adagrad method typically used for minimization of noisy function, but also allows the use of second-order information when available. The rate of convergence of methods in … Read more

    An adaptive regularization algorithm for unconstrained optimization with inexact function and derivatives values

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

    An adaptive regularization algorithm for unconstrained nonconvex optimization is proposed that is capable of handling inexact objective-function and derivative values, and also of providing approximate minimizer of arbitrary order. In comparison with a similar algorithm proposed in Cartis, Gould, Toint (2022), its distinguishing feature is that it is based on controlling the relative error between … Read more

    Trust-region algorithms: probabilistic complexity and intrinsic noise with applications to subsampling techniques

  • Stefania Bellavia
  • Gianmarco Gurioli
  • Benedetta Morini
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , , , ,

    A trust-region algorithm is presented for finding approximate minimizers of smooth unconstrained functions whose values and derivatives are subject to random noise. It is shown that, under suitable probabilistic assumptions, the new method finds (in expectation) an epsilon-approximate minimizer of arbitrary order q > 0 in at most O(epsilon^{-(q+1)}) inexact evaluations of the function and … Read more

    OPM, a collection of Optimization Problems in Matlab

  • Serge Gratton
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Optimization Software Benchmark, Unconstrained Optimization Tags , , ,

    OPM is a small collection of CUTEst unconstrained and bound-constrained nonlinear optimization problems, which can be used in Matlab for testing optimization algorithms directly (i.e. without installing additional software). Article Download View OPM, a collection of Optimization Problems in Matlab

    Adaptive Regularization Minimization Algorithms with Non-Smooth Norms

  • Serge Gratton
  • Philippe L. Toint
    • Categories Unconstrained Optimization Tags , , , ,

    A regularization algorithm (AR1pGN) for unconstrained nonlinear minimization is considered, which uses a model consisting of a Taylor expansion of arbitrary degree and regularization term involving a possibly non smooth norm. It is shown that the non-smoothness of the norm does not affect the O(\epsilon_1^{-(p+1)/p}) upper bound on evaluation complexity for finding first-order \epsilon_1-approximate minimizers … Read more

    Hölder Gradient Descent and Adaptive Regularization Methods in Banach Spaces for First-Order Points

  • Serge Gratton
  • Philippe L. Toint
  • Sadok Jerad
    • Categories Unconstrained Optimization Tags , ,

    This paper considers optimization of smooth nonconvex functionals in smooth infinite dimensional spaces. A Hölder gradient descent algorithm is first proposed for finding approximate first-order points of regularized polynomial functionals. This method is then applied to analyze the evaluation complexity of an adaptive regularization method which searches for approximate first-order points of functionals with $\beta$-H\”older … Read more

    The Impact of Noise on Evaluation Complexity: The Deterministic Trust-Region Case

  • Stefania Bellavia
  • Benedetta Morini
  • Philippe L. Toint
  • Gianmarco Gurioli
    • Categories Unconstrained Optimization Tags , , ,

    Intrinsic noise in objective function and derivatives evaluations may cause premature termination of optimization algorithms. Evaluation complexity bounds taking this situation into account are presented in the framework of a deterministic trust-region method. The results show that the presence of intrinsic noise may dominate these bounds, in contrast with what is known for methods in … Read more