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

1 Downloads (Pure)


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
Publication statusPublished - 10 Aug 2019



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

Cite this