Optimization Online


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

Coralia Cartis(coralia.cartis***at***ed.ac.uk)
Nicholas I. M. Gould( nick.gould***at***sftc.ac.uk)
Philippe L. Toint(philippe.toint***at***fundp.ac.be)

Abstract: The complexity of finding epsilon-approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that O(epsilon^{-2}) in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order shorts-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.

Keywords: evaluation complexity, worst-case analysis, constrained nonlinear optimization

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: naXys Report 13-2011, Namur Center for Complex Systems (naXys), University of Namur, Namur (Belgium)

Download: [PDF]

Entry Submitted: 04/14/2011
Entry Accepted: 04/14/2011
Entry Last Modified: 04/14/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society