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

Coralia Cartis, Nicholas I M Gould, Philippe Toint

Résultats de recherche: Papier de travailArticle de travail

### Résumé

The unconstrained minimization of a sufficiently smooth objective function f(x) is considered, for which derivatives up to order p, p >= 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(max(\epsilon_1^{-(p+1)/p},\epsilon_2^{-(p+1)/(p-1)})) 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.
langue Anglais Arxiv 1708.04044 Publié - août 2017

### Empreinte digitale

Function evaluation
Unconstrained Optimization
Nonlinear Optimization
Tensors
Higher Order
Derivatives
Evaluation
Criticality
Critical point
Unconstrained Minimization
Model
Evaluation Function
Lipschitz
Tolerance
Optimality
Regularization
Tensor
First-order
Derivative

### Citer ceci

@techreport{70387628b18d4359a9e8a52d1e69eeea,
title = "Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models",
abstract = "The unconstrained minimization of a sufficiently smooth objective function f(x) is considered, for which derivatives up to order p, p >= 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(max(\epsilon_1^{-(p+1)/p},\epsilon_2^{-(p+1)/(p-1)})) 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 = "Evaluation complexity, Nonlinear optimization, second-order methods",
author = "Coralia Cartis and Gould, {Nicholas I M} and Philippe Toint",
year = "2017",
month = "8",
language = "English",
volume = "1708.04044",
publisher = "Arxiv",
type = "WorkingPaper",
institution = "Arxiv",

}

Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe.

Arxiv, 2017.

Résultats de recherche: Papier de travailArticle de travail

TY - UNPB

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

AU - Cartis,Coralia

AU - Gould,Nicholas I M

AU - Toint,Philippe

PY - 2017/8

Y1 - 2017/8

N2 - The unconstrained minimization of a sufficiently smooth objective function f(x) is considered, for which derivatives up to order p, p >= 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(max(\epsilon_1^{-(p+1)/p},\epsilon_2^{-(p+1)/(p-1)})) 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.

AB - The unconstrained minimization of a sufficiently smooth objective function f(x) is considered, for which derivatives up to order p, p >= 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(max(\epsilon_1^{-(p+1)/p},\epsilon_2^{-(p+1)/(p-1)})) 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.

KW - Evaluation complexity

KW - Nonlinear optimization

KW - second-order methods

M3 - Working paper

VL - 1708.04044

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

PB - Arxiv

ER -