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

50 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	27
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.

Bailleurs de fonds	Numéro du bailleur de fonds
Department of Applied Mathematics
ENSEEIHT
Istituto Nazionale di Alta Matematica "Francesco Severi"
Engineering and Physical Sciences Research Council	EP/M025179/1
Leverhulme Trust
Fonds De La Recherche Scientifique - FNRS
Hong Kong Polytechnic University
Balliol college

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

12 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
50 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 - https://www.scopus.com/pages/publications/85057041807

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