Philippe L. Toint

Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization

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

    We establish or refute the optimality of inexact second-order methods for unconstrained nonconvex optimization from the point of view of worst-case evaluation complexity, improving and generalizing the results of Cartis, Gould and Toint (2010,2011). To this aim, we consider a new general class of inexact second-order algorithms for unconstrained optimization that includes regularization and trust-region … Read more

    On the use of the saddle formulation in weakly-constrained 4D-VAR data assimilation

  • Serge Gratton
  • Philippe L. Toint
  • Selime Gürol
  • Ehouarn Simon
    • Categories Basic Sciences Applications, Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , , ,

    This paper discusses the practical use of the saddle variational formulation for the weakly-constrained 4D-VAR method in data assimilation. It is shown that the method, in its original form, may produce erratic results or diverge because of the inherent lack of monotonicity of the produced objective function values. Convergent, variationaly coherent variants of the algorithm … Read more

    Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

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

    The unconstrained minimization of a sufficiently smooth objective function $f(x)$ is considered, for which derivatives up to order $p$, $p\geq 2$, are assumed to be available. An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order $p$ and that is guaranteed to find a first- and second-order critical point in … Read more

    Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization

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

    Necessary conditions for high-order optimality in smooth nonlinear constrained optimization are explored and their inherent intricacy discussed. A two-phase minimization algorithm is proposed which can achieve approximate first-, second- and third-order criticality and its evaluation complexity is analyzed as a function of the choice (among existing methods) of an inner algorithm for solving subproblems in … Read more

    Partially separable convexly-constrained optimization with non-Lipschitz singularities and its complexity

  • Xiaojun Chen
  • Philippe L. Toint
  • Hong Wang
    • Categories Nonsmooth Optimization Tags , ,

    An adaptive regularization algorithm using high-order models is proposed for partially separable convexly constrained nonlinear optimization problems whose objective function contains non-Lipschitzian $\ell_q$-norm regularization terms for $q\in (0,1)$. It is shown that the algorithm using an $p$-th order Taylor model for $p$ odd needs in general at most $O(\epsilon^{-(p+1)/p})$ evaluations of the objective function and … Read more

    Universal regularization methods – varying the power, the smoothness and the accuracy

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

    Adaptive cubic regularization methods have emerged as a credible alternative to linesearch and trust-region for smooth nonconvex optimization, with optimal complexity amongst second-order methods. Here we consider a general/new class of adaptive regularization methods, that use first- or higher-order local Taylor models of the objective regularized by a(ny) power of the step size and applied … Read more

    Approximate norm descent methods for constrained nonlinear systems

  • Benedetta Morini
  • Margherita Porcelli
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Nonlinear Systems and Least-Squares Tags , , ,

    We address the solution of convex-constrained nonlinear systems of equations where the Jacobian matrix is unavailable or its computation/storage is burdensome. In order to efficiently solve such problems, we propose a new class of algorithms which are “derivative-free” both in the computation of the search direction and in the selection of the steplength. Search directions … Read more

    Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization

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

    High-order optimality conditions for convexly-constrained nonlinear optimization problems are analyzed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order $\epsilon$-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that, if derivatives of the objective function up to order $q \geq 1$ … Read more

    Improved worst-case evaluation complexity for potentially rank-deficient nonlinear least-Euclidean-norm problems using higher-order regularized models

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

    We present an improved evaluation complexity bound for nonlinear least squares problems using higher order regularization methods. CitationTechnical Report NA 15-17, Numerical Analysis Group, University of Oxford, 2015ArticleDownload View PDF

    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