Projects per year
Abstract
The complexity of finding eApproximate firstorder critical points for the general smooth constrained optimization problem is shown to be no worse that O(e2) in terms of function and constraints evaluations. This result is obtained by analyzing the worstcase behaviour of a firstorder shortstep 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. © 2012 SpringerVerlag Berlin Heidelberg and Mathematical Optimization Society.
Original language  English 

Pages (fromto)  93106 
Number of pages  14 
Journal  Mathematical Programming 
Volume  144 
Issue number  12 
DOIs  
Publication status  Published  2014 
Keywords
 Constrained nonlinear optimization
 Evaluation complexity
 Worstcase analysis
Fingerprint Dive into the research topics of 'On the complexity of finding firstorder critical points in constrained nonlinear optimization'. Together they form a unique fingerprint.
Projects
 2 Active

Complexity in nonlinear optimization
TOINT, P., Gould, N. I. M. & Cartis, C.
1/11/08 → …
Project: Research

Activities

How much patience do you have? Issues in complexity for nonlinear optimization
Philippe Toint (Invited speaker)
5 Feb 2016Activity: Talk or presentation types › Oral presentation

Polytechnic University of Hong Kong
Philippe Toint (Visiting researcher)
31 Jan 2016 → 14 Feb 2016Activity: Visiting an external institution types › Research/Teaching in a external institution

How much patience do you have? Issues in complexity for nonlinear optimization
Philippe Toint (Speaker)
31 Jan 2016Activity: Talk or presentation types › Oral presentation