Complexity bounds for second-order optimality in unconstrained optimization

Coralia Cartis, N.I.M. Gould, Philippe Toint

Résultats de recherche: Contribution à un journal/une revueArticle

25 Downloads (Pure)

Résumé

This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) [15] and Cartis et al. (2010) [3] show that at most O(ε ) iterations may have to be performed for finding an iterate which is within of satisfying second-order optimality conditions. We first show that this bound can be derived for a version of the algorithm, which only uses one-dimensional global optimization of the cubic model and that it is sharp. We next consider the standard trust-region method and show that a bound of the same type may also be derived for this method, and that it is also sharp in some cases. We conclude by showing that a comparison of the bounds on the worst-case behaviour of the cubic regularization and trust-region algorithms favours the first of these methods. © 2011 Elsevier Inc. All rights reserved.
langue originaleAnglais
Pages (de - à)93-108
Nombre de pages16
journalJournal of Complexity
Volume28
Les DOIs
étatPublié - 1 févr. 2012

Empreinte digitale

Unconstrained Optimization
Optimality
Regularization
Global optimization
Trust Region Algorithm
Second-order Optimality Conditions
Trust Region Method
Minimizer
Iterate
Global Optimization
Iteration
Evaluation
Model

Citer ceci

@article{8d2e654481ca4003b6a667b21d85404a,
title = "Complexity bounds for second-order optimality in unconstrained optimization",
abstract = "This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) [15] and Cartis et al. (2010) [3] show that at most O(ε ) iterations may have to be performed for finding an iterate which is within of satisfying second-order optimality conditions. We first show that this bound can be derived for a version of the algorithm, which only uses one-dimensional global optimization of the cubic model and that it is sharp. We next consider the standard trust-region method and show that a bound of the same type may also be derived for this method, and that it is also sharp in some cases. We conclude by showing that a comparison of the bounds on the worst-case behaviour of the cubic regularization and trust-region algorithms favours the first of these methods. {\circledC} 2011 Elsevier Inc. All rights reserved.",
keywords = "evaluation complexity, second-order optimality conditions, nonconvex optimization, worst-case analysis",
author = "Coralia Cartis and N.I.M. Gould and Philippe Toint",
note = "Copyright 2011 Elsevier B.V., All rights reserved.",
year = "2012",
month = "2",
day = "1",
doi = "10.1016/j.jco.2011.06.001",
language = "English",
volume = "28",
pages = "93--108",
journal = "Journal of Complexity",
issn = "0885-064X",
publisher = "Academic Press Inc.",

}

Complexity bounds for second-order optimality in unconstrained optimization. / Cartis, Coralia; Gould, N.I.M.; Toint, Philippe.

Dans: Journal of Complexity, Vol 28, 01.02.2012, p. 93-108.

Résultats de recherche: Contribution à un journal/une revueArticle

TY - JOUR

T1 - Complexity bounds for second-order optimality in unconstrained optimization

AU - Cartis, Coralia

AU - Gould, N.I.M.

AU - Toint, Philippe

N1 - Copyright 2011 Elsevier B.V., All rights reserved.

PY - 2012/2/1

Y1 - 2012/2/1

N2 - This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) [15] and Cartis et al. (2010) [3] show that at most O(ε ) iterations may have to be performed for finding an iterate which is within of satisfying second-order optimality conditions. We first show that this bound can be derived for a version of the algorithm, which only uses one-dimensional global optimization of the cubic model and that it is sharp. We next consider the standard trust-region method and show that a bound of the same type may also be derived for this method, and that it is also sharp in some cases. We conclude by showing that a comparison of the bounds on the worst-case behaviour of the cubic regularization and trust-region algorithms favours the first of these methods. © 2011 Elsevier Inc. All rights reserved.

AB - This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) [15] and Cartis et al. (2010) [3] show that at most O(ε ) iterations may have to be performed for finding an iterate which is within of satisfying second-order optimality conditions. We first show that this bound can be derived for a version of the algorithm, which only uses one-dimensional global optimization of the cubic model and that it is sharp. We next consider the standard trust-region method and show that a bound of the same type may also be derived for this method, and that it is also sharp in some cases. We conclude by showing that a comparison of the bounds on the worst-case behaviour of the cubic regularization and trust-region algorithms favours the first of these methods. © 2011 Elsevier Inc. All rights reserved.

KW - evaluation complexity

KW - second-order optimality conditions

KW - nonconvex optimization

KW - worst-case analysis

UR - http://www.scopus.com/inward/record.url?scp=82555189756&partnerID=8YFLogxK

U2 - 10.1016/j.jco.2011.06.001

DO - 10.1016/j.jco.2011.06.001

M3 - Article

VL - 28

SP - 93

EP - 108

JO - Journal of Complexity

JF - Journal of Complexity

SN - 0885-064X

ER -