Philippe L. Toint

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

    An algorithm for optimization with disjoint linear constraints and its application for predicting rain

  • Tijana Janjic
  • Philippe L. Toint
  • Yvonne Ruckstuhl
    • Categories Basic Sciences Applications, Quadratic Programming Tags ,

    A specialized algorithm for quadratic optimization (QO, or, formerly, QP) with disjoint linear constraints is presented. In the considered class of problems, a subset of variables are subject to linear equality constraints, while variables in a different subset are constrained to remain in a convex set. The proposed algorithm exploits the structure by combining steps … Read more

    Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

  • Serge Gratton
  • Philippe L. Toint
  • Ehouarn Simon
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

    An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most O(|log(epsilon)|.epsilon^{-2}) evaluations of the problem’s functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, … Read more

    High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms

  • Xiaojun Chen
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Data-Mining, Statistics Tags , , , , ,

    This paper studies high-order evaluation complexity for partially separable convexly-constrained optimization involving non-Lipschitzian group sparsity terms in a nonconvex objective function. We propose a partially separable adaptive regularization algorithm using a $p$-th order Taylor model and show that the algorithm can produce an (epsilon,delta)-approximate q-th-order stationary point in at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of the objective … Read more

    A note on solving nonlinear optimization problems in variable precision

  • Serge Gratton
  • Philippe L. Toint
    • Categories Applications - Science and Engineering, Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags ,

    This short note considers an efficient variant of the trust-region algorithm with dynamic accuracy proposed Carter (1993) and Conn, Gould and Toint (2000) as a tool for very high-performance computing, an area where it is critical to allow multi-precision computations for keeping the energy dissipation under control. Numerical experiments are presented indicating that the use … Read more

    Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

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

    A regularization algorithm using inexact function values and inexact derivatives is proposed and its evaluation complexity analyzed. This algorithm is applicable to unconstrained problems and to problems with inexpensive constraints (that is constraints whose evaluation and enforcement has negligible cost) under the assumption that the derivative of highest degree is beta-H\”{o}lder continuous. It features a … Read more

    Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints

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

    We provide sharp worst-case evaluation complexity bounds for nonconvex minimization problems with general inexpensive constraints, i.e.\ problems where the cost of evaluating/enforcing of the (possibly nonconvex or even disconnected) constraints, if any, is negligible compared to that of evaluating the objective function. These bounds unify, extend or improve all known upper and lower complexity bounds … Read more

    Minimizing convex quadratics with variable precision Krylov methods

  • Serge Gratton
  • Philippe L. Toint
  • Ehouarn Simon
    • Categories Convex Optimization, Optimization Software and Modeling Systems, Quadratic Programming Tags , ,

    Iterative algorithms for the solution of convex quadratic optimization problems are investigated, which exploit inaccurate matrix-vector products. Theoretical bounds on the performance of a Conjugate Gradients and a Full-Orthormalization methods are derived, the necessary quantities occurring in the theoretical bounds estimated and new practical algorithms derived. Numerical experiments suggest that the new methods have significant … Read more

    A note on using performance and data profiles for training algorithms

  • Margherita Porcelli
  • Philippe L. Toint
    • Categories Nonlinear Optimization, Optimization of Simulated Systems, Optimization Software Benchmark Tags , , ,

    It is shown how to use the performance and data profile benchmarking tools to improve algorithms’ performance. An illustration for the BFO derivative-free optimizer suggests that the obtained gains are potentially significant. Citation ACM Transactions on Mathematical Software, 45:2 (2019), Article 20. Article Download View A note on using performance and data profiles for training … Read more