On the evaluation complexity of constrained nonlinear least-squares and
general constrained nonlinear optimization using second-order method
by C. Cartis, N. I. M. Gould and Ph. L. Toint
Report NAXYS-01-2013
Abstract.
When solving the general smooth nonlinear and possibly nonconvex optimization
problem involving equality and/or inequality constraints, an approximate
first-order critical point of accuracy $\epsilon$ can be obtained by a
second-order method using cubic regularization in at most $O(\epsilon^{-3/2})$
evaluations of problem functions, the same order bound as in the unconstrained
case. This result is obtained by first showing that the same result holds for
inequality constrained nonlinear least-squares. As a consequence, the presence
of (possibly nonconvex) equality/inequality constraints does not affect the
complexity of finding approximate first-order critical points in nonconvex
optimization. This result improves on the best known ($O(\epsilon^{-2})$)
evaluation-complexity bound for solving general nonconvexly constrained
optimization problems.