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.