Complexity bounds for second-order optimality in unconstrained optimization

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

doi:10.1016/j.jco.2011.06.001

Complexity bounds for second-order optimality in unconstrained optimization

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

Research output: Contribution to journal › Article

25 Downloads (Pure)

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. © 2011 Elsevier Inc. All rights reserved.

Original language	English
Pages (from-to)	93-108
Number of pages	16
Journal	Journal of Complexity
Volume	28
DOIs	https://doi.org/10.1016/j.jco.2011.06.001
Publication status	Published - 1 Feb 2012

Fingerprint

Unconstrained Optimization

Optimality

Regularization

Global optimization

Trust Region Algorithm

Second-order Optimality Conditions

Trust Region Method

Minimizer

Iterate

Global Optimization

Iteration

Evaluation

Model

Keywords

evaluation complexity
second-order optimality conditions
nonconvex optimization
worst-case analysis

Cite this

Cartis, C., Gould, N. I. M., & Toint, P. (2012). Complexity bounds for second-order optimality in unconstrained optimization. Journal of Complexity, 28, 93-108. https://doi.org/10.1016/j.jco.2011.06.001

Cartis, Coralia ; Gould, N.I.M. ; Toint, Philippe. / Complexity bounds for second-order optimality in unconstrained optimization. In: Journal of Complexity. 2012 ; Vol. 28. pp. 93-108.

@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",

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.",

}

Cartis, C, Gould, NIM & Toint, P 2012, 'Complexity bounds for second-order optimality in unconstrained optimization', Journal of Complexity, vol. 28, pp. 93-108. https://doi.org/10.1016/j.jco.2011.06.001

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

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

Research output: Contribution to journal › Article

TY - JOUR

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

AU - Cartis, Coralia

AU - Gould, N.I.M.

AU - Toint, Philippe

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