ON THE EVALUATION COMPLEXITY OF CONSTRAINED NONLINEAR LEAST-SQUARES AND GENERAL CONSTRAINED NONLINEAR OPTIMIZATION USING SECOND-ORDER METHODS

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 leastsquares. 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.