Philippe L. Toint

Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

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

    Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of $O(\epsilon^{-3/2})$ proved by Cartis, Gould and Toint (IMAJNA 32(4) 2012, pp.1662-1695) for computing an $\epsilon$-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are … Read more

    Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models

  • Ernesto G. Birgin
  • José Mario Martínez
  • Sandra Augusta Santos
  • Philippe L. Toint
  • John L. Gardenghi
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization Tags , , ,

    The evaluation complexity of general nonlinear, possibly nonconvex,constrained optimization is analyzed. It is shown that, under suitable smoothness conditions, an $\epsilon$-approximate first-order critical point of the problem can be computed in order $O(\epsilon^{1-2(p+1)/p})$ evaluations of the problem’s function and their first $p$ derivatives. This is achieved by using a two-phases algorithm inspired by Cartis, Gould, … Read more

    BFO, a trainable derivative-free Brute Force Optimizer for nonlinear bound-constrained optimization and equilibrium computations with continuous and discrete variables

  • Margherita Porcelli
  • Philippe L. Toint
    • Categories (Mixed) Integer Nonlinear Programming, Bound-constrained Optimization, Nonlinear Optimization Tags , , , ,

    A direct-search derivative-free Matlab optimizer for bound-constrained problems is described, whose remarkable features are its ability to handle a mix of continuous and discrete variables, a versatile interface as well as a novel self-training option. Its performance compares favourably with that of NOMAD, a state-of-the art package. It is also applicable to multilevel equilibrium- or … Read more

    Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

  • Ernesto G. Birgin
  • José Mario Martínez
  • Sandra Augusta Santos
  • Philippe L. Toint
  • John L. Gardenghi
    • Categories Unconstrained Optimization Tags , ,

    The worst-case evaluation complexity for smooth (possibly nonconvex) unconstrained optimization is considered. It is shown that, if one is willing to use derivatives of the objective function up to order $p$ (for $p\geq 1$) and to assume Lipschitz continuity of the $p$-th derivative, then an $\epsilon$-approximate first-order critical point can be computed in at most … Read more

    A trust-funnel method for nonlinear optimization problems with general nonlinear constraints and its application to derivative-free optimization

  • Phillipe Sampaio
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization Tags , , ,

    A trust-funnel method is proposed for solving nonlinear optimization problems with general nonlinear constraints. It extends the one presented by Gould and Toint (Math. Prog., 122(1):155-196, 2010), originally proposed for equality-constrained optimization problems only, to problems with both equality and inequality constraints and where simple bounds are also considered. As the original one, our method … Read more

    Corrigendum: On the complexity of finding first-order critical points in constrained nonlinear optimization

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

    In a recent paper (Cartis, Gould and Toint, Math. Prog. A 144(1-2) 93–106, 2014), the evaluation complexity of an algorithm to find an approximate first-order critical point for the general smooth constrained optimization problem was examined. Unfortunately, the proof of Lemma 3.5 in that paper uses a result from an earlier paper in an incorrect … Read more

    Worst-case evaluation complexity of regularization methods for smooth unconstrained optimization using Hölder continuous gradients

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

    The worst-case behaviour of a general class of regularization algorithms is considered in the case where only objective function values and associated gradient vectors are evaluated. Upper bounds are derived on the number of such evaluations that are needed for the algorithm to produce an approximate first-order critical point whose accuracy is within a user-defined … Read more

    Simple examples for the failure of Newton’s method with line search for strictly convex minimization

  • Florian Jarre
  • Philippe L. Toint
    • Categories Unconstrained Optimization Tags ,

    In this paper two simple examples of a twice continuously differentiable strictly convex function $f$ are presented for which Newton’s method with line search converges to a point where the gradient of $f$ is not zero. The first example uses a line search based on the Wolfe conditions. For the second example, some strictly convex … Read more

    A derivative-free trust-funnel method for equality-constrained nonlinear optimization

  • Phillipe Sampaio
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    In this work, we look into new derivative-free methods to solve equality-constrained optimization problems. Of particular interest, are the trust-region techniques, which have been investigated for the unconstrained and bound-constrained cases. For solving equality-constrained optimization problems, we introduce a derivative-free adaptation of the trust-funnel method combined with a self-correcting geometry scheme and present some encouraging … Read more

    An Interior-Point Trust-Funnel Algorithm for Nonlinear Optimization

  • Frank E. Curtis
  • Nicholas I. M. Gould
  • Daniel P. Robinson
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , ,

    We present an interior-point trust-funnel algorithm for solving large-scale nonlinear optimization problems. The method is based on an approach proposed by Gould and Toint (Math Prog 122(1):155–196, 2010) that focused on solving equality constrained problems. Our method is similar in that it achieves global convergence guarantees by combining a trust-region methodology with a funnel mechanism, … Read more