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.