Optimality of orders one to three and beyond: Characterization and evaluation complexity in constrained nonconvex optimization

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

doi:10.1016/j.jco.2018.11.001

Optimality of orders one to three and beyond: Characterization and evaluation complexity in constrained nonconvex optimization

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

Namur Institute for Complex Systems

Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

40 Téléchargements (Pure)

Résumé

Necessary conditions for high-order optimality in smooth nonlinear constrained optimization are explored and their inherent intricacy discussed. A two-phase minimization algorithm is proposed which can achieve approximate first-, second- and third-order criticality and its evaluation complexity is analyzed as a function of the choice (among existing methods) of an inner algorithm for solving subproblems in each of the two phases. The relation between high-order criticality and penalization techniques is finally considered, showing that standard algorithmic approaches will fail if approximate constrained high-order critical points are sought.

langue originale	Anglais
Pages (de - à)	68-94
Nombre de pages	32
journal	Journal of Complexity
Volume	53
Les DOIs	https://doi.org/10.1016/j.jco.2018.11.001
Etat de la publication	Publié - 10 août 2019

Financement

The authors would like to thank Oliver Stein for suggesting reference [41] . The work of the second author was supported by EPSRC, United Kingdom grant EP/M025179/1 . The third author acknowledges the support provided by the Belgian Fund for Scientific Research (FNRS) , the Leverhulme Trust (UK) , Balliol College (Oxford, UK) , the Department of Applied Mathematics of the Hong Kong Polytechnic University , ENSEEIHT (Toulouse, France) and INDAM (Florence, Italy) . Thanks are also due to a thoughtful referee whose patience and perceptive comments have helped to significantly improve the manuscript. Appendix

Accès au document

10.1016/j.jco.2018.11.001

2018_TointP_articleAccepted author manuscript, 570 KB

Autres fichiers et liens

Link to publication in Scopus

10 Citations
14 Article
3 Papier de travail
1 Livre
1 Chapitre
Afficher plus d’informations
- 1 Article dans les actes d'une conférence/un colloque

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
High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms
Chen, X. & Toint, P., mai 2021, Dans: Mathematical Programming. 187, 1-2, p. 47-78 32 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

Accès ouvert
File
43 Téléchargements (Pure)
A concise second-order complexity analysis for unconstrained optimization using high-order regularized models
Cartis, C., Gould, N. I. M. & Toint, P. L., 3 mars 2020, Dans: Optimization Methods and Software. 35, 2, p. 243-256 14 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

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

3 Discours invité
2 Visite à une institution académique externe
1 Participation à un atelier/workshop, un séminaire, un cours

5th Conference on Numerical Analysis and Optimization
Toint, P. (Orateur)
6 janv. 2020 → 9 janv. 2020
Activité: Participation ou organisation d'un événement › Participation à un atelier/workshop, un séminaire, un cours
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
Recent progress in evaluation complexity for nonlinear optimization
Toint, P. (Orateur)
4 oct. 2019
Activité: Discours ou présentation › Discours invité

Contient cette citation

@article{d401d6ce8bc04e38bbd433bb13c09735,

title = "Optimality of orders one to three and beyond: Characterization and evaluation complexity in constrained nonconvex optimization",

abstract = "Necessary conditions for high-order optimality in smooth nonlinear constrained optimization are explored and their inherent intricacy discussed. A two-phase minimization algorithm is proposed which can achieve approximate first-, second- and third-order criticality and its evaluation complexity is analyzed as a function of the choice (among existing methods) of an inner algorithm for solving subproblems in each of the two phases. The relation between high-order criticality and penalization techniques is finally considered, showing that standard algorithmic approaches will fail if approximate constrained high-order critical points are sought.",

keywords = "Complexity theory, Constrained problems, High-order optimality conditions, Nonlinear optimization",

author = "Coralia Cartis and Gould, {N. I. M.} and Philippe Toint",

note = "Funding Information: The authors would like to thank Oliver Stein for suggesting reference [41] . The work of the second author was supported by EPSRC, United Kingdom grant EP/M025179/1 . The third author acknowledges the support provided by the Belgian Fund for Scientific Research (FNRS) , the Leverhulme Trust (UK) , Balliol College (Oxford, UK) , the Department of Applied Mathematics of the Hong Kong Polytechnic University , ENSEEIHT (Toulouse, France) and INDAM (Florence, Italy) . Thanks are also due to a thoughtful referee whose patience and perceptive comments have helped to significantly improve the manuscript. Publisher Copyright: {\textcopyright} 2018 Elsevier Inc. Copyright: Copyright 2019 Elsevier B.V., All rights reserved.",

year = "2019",

month = aug,

day = "10",

doi = "10.1016/j.jco.2018.11.001",

language = "English",

volume = "53",

pages = "68--94",

journal = "Journal of Complexity",

issn = "0885-064X",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Optimality of orders one to three and beyond

T2 - Characterization and evaluation complexity in constrained nonconvex optimization

AU - Cartis, Coralia

AU - Gould, N. I. M.

AU - Toint, Philippe

N1 - Funding Information: The authors would like to thank Oliver Stein for suggesting reference [41] . The work of the second author was supported by EPSRC, United Kingdom grant EP/M025179/1 . The third author acknowledges the support provided by the Belgian Fund for Scientific Research (FNRS) , the Leverhulme Trust (UK) , Balliol College (Oxford, UK) , the Department of Applied Mathematics of the Hong Kong Polytechnic University , ENSEEIHT (Toulouse, France) and INDAM (Florence, Italy) . Thanks are also due to a thoughtful referee whose patience and perceptive comments have helped to significantly improve the manuscript. Publisher Copyright: © 2018 Elsevier Inc. Copyright: Copyright 2019 Elsevier B.V., All rights reserved.

PY - 2019/8/10

Y1 - 2019/8/10

N2 - Necessary conditions for high-order optimality in smooth nonlinear constrained optimization are explored and their inherent intricacy discussed. A two-phase minimization algorithm is proposed which can achieve approximate first-, second- and third-order criticality and its evaluation complexity is analyzed as a function of the choice (among existing methods) of an inner algorithm for solving subproblems in each of the two phases. The relation between high-order criticality and penalization techniques is finally considered, showing that standard algorithmic approaches will fail if approximate constrained high-order critical points are sought.

AB - Necessary conditions for high-order optimality in smooth nonlinear constrained optimization are explored and their inherent intricacy discussed. A two-phase minimization algorithm is proposed which can achieve approximate first-, second- and third-order criticality and its evaluation complexity is analyzed as a function of the choice (among existing methods) of an inner algorithm for solving subproblems in each of the two phases. The relation between high-order criticality and penalization techniques is finally considered, showing that standard algorithmic approaches will fail if approximate constrained high-order critical points are sought.

KW - Complexity theory

KW - Constrained problems

KW - High-order optimality conditions

KW - Nonlinear optimization

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

U2 - 10.1016/j.jco.2018.11.001

DO - 10.1016/j.jco.2018.11.001

M3 - Article

AN - SCOPUS:85057041807

SN - 0885-064X

VL - 53

SP - 68

EP - 94

JO - Journal of Complexity

JF - Journal of Complexity

ER -

Optimality of orders one to three and beyond: Characterization and evaluation complexity in constrained nonconvex optimization

Résumé

Financement

Accès au document

Autres fichiers et liens

Empreinte digitale

Résultat de recherche

Projets

Activités

Contient cette citation