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

Coralia Cartis, Nicholas I M Gould, Philippe Toint

Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférenceChapitre

Résumé

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.

langue originaleAnglais
titreSpringer Optimization and Its Applications
Sous-titreAlgorithms, Complexity and Applications
rédacteurs en chefIannis Demetriou, Panos Pardalos
EditeurSpringer Heidelberg
Chapitre1
Pages5-26
Nombre de pages22
ISBN (Electronique)978-3-030-12766-4
Les DOIs
étatPublié - juin 2019

Série de publications

NomSpringer Optimization and Its Applications
Volume145
ISSN (imprimé)1931-6828
ISSN (Electronique)1931-6836

Empreinte digitale

KKT Conditions
Constrained Optimization
Nonlinear Optimization
Higher Order
Derivatives
Constrained optimization
Evaluation
Higher order derivative
Equality Constraints
Inequality Constraints
Model
Critical point
First-order
Derivative
Computing

Citer ceci

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. Dans I. Demetriou, & P. Pardalos (eds.), Springer Optimization and Its Applications: Algorithms, Complexity and Applications (p. 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. Editeur / Iannis Demetriou ; Panos Pardalos. Springer Heidelberg, 2019. p. 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",
year = "2019",
month = "6",
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. Dans I Demetriou & P Pardalos (eds), Springer Optimization and Its Applications: Algorithms, Complexity and Applications. Springer Optimization and Its Applications, VOL. 145, Springer Heidelberg, p. 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).

Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférenceChapitre

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 - http://www.scopus.com/inward/record.url?scp=85065814036&partnerID=8YFLogxK

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. Dans Demetriou I, Pardalos P, rédacteurs en chef, Springer Optimization and Its Applications: Algorithms, Complexity and Applications. Springer Heidelberg. 2019. p. 5-26. (Springer Optimization and Its Applications). https://doi.org/10.1007/978-3-030-12767-1_2