On the evaluation complexity of cubic regularization methods
  for potentially rank-deficient nonlinear least-squares problems and its
             relevance to constrained nonlinear optimization

              by C. Cartis, N. I. M. Gould and Ph. L. Toint

              NAXYS-05-2012                   March 2012

Abstract. 
We propose a new termination criteria suitable for potentially singular, zero
or non-zero residual, least-squares problems, with which cubic regularization
variants take at most O(epsilon^{-3/2}) residual- and Jacobian-evaluations to
drive either the residual or a scaled gradient of the least-squares function
below epsilon; this is the best-known bound for potentially singular nonlinear
least-squares problems.  We then apply the new optimality measure and cubic
regularization steps to a family of least-squares merit functions in the
context of a target-following algorithm for nonlinear equality-constrained
problems; this approach yields the first evaluation complexity bound of order
epsilon^{-3/2} for nonconvexly constrained problems when higher accuracy is
required for primal feasibility than for dual first-order criticality.