### Abstract

Original language | English |
---|---|

Journal | Optimization Methods and Software |

Volume | to appear |

Publication status | Accepted/In press - 1 Oct 2019 |

### Fingerprint

### Keywords

- Evaluation complexity
- Nonlinear optimization
- second-order methods

### Cite this

*Optimization Methods and Software*,

*to appear*.

}

*Optimization Methods and Software*, vol. to appear.

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

Research output: Contribution to journal › Article

TY - JOUR

T1 - A concise 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 - 2019/10/1

Y1 - 2019/10/1

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 - Article

VL - to appear

JO - Optimization Methods and Software

JF - Optimization Methods and Software

SN - 1055-6788

ER -