Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Coralia Cartis; Nicholas I M Gould; Philippe Toint

doi:10.1007/978-3-030-12767-1_2

Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Coralia Cartis
, Nicholas I M Gould
, Philippe Toint

Namur Institute for Complex Systems

Research output: Contribution in Book/Catalog/Report/Conference proceeding › Chapter

Abstract

Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(ε- ^−3∕2 ) proved by Cartis et al. (IMA J Numer Anal 32:1662–1695, 2012) for computing an ε-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are used, resulting in a bound of (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) evaluations (ε- _P and ε- _D being primal and dual accuracy thresholds) suggested by Cartis et al. (SIAM J. Numer. Anal. 53:836–851, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of (Formula presented) evaluations under similarly weakened assumptions.

Original language	English
Title of host publication	Springer Optimization and Its Applications
Subtitle of host publication	Algorithms, Complexity and Applications
Editors	Iannis Demetriou, Panos Pardalos
Publisher	Springer Heidelberg
Chapter	1
Pages	5-26
Number of pages	22
ISBN (Electronic)	978-3-030-12766-4
DOIs	https://doi.org/10.1007/978-3-030-12767-1_2
Publication status	Published - Jun 2019

Publication series

Name	Springer Optimization and Its Applications
Volume	145
ISSN (Print)	1931-6828
ISSN (Electronic)	1931-6836

Funding

Acknowledgements The work of the second author was supported by EPSRC grants EP/I013067/1 and EP/M025179/1. The third author gratefully acknowledges the financial support of the Belgian Fund for Scientific Research, the Leverhulme Trust and Balliol College (Oxford). The work of the second author was supported by EPSRC grants EP/I013067/1 and EP/M025179/1. The third author gratefully acknowledges the financial support of the Belgian Fund for Scientific Research, the Leverhulme Trust and Balliol College (Oxford).

Funders	Funder number
Balliol College, University of Oxford
Leverhulme Trust
Belgian Fund for Scientific Research
Engineering and Physical Sciences Research Council	EP/I013067/1, EP/M025179/1

Keywords

Complexity theory
Nonlinear optimization
scaled optimality conditions

Access to Document

10.1007/978-3-030-12767-1_2

Cite this

Cartis, C., Gould, N. I. M., & Toint, P. (2019). Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models. In I. Demetriou, & P. Pardalos (Eds.), Springer Optimization and Its Applications: Algorithms, Complexity and Applications (pp. 5-26). (Springer Optimization and Its Applications; Vol. 145). Springer Heidelberg. https://doi.org/10.1007/978-3-030-12767-1_2

Cartis, Coralia ; Gould, Nicholas I M ; Toint, Philippe. / Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models. Springer Optimization and Its Applications: Algorithms, Complexity and Applications. editor / Iannis Demetriou ; Panos Pardalos. Springer Heidelberg, 2019. pp. 5-26 (Springer Optimization and Its Applications).

@inbook{de94c500502543daa0d5f17b80c41c7d,

title = "Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models",

abstract = "Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(ε- −3∕2 ) proved by Cartis et al. (IMA J Numer Anal 32:1662–1695, 2012) for computing an ε-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are used, resulting in a bound of (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) evaluations (ε- P and ε- D being primal and dual accuracy thresholds) suggested by Cartis et al. (SIAM J. Numer. Anal. 53:836–851, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of (Formula presented) evaluations under similarly weakened assumptions. ",

keywords = "Complexity theory, Nonlinear optimization, scaled optimality conditions",

author = "Coralia Cartis and Gould, \{Nicholas I M\} and Philippe Toint",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.",

year = "2019",

month = jun,

doi = "10.1007/978-3-030-12767-1\_2",

language = "English",

series = "Springer Optimization and Its Applications",

publisher = "Springer Heidelberg",

pages = "5--26",

editor = "Iannis Demetriou and Panos Pardalos",

booktitle = "Springer Optimization and Its Applications",

address = "Germany",

}

Cartis, C, Gould, NIM & Toint, P 2019, Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models. in I Demetriou & P Pardalos (eds), Springer Optimization and Its Applications: Algorithms, Complexity and Applications. Springer Optimization and Its Applications, vol. 145, Springer Heidelberg, pp. 5-26. https://doi.org/10.1007/978-3-030-12767-1_2

Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models. / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe.
Springer Optimization and Its Applications: Algorithms, Complexity and Applications. ed. / Iannis Demetriou; Panos Pardalos. Springer Heidelberg, 2019. p. 5-26 (Springer Optimization and Its Applications; Vol. 145).

Research output: Contribution in Book/Catalog/Report/Conference proceeding › Chapter

TY - CHAP

T1 - Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

AU - Cartis, Coralia

AU - Gould, Nicholas I M

AU - Toint, Philippe

PY - 2019/6

Y1 - 2019/6

N2 - Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(ε- −3∕2 ) proved by Cartis et al. (IMA J Numer Anal 32:1662–1695, 2012) for computing an ε-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are used, resulting in a bound of (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) evaluations (ε- P and ε- D being primal and dual accuracy thresholds) suggested by Cartis et al. (SIAM J. Numer. Anal. 53:836–851, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of (Formula presented) evaluations under similarly weakened assumptions.

AB - Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(ε- −3∕2 ) proved by Cartis et al. (IMA J Numer Anal 32:1662–1695, 2012) for computing an ε-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are used, resulting in a bound of (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) evaluations (ε- P and ε- D being primal and dual accuracy thresholds) suggested by Cartis et al. (SIAM J. Numer. Anal. 53:836–851, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of (Formula presented) evaluations under similarly weakened assumptions.

KW - Complexity theory

KW - Nonlinear optimization

KW - scaled optimality conditions

UR - https://www.scopus.com/pages/publications/85065814036

U2 - 10.1007/978-3-030-12767-1_2

DO - 10.1007/978-3-030-12767-1_2

M3 - Chapter

T3 - Springer Optimization and Its Applications

SP - 5

EP - 26

BT - Springer Optimization and Its Applications

A2 - Demetriou, Iannis

A2 - Pardalos, Panos

PB - Springer Heidelberg

ER -

Cartis C, Gould NIM, Toint P. Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models. In Demetriou I, Pardalos P, editors, Springer Optimization and Its Applications: Algorithms, Complexity and Applications. Springer Heidelberg. 2019. p. 5-26. (Springer Optimization and Its Applications). doi: 10.1007/978-3-030-12767-1_2

Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Abstract

Publication series

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Evaluation complexity of algorithms for nonconvex optimization

Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

Complexity of partially separable convexly constrained optimization with non-Lipschitzian singularities

Complexity in nonlinear optimization

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

University of Oxford

A path and some adventures in the jungle of high-order nonlinear optimization

A path and some adventures in the jungle of high-order nonlinear optimization

Leverhulme Fellow

Oliver Smithies Fellow

Cite this

Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Abstract

Publication series

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Research output

Projects

Activities

Prizes

Cite this