Optimization Online


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

Coralia Cartis(cartis***at***maths.ox.ac.uk)
Nicholas I M Gould(nimg***at***stfc.ac.uk)
Philippe L Toint(philippe.toint***at***unamur.be)

Abstract: 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 at most $O \left(\max\left( \epsilon_1^{-\frac{p+1}{p}}, \epsilon_2^{-\frac{p+1}{p-1}} \right) \right)$ function and derivatives evaluations, where $\epsilon_1$ and $\epsilon_2 >0$ are prescribed first- and second-order optimality tolerances. Our approach extends the method in Birgin et al. (2016) to finding second-order critical points, and establishes the novel complexity bound for second-order criticality under identical problem assumptions as for first-order, namely, that the $p$-th derivative tensor is Lipschitz continuous and that $f(x)$ is bounded from below. The evaluation-complexity bound for second-order criticality improves on all such known existing results.

Keywords: complexity analysis, regularisation methods

Category 1: Nonlinear Optimization

Citation: Technical Report, University of Oxford, Mathematical Institute, 2017.

Download: [PDF]

Entry Submitted: 08/13/2017
Entry Accepted: 08/13/2017
Entry Last Modified: 08/13/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society