On the complexity of finding first-order critical points in constrained nonlinear optimization

Coralia Cartis, Nick Gould, Philippe Toint

Research output: Contribution to journalArticlepeer-review

Abstract

The complexity of finding -approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order short-step homotopy algorithm consisting of a feasibility phase followed by an optimization phase, and requires minimal assumptions on the objective function. Since a bound of the same order is known to be valid for the unconstrained case, this leads to the conclusion that the presence of possibly nonlinear/nonconvex inequality/equality constraints is irrelevant for this bound to apply.

Original languageEnglish
Pages (from-to)93-106
Number of pages14
JournalMathematical programming
Volume144
Issue number1-2
Early online date8 Dec 2012
DOIs
Publication statusPublished - Apr 2014

Keywords

  • Evaluation complexity
  • Worst-case analysis
  • Constrained nonlinear optimization
  • CUBIC REGULARIZATION
  • NONCONVEX
  • MINIMIZATION
  • ALGORITHMS

Fingerprint

Dive into the research topics of 'On the complexity of finding first-order critical points in constrained nonlinear optimization'. Together they form a unique fingerprint.

Cite this