Philippe L. Toint

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
  • Gianmarco Gurioli
  • Benedetta Morini
  • Philippe L. Toint
    • 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

    Strong Evaluation Complexity of An Inexact Trust-Region Algorithm for Arbitrary-Order Unconstrained Nonconvex Optimization

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

    A trust-region algorithm using inexact function and derivatives values is introduced for solving unconstrained smooth optimization problems. This algorithm uses high-order Taylor models and allows the search of strong approximate minimizers of arbitrary order. The evaluation complexity of finding a $q$-th approximate minimizer using this algorithm is then shown, under standard conditions, to be $\mathcal{O}\big(\min_{j\in\{1,\ldots,q\}}\epsilon_j^{-(q+1)}\big)$ … Read more

    High-order Evaluation Complexity of a Stochastic Adaptive Regularization Algorithm for Nonconvex Optimization Using Inexact Function Evaluations and Randomly Perturbed Derivatives

  • Stefania Bellavia
  • Benedetta Morini
  • Philippe L. Toint
  • Gianmarco Gurioli
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    A stochastic adaptive regularization algorithm allowing random noise in derivatives and inexact function values is proposed for computing strong approximate minimizers of any order for inexpensively constrained smooth optimization problems. For an objective function with Lipschitz continuous p-th derivative in a convex neighbourhood of the feasible set and given an arbitrary optimality order q, it … Read more

    Strong Evaluation Complexity Bounds for Arbitrary-Order Optimization of Nonconvex Nonsmooth Composite Functions

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

    We introduce the concept of strong high-order approximate minimizers for nonconvex optimization problems. These apply in both standard smooth and composite non-smooth settings, and additionally allow convex or inexpensive constraints. An adaptive regularization algorithm is then proposed to find such approximate minimizers. Under suitable Lipschitz continuity assumptions, whenever the feasible set is convex, it is … Read more

    Exploiting problem structure in derivative free optimization

  • Margherita Porcelli
  • Philippe L. Toint
    • Categories Nonlinear Optimization, Optimization Software and Modeling Systems Tags , , ,

    A structured version of derivative-free random pattern search optimization algorithms is introduced which is able to exploit coordinate partially separable structure (typically associated with sparsity) often present in unconstrained and bound-constrained optimization problems. This technique improves performance by orders of magnitude and makes it possible to solve large problems that otherwise are totally intractable by … Read more