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

Coralia Cartis, Nicholas I M Gould, Philippe Toint

Research output: Contribution to journalArticle

1 Downloads (Pure)

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.
Original languageEnglish
JournalOptimization Methods and Software
Volumeto appear
Publication statusAccepted/In press - 1 Oct 2019

Fingerprint

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

Keywords

  • Evaluation complexity
  • Nonlinear optimization
  • second-order methods

Cite this

@article{135cea3d0f2949eb91d222870002daca,
title = "A concise 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 = "2019",
month = "10",
day = "1",
language = "English",
volume = "to appear",
journal = "Optimization Methods and Software",
issn = "1055-6788",
publisher = "Taylor & Francis",

}

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

In: Optimization Methods and Software, Vol. to appear, 01.10.2019.

Research output: Contribution to journalArticle

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 -