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

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

Research output: Contribution to journalArticle

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 languageEnglish
Pages (from-to)68-94
Number of pages32
JournalJournal of Complexity
Volume53
DOIs
Publication statusPublished - 10 Aug 2019

Fingerprint

Nonconvex Optimization
Constrained optimization
Constrained Optimization
Optimality
Criticality
Higher Order
Evaluation
Penalization
Nonlinear Optimization
Critical point
Necessary Conditions

Keywords

  • Complexity theory
  • Constrained problems
  • High-order optimality conditions
  • Nonlinear optimization

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",
year = "2019",
month = "8",
day = "10",
doi = "2018_TointPh_Article",
language = "English",
volume = "53",
pages = "68--94",
journal = "Journal of Complexity",
issn = "0885-064X",
publisher = "Academic Press Inc.",

}

Optimality of orders one to three and beyond : Characterization and evaluation complexity in constrained nonconvex optimization. / Cartis, Coralia; Gould, N. I. M.; Toint, Philippe.

In: Journal of Complexity, Vol. 53, 10.08.2019, p. 68-94.

Research output: Contribution to journalArticle

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

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 - 2018_TointPh_Article

DO - 2018_TointPh_Article

M3 - Article

VL - 53

SP - 68

EP - 94

JO - Journal of Complexity

JF - Journal of Complexity

SN - 0885-064X

ER -