On the complexity of finding first-order critical
points in constrained nonlinear optimization
by C. Cartis, N. Gould, Ph. L. Toint
naXys report 13-2011
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
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.
Keywords: evaluation complexity, worst-case analysis, constrained
nonlinear optimization.