Improved worst-case evaluation complexity
   for potentially rank-deficient nonlinear least-Euclidean-norm
        problems using higher-order regularized models

          C. Cartis, N. I. M. Gould and Ph. L. Toint
           Report NAXYS-12-2015      17 November 2015

Abstract.  Given a sufficiently smooth vector-valued function $r(x)$, a local
minimizer of $\|r(x)\|_2$ within a closed, non-empty, convex set $\calF$ is
sought by modelling $\|r(x)\|^q_2 / q$ with a $p$-th order Taylor-series
approximation plus a $(p+1)$-st order regularization term for given even $p$
and some appropriate associated $q$.  The resulting algorithm is guaranteed to
find a value $\bar{x}$ for which $\|r(\bar{x})\|_2 \leq \epsilon_p$ or
$\chi(\bar{x}) \leq \epsilon_d$, for some first-order criticality measure
$\chi(x)$ of $\|r(x)\|_2$ within $\calF$, using at most
$O(\max\{\max(\epsilon_d,\chi_{\min})^{-(p+1)/p},
\max(\epsilon_p,r_{\min})^{-1/2^i}\})$ evaluations of $r(x)$ and its
derivatives; here $r_{\min}$ and $\chi_{\min} \geq 0$ are any lower bounds on
$\|r(x)\|_2$ and $\chi(x)$, respectively, and $2^i$ is the highest power of
$2$ that divides $p$.  An improved bound is possible under a suitable
full-rank assumption.