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

Research output: Contribution to journal › Article › peer-review

46 Downloads (Pure)

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.

Original language	English
Pages (from-to)	68-94
Number of pages	32
Journal	Journal of Complexity
Volume	53
DOIs	https://doi.org/10.1016/j.jco.2018.11.001
Publication status	Published - 10 Aug 2019

Keywords

Complexity theory
Constrained problems
High-order optimality conditions
Nonlinear optimization

Access to Document

10.1016/j.jco.2018.11.001

2018_TointP_articleAccepted author manuscript, 570 KB

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Evaluation complexity of algorithms for nonconvex optimization

High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms

A concise second-order complexity analysis for unconstrained optimization using high-order regularized models

Complexity in nonlinear optimization

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

5th Conference on Numerical Analysis and Optimization

University of Oxford

Recent progress in evaluation complexity for nonlinear optimization

Cite this

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Research output

Projects

Activities

Cite this