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

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

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 originale	Anglais
titre	Springer Optimization and Its Applications
Sous-titre	Algorithms, Complexity and Applications
rédacteurs en chef	Iannis Demetriou, Panos Pardalos
Editeur	Springer Heidelberg
Chapitre	1
Pages	5-26
Nombre de pages	22
ISBN (Electronique)	978-3-030-12766-4
Les DOIs	https://doi.org/10.1007/978-3-030-12767-1_2
Etat de la publication	Publié - juin 2019

Série de publications

Nom	Springer Optimization and Its Applications
Volume	145
ISSN (imprimé)	1931-6828
ISSN (Electronique)	1931-6836

Financement

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).

Bailleurs de fonds	Numéro du bailleur de fonds
Engineering and Physical Sciences Research Council	EP/I013067/1, EP/M025179/1
Leverhulme Trust
Fonds De La Recherche Scientifique - FNRS
Balliol college

Accès au document

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

Autres fichiers et liens

Lien vers la publication sur Scopus

6 Citations
15 Article
3 Papier de travail
1 Livre

Evaluation complexity of algorithms for nonconvex optimization
Cartis, C., Gould, N. I. M. & TOINT, P., juil. 2022, SIAM. 600 p. (SIAM-MOS Series on Optimization)
Résultats de recherche: Livre/Rapport/Revue › Livre
Adaptive regularization algorithms with inexact evaluations for nonconvex optimization
Bellavia, S., Gurioli, G., Morini, B. & Toint, P., 2 janv. 2020, Dans: SIAM Journal on Optimization. 29, 4, p. 2881-2915 35 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

Accès ouvert
File
53 Téléchargements (Pure)
Complexity of partially separable convexly constrained optimization with non-Lipschitzian singularities
Chen, X., Toint, P. & Wang, H., 15 avr. 2019, Dans: SIAM Journal on Optimization. 29, 1, p. 874-903 30 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

Accès ouvert
File
36 Téléchargements (Pure)

2 Actif

Complexity in nonlinear optimization
Toint, P. (Co-investigateur), Gould, N. I. M. (Co-investigateur) & Cartis, C. (Co-investigateur)
1/11/08 → …
Projet: Recherche
ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire
Sartenaer, A. (Co-investigateur) & Toint, P. (Co-investigateur)
1/01/87 → …
Projet: Axe de recherche

4 Discours invité
4 Présentation orale
2 Visite à une institution académique externe
1 Recherche/Enseignement dans une institution externe

University of Oxford
Toint, P. (Chercheur visiteur)
20 nov. 2019 → 6 déc. 2019
Activité: Visite d'une organisation externe › Visite à une institution académique externe
A path and some adventures in the jungle of high-order nonlinear optimization
Toint, P. (Orateur)
23 oct. 2017
Activité: Discours ou présentation › Discours invité
A path and some adventures in the jungle of high-order nonlinear optimization
Toint, P. (Orateur)
24 oct. 2017
Activité: Discours ou présentation › Discours invité

Leverhulme Fellow
Toint, P. (Bénéficiaire), sept. 2015
Prix: Bourse attribuée par concours
Oliver Smithies Fellow
Toint, P. (Bénéficiaire), sept. 2015
Prix: Bourse attribuée par concours

Contient cette citation

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

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. 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érence › Chapitre

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). 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

Résumé

Série de publications

Financement

Accès au document

Autres fichiers et liens

Empreinte digitale

Résultat de recherche

Projets

Activités

Prix

Contient cette citation