Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization

Introduction

Newton’s method has long represented a benchmark for rapid asymptotic convergence when minimizing smooth, unconstrained objective functions . It has also been efficiently safeguarded to ensure its global convergence to first- and even second-order critical points, in the presence of local nonconvexity of the objective using linesearch , trust-region or other regularization techniques . Many variants of these globalization techniques have been proposed. These generally retain fast local convergence under non-degeneracy assumptions, are often suitable when solving large-scale problems and sometimes allow approximate rather than true Hessians to be employed. We attempt to capture the common features of these methods in the description of a general class of second-order methods, which we denote by ${\cal M}.\alpha$ in what follows.

In this paper, we are concerned with establishing lower bounds on the worst-case evaluation complexity of the ${\cal M}.\alpha$ methodsAnd, as an aside, on that of the steepest-descent method. when applied to “sufficiently smooth” nonconvex minimization problems, in the sense that we exhibit objective functions on which these methods take a large number of function evaluations to obtain an approximate first-order point.

There is a growing literature on the global worst-case evaluation complexity of first- and second-order methods for nonconvex smooth optimization problems (for which we provide a partial bibliography with this paper). In particular, it is known , [61, p. 29] that steepest-descent method with either exact or inexact linesearches takes at mostWhen $\{a_{k}\}$ and $\{b_{k}\}$ are two sequences of real numbers, we say that $a_{k}={\cal O}\left(b_{k}\right)$ if the ratio $a_{k}/b_{k}$ is bounded. ${\cal O}\left(\epsilon^{-2}\right)$ iterations/function-evaluations to generate a gradient whose norm is at most $\epsilon$ when started from an arbitrary initial point and applied to nonconvex smooth objectives with gradients that are globally Lipschitz continuous within some open convex set containing the iterates generated. Furthermore, this bound is essentially sharp (for inexact and exact linesearches). Similarly, trust-region methods that ensure at least a Cauchy (steepest-descent-like) decrease on each iteration satisfy a worst-case evaluation complexity bound of the same order under identical conditions . It follows that Newton’s method globalized by trust-region regularization has the same ${\cal O}\left(\epsilon^{-2}\right)$ worst-case evaluation upper bound; such a bound has also been shown to be essentially sharp .

From a worst-case complexity point of view, one can do better when a cubic regularization/perturbation of the Newton direction is used —such a method iteratively calculates step corrections by (exactly or approximately) minimizing a cubic model formed of a quadratic approximation of the objective and the cube of a weighted norm of the step. For such a method, the worst-case global complexity improves to be ${\cal O}\left(\epsilon^{-3/2}\right)$ , for problems whose gradients and Hessians are Lipschitz continuous as above; this bound is also essentially sharp . If instead powers between two and three are used in the regularization, then an “intermediate” worst-case complexity of ${\cal O}\left(\epsilon^{-(2+\alpha)/(1+\alpha)}\right)$ is obtained for such variants when applied to functions with globally $\alpha-$Hölder continuous Hessian on the path of iterates, where $\alpha\in(0,1]$ . It is finally possible, as proposed in , to obtain the desired ${\cal O}\left(\epsilon^{-3/2}\right)$ order of worst-case evaluation complexity using a purely quadratic regularization, at the price of mixing iterations using the regularized and unregularized Hessian with iterations requiring the computation of its left-most eigenpair.

These (essentially tight) upper bounds on the worst-case evaluation complexity of such second-order methods naturally raise the question as to whether other second-order methods might have better worst-case complexity than cubic (or similar) regularization over certain classes of sufficiently smooth functions. To attempt to answer this question, we define a general, parametrized class of methods that includes Newton’s method, and that attempts to capture the essential features of globalized Newton variants we have mentioned. Our class includes for example, the algorithms discussed above as well as multiplier-adjusting types such as the Goldfeld-Quandt-Trotter approach . The methods of interest take a potentially-perturbed Newton step at each iteration so long as the perturbation is “not too large” and the subproblem is solved “sufficiently accurately”. The size of the perturbation allowed is simultaneously related to the parameter $\alpha$ defining the class of methods and the rate of the asymptotic convergence of the method. For each method in each $\alpha$-parametrized class and each $\epsilon\in(0,1)$, we construct a function with globally $\alpha-$Hölder-continuous Hessian and Lipschitz continuous gradient for which the method takes precisely $\lceil\epsilon^{-(2+\alpha)/(1+\alpha)}\rceil$ function evaluations to drive the gradient norm below $\epsilon$. As such counts are the same order as the worst-case upper complexity bound of regularization methods, it follows that the latter methods are optimal within their respective $\alpha$-class of methods. As $\alpha$ approaches zero, the worst-case complexity of these methods approaches that of steepest descent, while for $\alpha=1$, we recover that of cubic regularization. We also improve the examples proposed in in two ways. The first is that we now employ objective functions with bounded range, which allows refining the associated definition of sharp worst-case evaluation complexity bounds, the second being that the new examples now have finite isolated global minimizers.

The structure of the paper is as follows. Section 2 describes the parameter-dependent class of methods and objectives of interest; Section 2.1 gives properties of the methods such as their connection to fast asymptotic rates of convergence while Section 2.2 reviews some well-known examples of methods covered by our general definition of the class. Section 3 then introduces two examples of inefficiency of these methods and Section 4 discusses the consequences of these examples regarding the sharpness and possible optimality of the associated worst-case evaluation complexity bounds. Further consequences of our results on the new class proposed by and are developed in Section 5 and 6, respectively. Section 7 draws our conclusions.

Notation. Throughout the paper, $\|\cdot\|$ denotes the Euclidean norm on $\hbox{I\hskip-2.0ptR}^{n}$, $I$ the $n\times n$ identity matrix, and $\lambda_{\min}(H)$ and $\lambda_{\max}(H)$ the left- and right-most eigenvalue of any given symmetric matrix $H$, respectively. The condition number of a symmetric positive definite matrix $M$ is denoted by $\kappa(M)\stackrel{{\scriptstyle\rm def}}{{=}}\lambda_{\max}(M)/\lambda_{\min}(M)$. If $M$ is only positive-semidefinite which we denote by $M\succeq 0$, and $\lambda_{\min}(M)=0$, then $\kappa(0)\stackrel{{\scriptstyle\rm def}}{{=}}+\infty$ unless $M=0$, in which case we set $\kappa(0)\stackrel{{\scriptstyle\rm def}}{{=}}1$. Positive definiteness of $M$ is written as $M\succ 0$.

A general parametrized class of methods and objectives

Our aim is to minimize a given $C^{2}$ objective function $f(x)$, $x\in\hbox{I\hskip-2.0ptR}^{n}$. We consider methods that generate sequences of iterates $\{x_{k}\}$ for which $\{f(x_{k})\}$ is monotonically decreasing, we let

where $g(x)=\nabla_{x}f(x)$ and $H(x)=\nabla_{xx}f(x)$.

Let $\alpha\in$ be a fixed parameter and consider iterative methods whose iterations are defined as follows. Given some $x_{0}\in\hbox{I\hskip-2.0ptR}^{n}$, let

for some residual $r_{k}$ and constants $\kappa_{rg}\in[0,1)$ and $\kappa_{rs}>0$, and for some symmetric matrix $M_{k}$ such that

for some $\kappa_{\lambda}>1$ independent of $k$. Without loss of generality, we assume that $s_{k}\neq 0$. Furthermore, we require that no infinite steps are taken, namely

for some $\kappa_{s}>0$ independent of $k$. The ${\cal M}.\alpha$ class of second-order methods consists of all methods whose iterations satisfy (2.1)–(2.5). The particular choices $M_{k}=\lambda_{k}I$ and $M_{k}=\lambda_{k}N_{k}$ (with $N_{k}$ symmetric, positive definite and with bounded condition number) will be of particular interest in what followsNote that (2.4) is slightly more general than a maybe more natural condition involving $\lambda_{\min}(H_{k}+M_{k})$ instead of $\lambda_{\min}(H_{k})+\lambda_{\min}(M_{k})$.. Note that the definition of ${\cal M}.\alpha$ just introduced generalizes that of M.$\alpha$ in .

Typically, the expression (2.2) for $s_{k}$ is derived by minimizing (possibly approximately) the second-order model

of $f(x_{k}+s)$—possibly with an explicit regularizing constraint—with the aim of obtaining a sufficient decrease of $f$ at the new iterate $x_{k+1}=x_{k}+s_{k}$ compared to $f(x_{k})$. In the definition of an ${\cal M}.\alpha$ method however, the issue of (sufficient) objective-function decrease is not explicitly addressed/required. There is no loss of generality in doing so here since although local refinement of the model may be required to ensure function decrease, the number of function evaluations to do so (at least for known methods) does not increase the overall worst-case evaluation complexity by more than a constant multiple and thus does not affect quantitatively the worst-case bounds derived; see for example, and also Section 2.2. Furthermore, the examples of inefficiency proposed in Section 3 are constructed in such a way that each iteration of the method automatically provides sufficient decrease of $f$.

Having defined the classes of methods we shall be concerned with, we now specify the problem classes that we shall apply the methods in each class to, in order to demonstrate slow convergence. Given a method in ${\cal M}.\alpha$, we are interested in minimizing functions $f$ that satisfy

A.$\alpha$ $f:\hbox{I\hskip-2.0ptR}^{n}\rightarrow\hbox{I\hskip-2.0ptR}$ is twice continuously differentiable and bounded below, with gradient $g$ being globally Lipschitz continuous on $\hbox{I\hskip-2.0ptR}^{n}$ with constant $L_{g}$, namely,

and the Hessian $H$ being globally $\alpha-$Hölder continuous on $\hbox{I\hskip-2.0ptR}^{n}$ with constant $L_{H,\alpha}$, i.e.,

The case when $\alpha=1$ in A.$\alpha$ corresponds to the Hessian of $f$ being globally Lipschitz continuous. Moreover, (2.7) implies (2.8) when $\alpha=0$, so that the A. class is that of twice continuously differentiable functions with globally Lipschitz continuous gradient. Note also that (2.7) and the existence of $H(x)$ imply that

for all $x\in\hbox{I\hskip-2.0ptR}^{n}$ [61, Lemma 1.2.2], and that every function $f$ satisfying A.$\alpha$ with $\alpha>1$ must be quadratic. As we will see below, it turns out that we could weaken the conditions defining A.$\alpha$ by only requiring (2.7) and (2.8) to hold in an open set containing all the segments $[x_{k},x_{k}+s_{k}]$ (the “path of iterates”), but these segments of course depend themselves on $f$ and the method applied.

The next subsection provides some background and justification for the technical condition (2.4) by relating it to fast rates of asymptotic convergence, which is a defining feature of second-order algorithms. In Section 2.2, we then review some methods belonging to ${\cal M}.\alpha$.

We first state inclusions properties for ${\cal M}.\alpha$ and A.$\alpha$.

Lemma 2.1 1. Consider a method of ${\cal M}.\alpha_{1}$ for $\alpha_{1}\in$ and assume that it generates bounded gradients. Then it belongs to ${\cal M}.\alpha_{2}$ for $\alpha_{2}\in[0,\alpha_{1}]$. 2. A.$\alpha_{1}$ implies A.$\alpha_{2}$ for $\alpha_{2}\in[0,\alpha_{1}]$, with $L_{H,\alpha_{2}}=\max[L_{H,\alpha_{1}},2L_{g}]$.

Proof. By assumption, $\|g_{k}\|\leq\kappa_{g}$ for some $\kappa_{g}\geq 1$. Hence, if $\|g_{k}\|\geq 1$,

for any $\alpha_{2}\in[0,\alpha_{1}]$. Moreover, (2.10) also holds if $\|g_{k}\|\leq 1$, proving the first statement of the lemma. Now we obtain from (2.9), that, if $\|x-y\|>1$, then

for any $\alpha\in$. When $\|x-y\|\leq 1$, we may deduce from (2.8) that, if $\alpha_{1}\geq\alpha_{2}$, then (2.8) with $\alpha=\alpha_{1}$ implies (2.8) with $\alpha=\alpha_{2}$. This proves the second statement. $\Box$

Observe if a method is known to be globally convergent in the sense that $\|g_{k}\|\rightarrow 0$ when $k\rightarrow\infty$, then it obviously generates bounded gradients and thus the globally convergent methods of ${\cal M}.\alpha_{1}$ are included in ${\cal M}.\alpha_{2}$ ($\alpha_{2}\in[0,\alpha_{1}]$).

We next give a sufficient, more concise, condition on the algorithm-generated matrices $M_{k}$ that implies the bound (2.4).

Lemma 2.2 Let (2.2) and (2.3) hold. Assume also that the algorithm-generated matrices $M_{k}$ satisfies \lambda_{\min}(M_{k})\leq\overline{\kappa}_{\lambda}\|s_{k}\|^{\alpha},\;\;\mbox{for some\overline{\kappa}_{\lambda}>1$and$\alpha\in$independent of$k.}\;\; (2.11) Then (2.4) holds with $\kappa_{\lambda}\stackrel{{\scriptstyle\rm def}}{{=}}2\overline{\kappa}_{\lambda}^{\frac{1}{1+\alpha}}(1+\kappa_{rg})$.

Proof. Clearly, (2.4) holds when $\lambda_{\min}(H_{k}+M_{k})=0$. When $\lambda_{\min}(H_{k}+M_{k})>0$ and hence $H_{k}+M_{k}\succ 0$, (2.2) implies that

Now note that $\psi(0)=\psi(-\lambda_{\min}(H_{k}))=-\overline{\kappa}_{\lambda}^{\frac{1}{\alpha}}(1+\kappa_{rg})\|g_{k}\|$ and thus

Moreover, the form of $\psi(\lambda)$ implies that $\psi(\lambda)$ is strictly increasing for $\lambda\geq\lambda_{1,k}$. Define now

Suppose first that $\lambda_{\min}(H_{k})<0$ and $|\lambda_{\min}(H_{k})|\geq\overline{\kappa}_{\lambda}^{\frac{1}{1+\alpha}}(1+\kappa_{rg})^{\frac{\alpha}{1+\alpha}}\|g_{k}\|^{\frac{\alpha}{1+\alpha}}$. Then one verifies that $\lambda_{2,k}=3|\lambda_{\min}(H_{k})|$ and

Suppose now that $\lambda_{\min}(H_{k})\geq 0$ and $|\lambda_{\min}(H_{k})|\geq\overline{\kappa}_{\lambda}^{\frac{1}{1+\alpha}}(1+\kappa_{rg})^{\frac{\alpha}{1+\alpha}}\|g_{k}\|^{\frac{\alpha}{1+\alpha}}$. Then $\lambda_{2,k}=\lambda_{\min}(H_{k})$ and

Thus we deduce that $\psi(\lambda_{2,k})>0$ whenever $|\lambda_{\min}(H_{k})|\geq\overline{\kappa}_{\lambda}^{\frac{1}{1+\alpha}}(1+\kappa_{rg})^{\frac{\alpha}{1+\alpha}}\|g_{k}\|^{\frac{\alpha}{1+\alpha}}$. Moreover the same inequality obviously holds if $|\lambda_{\min}(H_{k})|<\overline{\kappa}_{\lambda}^{\frac{1}{1+\alpha}}(1+\kappa_{rg})^{\frac{\alpha}{1+\alpha}}\|g_{k}\|^{\frac{\alpha}{1+\alpha}}$ because $\psi(\lambda)$ is increasing with $\lambda$. As a consequence, $\psi(\lambda_{2,k})>0$ in all cases. We now combine this inequality, (2.14) and the monotonicity of $\psi(\lambda)$ for $\lambda\geq\lambda_{1,k}$ to obtain that either $\lambda_{\min}(M_{k})\leq\lambda_{1,k}<\lambda_{2,k}$ or $\lambda_{\min}(M_{k})\in[\lambda_{1,k},\lambda_{2,k})$ because of of (2.13). Thus $\lambda_{\min}(M_{k})\leq\lambda_{2,k}$, which, due to (2.15) and $\overline{\kappa}_{\lambda}>1$, implies (2.4). $\Box$

Thus a method satisfying (2.1)–(2.5) and (2.11) belongs to ${\cal M}.\alpha$, but not every method in ${\cal M}.\alpha$ needs to satisfy (2.11). This latter requirement implies the following property regarding the length of the step generated by methods in ${\cal M}.\alpha$ satisfying (2.11) when applied to functions satisfying A.$\alpha$.

Lemma 2.3 Assume that an objective function $f$ satisfying A.$\alpha$ is minimized by a method satisfying (2.1), (2.2), (2.11) and such that the conditioning of $M_{k}$ is bounded in that $\kappa(M_{k})\leq\kappa_{\kappa}$ for some $\kappa_{\kappa}\geq 1$. Then there exists $\overline{\kappa}_{s,\alpha}>0$ independent of $k$ such that, for $k\geq 0$, $\|s_{k}\|\geq\overline{\kappa}_{s,\alpha}\|g_{k+1}\|^{\frac{1}{1+\alpha}}.$ (2.16)

From (2.1), $g_{k+1}=g(x_{k}+s_{k})$ and Taylor expansion provides $g_{k+1}=g_{k}+\int_{0}^{1}H(x_{k}+\tau s_{k})s_{k}d\tau$. This and (2.8) now imply

so that (2.17) and (2.2) together give that

If $M_{k}\neq 0$, this inequality and the fact that $\kappa(M_{k})$ is bounded then imply that

while we may ignore the last term on the right-hand side if $M_{k}=0$. Hence, in all cases,

where we used that $\kappa(M_{k})\leq\kappa_{\kappa}$ by assumption. This bound and (2.11) then imply (2.16) with $\overline{\kappa}_{s,\alpha}\stackrel{{\scriptstyle\rm def}}{{=}}[L_{H,\alpha}(1+\alpha)^{-1}+\kappa_{\kappa}(1+\kappa_{rs})\overline{\kappa}_{\lambda}]^{-\frac{1}{1+\alpha}}$. $\Box$

Property (2.16) will be central for proving (in Appendix A2) desirable properties of a class of methods belonging to ${\cal M}.\alpha$. In addition, we now show that (2.16) is a necessary condition for fast local convergence of methods of type (2.2), under reasonable assumptions; fast local rate of convergence in a neighbourhood of well-behaved minimizers is a “trademark” of what is commonly regarded as second-order methods.

Lemma 2.4 Let $f$ satisfy assumptions A.$\alpha$. Apply an algorithm to minimizing $f$ that satisfies (2.1) and (2.2) and for which \|M_{k}\|\leq\overline{\kappa}_{\lambda},\;\;\mbox{k\geq 0$, \quad for some$\overline{\kappa}_{\lambda}>0$independent of$k.}\;\; (2.18) Assume also that convergence at linear or faster than linear rate occurs, namely, $\|g_{k+1}\|\leq\kappa_{c}\|g_{k}\|^{1+\alpha},\quad k\geq 0,$ (2.19) for some $\kappa_{c}>0$ independent of $k$, with $\kappa_{c}\in(0,1)$ when $\alpha=0$. Then (2.16) holds.

From (2.19) and the definition of $\alpha_{k}$ in (2.20), we have that, for $k\geq 0$,

where $\kappa_{c,\alpha}\stackrel{{\scriptstyle\rm def}}{{=}}\kappa_{c}^{\frac{1}{1+\alpha}}$ and where we used (2.2) to obtain the first equality. It follows that

The bounds (2.9) and (2.18) imply that $\{H_{k}+M_{k}\}$ is uniformly bounded above for all $k$, namely,

where $\kappa_{hl}\stackrel{{\scriptstyle\rm def}}{{=}}L_{g}+\overline{\kappa}_{\lambda}$. Now (2.21) and (2.22) give that $\alpha_{k}\geq 1/(\kappa_{hl}\kappa_{c,\alpha})>0$, for all $k\geq 0$, and so it follows from (2.20), that (2.16) holds with $\overline{\kappa}_{s,\alpha}\stackrel{{\scriptstyle\rm def}}{{=}}(1-\kappa_{rg})/(\kappa_{c_{1}}\kappa_{c,\alpha})$. $\Box$

It is clear from the proof of Lemma 2.4 that (2.19) is only needed asymptotically, that is for all $k$ sufficiently large; for simplicity, we have assumed it holds globally.

Note that letting $\alpha=1$ in Lemma 2.4 provides a necessary condition for quadratically convergent methods satisfying (2.1), (2.2) and (2.18). Also, similarly to the above proof, one can show that if superlinear convergence of $\{g_{k}\}$ to zero occurs, then (2.16) holds with $\alpha=0$ for all $\overline{\kappa}_{s,\alpha}>0$, or equivalently, $\|g_{k+1}\|/\|s_{k}\|\rightarrow 0$, as $k\rightarrow\infty$.

Summarizing, we have shown that (2.16) holds for a method in ${\cal M}.\alpha$ if (2.11) holds and $\kappa(M_{k})$ is bounded, or if linear of faster asymptotic convergence takes place for unit steps.

2 Some examples of methods that belong to the class ℳ.αformulae-sequenceℳ𝛼{\cal M}.\alpha

Let us now illustrate some of the methods that either by construction or under certain conditions belong to ${\cal M}.\alpha$. This list of methods does not attempt to be exhaustive and other practical methods may be found to belong to ${\cal M}.\alpha$.

Newton’s method . Newton’s method for convex optimization is characterised by finding a correction $s_{k}$ that satisfies $H_{k}s_{k}=-g_{k}$ for nonzero $g_{k}\in{\rm Range}(H_{k})$. Letting

in (2.2) and (2.6), respectively, yields Newton’s method. Provided additionally that both $g_{k}\in{\rm Range}(H_{k})$ and $H_{k}$ is positive semi-definite, $s_{k}$ is a descent direction and (2.3) holds. Since (2.4) is trivially satisfied in this case, it follows that Newton’s method belongs to the class ${\cal M}.\alpha$, for any $\alpha\in$, provided it does not generate infinite steps to violate (2.5). As Newton’s method is commonly embedded within trust-region or regularization frameworks when applied to nonconvex functions, (2.5) will in fact, hold as it is generally enforced for the latter methods. Note that allowing $\|r_{k}\|>0$ subject to the second part of (2.2) then covers inexact variants of Newton’s method.

Regularization algorithms . In these methods, the step $s_{k}$ from the current iterate $x_{k}$ is computed by (possibly approximately) globally minimizing the model

where the regularization weight $\sigma_{k}$ is adjusted to ensure sufficient decrease of $f$ at $x_{k}+s_{k}$. We assume here that the minimization of (2.24) is carried accurately enough to ensure that $\nabla_{ss}^{\texttwosuperior}m_{k}-(s)=H_{k}+\sigma_{k}\|s\|I$ is positive semidefinite, which is always possible because of [16, Theorem 3.1]. The scalar $\alpha$ is the same fixed parameter as in the definition of A.$\alpha$ and ${\cal M}.\alpha$, so that for each $\alpha\in$, we have a different regularization term and hence what we shall call an $(2+\alpha)$-regularization method. For $\alpha=1$, we recover the cubic regularization (ARC) approach . For $\alpha=0$, we obtain a quadratic regularization scheme, reminiscent of the Levenberg-Morrison-Marquardt method . For these $(2+\alpha)$-regularization methods, we have

in (2.2) and (2.6). If scaling the regularization term is considered, then the second of these relation is replaced by $M_{k}=\sigma_{k}\|s_{k}\|^{\alpha}N_{k}$ for some fixed scaling symmetric positive definite matrix having a bounded condition number. Note that, by construction, $\kappa(M_{k})=1$. Since $\alpha\geq 0$, we have $0\leq\beta_{k}\leq 1$ which is required in (2.6). A mechanism of successful and unsuccessful iterations and $\sigma_{k}$ adjustments can be devised similarly to ARC [16, Alg. 2.1] in order to deal with steps $s_{k}$ that do not give sufficient decrease in the objective. An upper bound on the number of unsuccessful iterations which is constant multiple of successful ones can be given under mild assumptions on $f$ [17, Theorem 2.1]. Note that each (successful or unsuccessful) iteration requires one function- and at most one gradient evaluation.

We now show that for each $\alpha\in$, the $(2+\alpha)-$regularization method based on the model (2.24) satisfies (2.5) and (2.4) when applied to $f$ in A.$\alpha$, and so it belongs to ${\cal M}.\alpha$.

Lemma 2.5 Let $f$ satisfy A.$\alpha$ with $\alpha\in(0,1]$. Consider minimizing $f$ by applying an $(2+\alpha)$-regularization method based on the model (2.24), where the step $s_{k}$ is chosen as the global minimizer of the local $\alpha-$model, namely of $m_{k}(s)$ in (2.6) with the choice (2.25), and where the regularization parameter $\sigma_{k}$ is chosen to ensure that $\sigma_{k}\geq\sigma_{\min},\quad k\geq 0,$ (2.26) for some $\sigma_{\min}>0$ independent of $k$. Then (2.5) and (2.11) hold, and so the $(2+\alpha)$-regularization method belongs to ${\cal M}.\alpha$.

Proof. (see Appendix A2 for details) The same argument that is used in [16, Lem.2.2] for the $\alpha=1$ case (see also Appendix A2) provides

so long as A.$\alpha$ holds, which together with (2.26), implies

The assumptions A.$\alpha$, that the model is minimized globally imply that the $\alpha\leq 1$ analog of [16, Corollary 2.6] holds, which gives $\|g_{k}\|\rightarrow 0$ as $k\rightarrow\infty$, and so $\{\|g_{k}\|\}$, $k\geq 0$, is bounded above. The bound (2.5) now follows from (2.28).

Using the same techniques as in [16, Lemma 5.2] that applies when $f$ satisfies A.$1$, it is easy to show for the more general A.$\alpha$ case that $\sigma_{k}\leq c_{\sigma}\max(\sigma_{0},L_{H,\alpha})$ for all $k$, where $c_{\sigma}$ is a constant depending solely on $\alpha$ and algorithm parameters. It then follows from (2.25) that (2.11) holds and therefore that the $(2+\alpha)$-regularization method belongs to ${\cal M}.\alpha$ for $\alpha\in(0,1]$. $\Box$

We cannot extend this result to the $\alpha=0$ case unless we also assume that $H_{k}$ is positive semi-definite. If this is the case, further examination of the proof of [16, Lem.2.2] allows us to remove the first term in the max in (2.28), and the remainder of the proof is valid.

We note that bounding the regularization parameter $\sigma_{k}$ away from zero in (2.26) appears crucial when establishing the bounds (2.5) and (2.4). Requiring (2.26) implies that the Newton step is always perturbed, but does not prevent local quadratic convergence of ARC .

Goldfeld-Quandt-Trotter-type (GQT) methods . Let $\alpha\in(0,1]$. These algorithms set $M_{k}=\lambda_{k}I$, where

in (2.2), where $\omega_{k}>0$ is a parameter that is adjusted so as to ensure sufficient objective decrease. (Observe that replacing $\frac{\alpha}{1+\alpha}$ by $1$ in the exponent of $\|g_{k}\|$ in (2.29) recovers the original method of Goldfeld et al. .) It is straightforward to check that (2.3) holds for the choice (2.29). Thus the GQT approach takes the pure Newton step whenever the Hessian is locally sufficiently positive definite, and a suitable regularization of this step otherwise. The parameter $\omega_{k}$ is increased by a factor, say $\gamma_{1}>1$, and $x_{k+1}$ left as $x_{k}$ whenever the step $s_{k}$ does not give sufficient decrease in $f$ (i.e., iteration $k$ is unsuccessful), namely when

is the model (2.6) with $\beta_{k}=0$. If $\rho_{k}>\eta_{1}$, then $\omega_{k+1}\leq\omega_{k}$ and $x_{k+1}$ is constructed as in (2.1). Note that the choice (2.29) implies that (2.4) holds, provided $\omega_{k}$ is uniformly bounded above. We show that the latter, as well as (2.5), hold for functions in A.$\alpha$.

Lemma 2.6 Let $f$ satisfy A.$\alpha$ with $\alpha\in(0,1]$. Consider minimizing $f$ by applying a GQT method that sets $\lambda_{k}$ in (2.2) according to (2.29), measures progress according to (2.30), and chooses the parameter $\omega_{k}$ and the residual $r_{k}$ to satisfy, for $k\geq 0$, $\omega_{k}\geq\omega_{\min}\quad k\geq 0.\;\;\mbox{ and }\;\;r_{k}^{T}s_{k}\leq 0.$ (2.32) Then (2.5) and (2.4) hold, and so the GQT method belongs to ${\cal M}.\alpha$.

Note that the second part of (2.32) merely requires that $s_{k}$ is not longer that the line minimum of the regularized model along the direction $s_{k}$, that is $1\leq{\rm arg}\min_{\tau\geq 0}m_{k}(\tau s_{k})$.

Proof. Let us first show (2.5). Since $\omega_{k}>0$, and $g_{k}+r_{k}\neq 0$ until termination, the choice of $\lambda_{k}$ in (2.29) implies that $\lambda_{k}+\lambda_{\min}(H_{k})>0$, for all $k$, and so (2.2) provides

It follows from (2.29) and the first part of (2.32) that, for all $k\geq 0$,

As global convergence assumptions are satisfied when $f$ in A.$\alpha$ , we have $\|g_{k}\|\rightarrow 0$ as $k\rightarrow\infty$ (in fact, we only need the gradients $\{g_{k}\}$ to be bounded). Thus (2.36) implies (2.5).

Due to (2.29), (2.4) holds if we show that $\{\omega_{k}\}$ is uniformly bounded above. For this, we first need to estimate the model decrease. Taking the inner product of (2.2) with $s_{k}$, we obtain that

Substituting this into the model decrease, we deduce also from (2.6) with $\beta_{k}=0$ that

where we used the second part of (2.32) to obtain the last inequality. It is straightforward to check that this and (2.35) now imply

We show next that iteration $k$ is successful for $\omega_{k}$ sufficiently large. From (2.30) and second-order Taylor expansion of $f(x_{k}+s_{k})$, we deduce

where to obtain the last inequality, we used (2.36). Due to (2.30), iteration $k$ is successful when $|\rho_{k}-1|\leq 1-\eta_{1}$, which from (2.38) is guaranteed to hold whenever $\omega_{k}\geq\frac{L_{H,\alpha}}{\omega_{\min}^{\alpha}(1-\eta_{1})}$. As on each successful iteration we set $\omega_{k+1}\leq\omega_{k}$, it follows that

where the $\max$ term addresses the situation at the starting point and the $\gamma_{1}$ factor is included in case an iteration was unsuccessful and close to the bound. This concludes proving (2.4). $\Box$

Trust-region algorithms . These methods compute the correction $s_{k}$ as the global solution of the subproblem

where $\Delta_{k}$ is an evolving trust-region radius that is chosen to ensure sufficient decrease of $f$ at $x_{k}+s_{k}$. The resulting global minimizer satisfies (2.2)–(2.3) [34, Corollary 7.2.2] with $M_{k}=\lambda_{k}I$ (or $M_{k}=\lambda_{k}N_{k}$ if scaling is considered) and $r_{k}=0$. The scalar $\lambda_{k}$ is the Lagrange multiplier of the trust-region constraint, satisfies

and is such that $\lambda_{k}=0$ whenever $\|s_{k}\|<\Delta_{k}$ (and then, $s_{k}$ is the Newton step) or calculated using (2.2) to ensure that $\|s_{k}\|=\Delta_{k}$. The scalar $\beta_{k}=0$ in (2.6). The iterates are defined by (2.1) whenever sufficient progress can be made in some relative function decrease (so-called successful iterations), and they remain unchanged otherwise (unsuccessful iterations) while $\Delta_{k}$ is adjusted to improve the model (decreased on unsuccessful iterations, possibly increased on successful ones). The total number of unsuccessful iterations is bounded above by a constant multiple of the successful ones plus a (negligible) term in $\log\epsilon$ [53, page 23] provided $\Delta_{k}$ is not increased too fast on successful iterations. One successful iteration requires one gradient and one function evaluation while an unsuccessful one only evaluates the objective.

The property (2.5) of ${\cal M}.\alpha$ methods can be easily shown for trust-region methods, see Lemma 2.7. It is unclear however, whether conditions (2.4) or (2.11) can be guaranteed in general for functions in A.$\alpha$. The next lemma gives conditions ensuring a uniform upper bound on the multiplier $\lambda_{k}$, which still falls short of (2.4) in general.

Lemma 2.7 Let $f$ satisfy assumptions A.. Consider minimizing $f$ by applying a trust-region method as described in [34, Algorithm 6.1.1], where the trust-region subproblem is minimized globally to compute $s_{k}$ and where the trust-region radius is chosen to ensure that $\Delta_{k}\leq\Delta_{\max},\quad k\geq 0,$ (2.42) for some $\Delta_{\max}>0$. Then (2.5) holds. Additionally, if \|g_{k+1}\|\leq\|g_{k}\|,\;\;\mbox{for allksufficiently large,}\;\; (2.43) then $\lambda_{k}\leq\lambda_{\max}$ for all $k$ and some $\lambda_{\max}>0$, and $\lambda_{\min}(M_{k})$ is bounded.

Proof. Consider the basic trust-region algorithm as described in [34, Algorithm 6.1.1], using the same notation. Since the global minimizer $s_{k}$ of the trust-region subproblem is feasible with respect to the trust-region constraint, we have $\|s_{k}\|\leq\Delta_{k}$, and so (2.5) follows trivially from (2.42).

Clearly, the upper bound on $\lambda_{k}$ holds whenever $\lambda_{k}=0$ or $\lambda_{k}=-\lambda_{\min}(H_{k})\leq L_{g}$. Thus it is sufficient to consider the case when $\lambda_{k}>0$ and $H_{k}+\lambda_{k}I\succ 0$. The first condition implies that the trust-region constraint is active, namely $\|s_{k}\|=\Delta_{k}$ [34, Corollary 7.2.2]. The second condition together with (2.2) implies, as in the proof of Lemma 2.2, that (2.12) holds. Thus we deduce

By [34, Theorem 6.4.2], we have that there exists $c\in(0,1)$ such that the implication holds

(Observe that the Cauchy model decrease condition [34, Theorem 6.3.3] is sufficient to obtain the above implication.) Let $\gamma_{1}\in(0,1)$ denote the largest factor we allow $\Delta_{k}$ to be decreased by (during unsuccessful iterations). Using a similar argument to that of [34, Theorem 6.4.3], we let $k\geq k_{0}$ be the first iterate such that

where $k_{0}$ is the iteration from which onwards (2.43) holds. Then since $\Delta_{k+1}\geq\gamma_{1}\Delta_{k}$ and from (2.43) we have that $\Delta_{k}<c\|g_{k}\|$. This and (2.46) give

where to obtain the second and third inequalities, we used the hypothesis and (2.43), respectively. We have reached a contradiction with our assumption that $k+1$ is the first iteration greater than $k_{0}$ such that (2.47) holds. Hence there is no such $k$ and we deduce that

Note that since $g_{k}$ remains unchanged on unsuccessful iterations, (2.43) trivially holds on such iterations. Since the assumptions of [34, Theorem 6.4.6] are satisfied, we have that $\|g_{k}\|\rightarrow 0$, as $k\rightarrow\infty$. This and (2.48) imply (2.45). The desired conclusion then follows from (2.44). $\Box$

Note that if (2.19) holds for some $\alpha\in$, then (2.43) is satisfied, and so Lemma 2.7 shows that if (2.19) holds, then (2.18) is satisfied. It follows from Lemma 2.4 that fast convergence of trust-region methods for functions in A.$\alpha$ alone is sufficient to ensure (2.16), which in turn is connected to our definition of the class ${\cal M}.\alpha$. However, the properties of the multipliers (in the sense of (2.4) for any $\alpha\in$ or even (2.16)) remain unclear in the absence of fast convergence of the method. Based on our experience, we are inclined to believe that generally, the multipliers $\lambda_{k}$ are at best guaranteed to be uniformly bounded above, even for specialized, potentially computationally expensive, rules of choosing the trust-region radius.

As the Newton step is taken in the trust-region framework satisfying (2.2) whenever it is within the trust region and gives sufficient decrease in the presence of local convexity, the A.$1$- (hence A.$\alpha$-) example of inefficient behaviour for Newton’s method of worst-case evaluation complexity precisely $\epsilon^{-2}$ can be shown to apply also to trust-region methods (see also ).

Linesearch methods . We finally consider methods using a linesearch to control improvement in the objective at each step. Such methods compute $x_{k+1}=x_{k}+s_{k}$, $k\geq 0$, where $s_{k}$ is defined via (2.2) in which $M_{k}$ is chosen so that $H_{k}+M_{k}$, the Hessian of the selected quadratic model $m_{k}(s)$, is “sufficiently” positive definite, and $r_{k}=(1-\mu_{k})g_{k}$, yielding a stepsize $\mu_{k}\in[1-\kappa_{rg},1]$ which is calculated so as to decrease $f$ (the linesearch); this is always possible for sufficiently small $\mu_{k}$ (and hence sufficiently small $\kappa_{rg}$.) The precise definition of ”sufficient decrease” depends on the particular linesearch scheme being considered, but we assume here that

In other words, we require the unit step to be acceptable when the model and the true objective function match at the trial point. Because the minimization of the quadratic model along the step always ensure that $m_{k}(s_{k})=f(x_{k})+{\scriptstyle\frac{1}{2}}g_{k}s_{k}$, the above condition says that $s_{k}$ must be acceptable with $\mu_{k}=1$ whenever $f(x_{k}+s_{k})=f(x_{k})+{\scriptstyle\frac{1}{2}}g_{k}s_{k}$. This is for instance the case for the Armijo and Goldstein linesearch conditionsWith reasonable algorithmic constants, see Appendix A1., two standard linesearch techniques. As a consequence, the corresponding linesearch variants of Newton’s method and of the $(2+\alpha)$-regularization methods also belong to ${\cal M}.\alpha$ (with $\beta_{k}=1$ for all $k$), and the list is not exhaustive. Note that linesearch methods where the search direction is computed inexactly are also covered by setting $r_{k}=g_{k}-\mu_{k}(g_{k}+w_{k})$ for some “error vector” $w_{k}$, provided the second part of (2.2) still holds.

Examples of inefficient behaviour

After reviewing the methods in ${\cal M}.\alpha$, we now turn to showing they can converge slowly when applied to specific functions with fixed rangeAt variancewith the examples proposed in . and the relevant degree of smoothness.

Let $\alpha\in$ and $\epsilon\in(0,1)$ be given and consider an arbitrary method in ${\cal M}.\alpha$. Our intent is now to construct a univariate function $f^{{\cal M}.\alpha}_{\epsilon}(x)$ satisfying A.$\alpha$ such that

for some constants $a\leq b$ independent of $\epsilon$ and $\alpha$, and such that the method will terminate in exactly

iterations (and evaluations of $f$, $g$ and $H$).

We start by defining the sequences ${f_{k}}$, ${g_{k}}$ and ${H_{k}}$ for $k=0,\ldots,k_{\epsilon,\alpha}$ by

They are intended to specify the objective function, gradient and Hessian values at successive iterates generated by the chosen method in ${\cal M}.\alpha$, according to (2.1) and (2.2) for some choice of multipliers $\{\lambda_{k}\}=\{M_{k}\}=\{\lambda_{\min}(M_{k})\}$ satisfying (2.3) and (2.4). In other words, we impose that $f_{k}=f^{{\cal M}.\alpha}_{\epsilon}(x_{k})$, $g_{k}=\nabla f^{{\cal M}.\alpha}_{\epsilon}(x_{k})$ and $H_{k}=\nabla^{2}f^{{\cal M}.\alpha}_{\epsilon}(x_{k})$ for $k\in{\cal K}\stackrel{{\scriptstyle\rm def}}{{=}}\{0,\ldots,k_{\epsilon,\alpha}\}$. Note that ${f_{k}}$, ${|g_{k}|}$ and ${H_{k}}$ are monotonically decreasing and that, using (3.2),

In addition, (2.3) and (2.4) impose that, for $k\in{\cal K}$,

As a consequence, we obtain, using both parts of (2.2), that, for $k\in{\cal K}$,

where we have used (2.2), (3.3), (3.6), (3.5) and $\beta_{k}\leq 1$. Hence, again taking (3.3) into account,

and sufficient decrease of the objective function automatically follows. Moreover, given (3.4), we deduce from (3.6) that $|s_{k}|\leq 1$ for $k\in{\cal K}$ and (2.5) holds with $\kappa_{s}=1$, as requested for a method in ${\cal M}.\alpha$. It also follows from (2.1) and (3.6) that, if $x_{0}=0$,

We therefore conclude that the sequences $\{f_{k}\}_{k=0}^{k_{\epsilon,\alpha}}$, $\{g_{k}\}_{k=0}^{k_{\epsilon,\alpha}}$, $\{H_{k}\}_{k=0}^{k_{\epsilon,\alpha}}$, $\{\lambda_{k}\}_{k=0}^{k_{\epsilon,\alpha}-1}$ and $\{s_{k}\}_{k=0}^{k_{\epsilon,\alpha}-1}$ can be viewed as produced by our chosen method in ${\cal M}.\alpha$, and, from (3.3), that termination occurs precisely for $k=k_{\epsilon,\alpha}$, as desired.

We now construct the function $f^{{\cal M}.\alpha}_{\epsilon}(x)$ for $x\in[0,x_{k_{\epsilon,\alpha}}]$ using Hermite interpolation. We set

with coefficients defined by the interpolation conditions

where $s_{k}$ is defined in (3.6). These conditions yield the following values for the coefficients

with the remaining coefficients satisfying

Hence we obtain after elementary calculations that

The top three graphs of Figure 3.1 3.1 illustrate the global behaviour of the resulting function $f^{{\cal M}.\alpha}_{\epsilon}(x)$ and of its first and second derivatives for $x\in[0,x_{k_{\epsilon,\alpha}}]$, while the bottom ones show more detail of the first 10 iterations. The figure is constructed using $\epsilon=5.10^{-2}$ and $\alpha={\scriptstyle\frac{1}{2}}$, which then yields that $k_{\epsilon,\alpha}=148$. In addition, we set $\lambda_{k}={\scriptstyle\frac{1}{10}}|g_{k}|^{\frac{\alpha}{1+\alpha}}$ for $k=0,\ldots,k_{\epsilon,\alpha}$. The nonconvexity of $f^{{\cal M}.\alpha}_{\epsilon}(x)$ is clear from the bottom graphs.

Lemma 3.1 The function $f^{{\cal M}.\alpha}_{\epsilon}$ defined above on the interval $[0,x_{k_{\epsilon,\alpha}}]$ can be extended to a function from IR to IR satifying A.$\alpha$ and whose range is bounded independently of $\alpha$ and $\epsilon$.

$f^{{\cal M}.\alpha}_{\epsilon}$ is bounded in absolute value independently of $\epsilon$ and $\alpha$, twice continuously differentiable with Lipschitz continuous gradient and $\alpha$-Hölder continous Hessian. Recall first (3.10) provide that $f^{{\cal M}.\alpha}_{\epsilon}$ is twice continuously differentiable by construction on $[0,x_{k_{\epsilon,\alpha}}]$. It thus remains to investigate the gradient’s Lipschitz continuity and Hessian’s $\alpha-$Hölder continuity, as well as whether $|f^{{\cal M}.\alpha}_{\epsilon}(x)|$ is bounded on this interval.

(where we used (3.4) and (3.6)), we obtain from (3.2), (3.3), (3.6) and (3.13), that, for $k\in{\cal K}$,

where we also used $\epsilon\leq 1$ and (3.4). To show that the Hessian of $f^{{\cal M}.\alpha}_{\epsilon}$ is globally $\alpha-$Hölder continuous on $[0,x_{k_{\epsilon,\alpha}}]$, we need to verify that (2.8) holds for all $x,y$ in this interval. From (3.10), this is implied by

for some $c>0$ independent of $\epsilon$, $s$ and $k$. We have from the expression of $p_{k}$ and $s\in[0,s_{k}]$ that

The boundedness of this last right-hand side on $[0,x_{k_{\epsilon,\alpha}}]$ , and thus the $\alpha$-Hölder continuity of the Hessian of $f^{M}$, then follow from (3.15), (3.6) and (3.4).

Similarly, to show that the gradient of $f^{M}$ is globally Lipschitz continuous in $[0,x_{k_{\epsilon,\alpha}}]$ is equivalent to proving that $p_{k}^{{}^{\prime\prime}}(s)$ is uniformly bounded above on the interval $[0,s_{k}]$ for $k\in{\cal K}$. Since $s_{k}>0$, we have

Then the third part of (3.3) and the bounds $\epsilon\leq 1$, (3.15), (3.12), (3.6) and (3.4) again imply the boundedness of the last right-hand side on $[0,x_{k_{\epsilon,\alpha}}]$, as requested. Finally, the fact that $|f^{{\cal M}.\alpha}_{\epsilon}|$ is bounded on $[0,x_{k_{\epsilon,\alpha}}]$ results from the observation that, on the interval $[0,s_{k}]$ with $k\in{\cal K}$,

from which a finite bound $a$ independent from $\alpha$ and $\epsilon$ again follows from $\epsilon\leq 1$, (3.3), (3.10), (3.15), (3.12), (3.6) and (3.4). We have thus proved that $f^{{\cal M}.\alpha}_{\epsilon}$ satisfies the desired properties on $[0,x_{k_{\epsilon,\alpha}}]$.

We may then smoothly prolongate $f^{{\cal M}.\alpha}_{\epsilon}$ for $x\in\hbox{I\hskip-2.0ptR}$, for instance by defining two additional interpolation intervals $[x_{-1},x_{0}]=$ and $[x_{k_{\epsilon,\alpha}},x_{k_{\epsilon,\alpha}}+1]$ with end conditions

which subsumes (3.10). Using arguments similar to those used above, it is easy to verify from (3.12), (3.13) and $s_{-1}=s_{k_{\epsilon,\alpha}}=1$ that all desired properties are maintained. $\Box$

We formulate the results of this development in the following theorem.

Theorem 3.2 For every $\epsilon\in(0,1)$, every $\alpha\in$ and every method in ${\cal M}.\alpha$, a function $f^{{\cal M}.\alpha}_{\epsilon}$ satisfying A.$\alpha$ with values in a bounded interval independent of $\epsilon$ and $\alpha$ can be constructed, such, when applied to $f^{{\cal M}.\alpha}_{\epsilon}$, the considered method terminates exactly at iteration $k_{\epsilon,\alpha}=\left\lceil\epsilon^{-\frac{2+\alpha}{1+\alpha}}\right\rceil.$ with the first iterate $x_{k_{\epsilon,\alpha}}$ such that $\|\nabla_{x}f^{{\cal M}.\alpha}_{\epsilon}(x_{k_{\epsilon,\alpha}})\|\leq\epsilon$.

Note that the prolongation of $f^{{\cal M}.\alpha}_{\epsilon}(x)$ to $x\geq 0$ suggested as an example in the proof of Lemma 3.1 admits an isolated finite global minimizer. Indeed, since the $g_{k_{\epsilon,\alpha}}<0$, there must be a value lower than $f(x_{k_{\epsilon,\alpha}})$ in $(x_{k_{\epsilon,\alpha}},x_{k_{\epsilon,\alpha}}+1)$, and thus the global minimizer must lie in one of the constructed sub-intervals in $(-1,x_{k_{\epsilon,\alpha}+1})$; since $f^{{\cal M}.\alpha}_{\epsilon}(x)$ is quintic (and not constant) in each of these, the global minimizer must therefore be isolated.

2 The inexact Newton’s method

It is interesting that the technique developed in the previous subsection can also be used to derive an ${\cal O}\left(\epsilon^{-2}\right)$ lower bound on worst-case evaluation complexity for an inexact Newton’s method applied to a function having Lipschitz continuous Hessians on the path of iterates. This is stronger than using Theorem 3.2 above for $\alpha=1$, as it would result in a weaker ${\cal O}\left(\epsilon^{-3/2}\right)$ lower bound, or for $\alpha=0$ as it would then only guarantee bounded Hessians. In the spirit of , this new function is constructed by extending to $\hbox{I\hskip-2.0ptR}^{2}$ the unidimensional $f^{{\cal M}.0}_{\epsilon}(x)$ obtained in the previous section for the specific choice $M_{k}=0$, which then ensures that $\theta_{k}\in[1-\kappa_{rg},1+\kappa_{rg}]$ for all $k$ (see (3.5) and (3.6)). The proposed extension is of the form

where we still have to specify the univariate function $u_{\epsilon}$ such that Newton’s method applied to $u_{\epsilon}$ converges with large steps. In order to define it, we start by redefining

(Remember that $M_{k}=0$ because we are considering Newton’s method.) Note that sufficient decrease is obtained in manner similar to (3.7)-(3.8), because of (3.20), (3.21) and $\lambda_{k}=0$, yielding that $u_{k}-u_{k+1}\geq-(g_{k}^{u}s_{k}^{u}+{\scriptstyle\frac{1}{2}}H_{k}^{u}(s_{k}^{u})^{2})/(1+\kappa_{rg})$. Setting now $y_{0}=0$ and $y_{k+1}=y_{k}+s_{k}^{u}$ for $k\in\{1,\ldots,k_{\epsilon}\}$, we may then, as in Section 3.1, define

where $p^{u}_{k}$ is a fifth degree polynomial interpolating the values and derivatives given by (3.20) on the interval $[0,s_{k}^{u}]$. We then obtain the following result.

Theorem 3.3 For every $\epsilon\in(0,1)$, there exists a function $h^{N}_{\epsilon}$ with Lipschitz continuous gradient and Lipschitz continuous Hessian along the path of iterates $\cup_{k=0}^{k_{\epsilon}-1}[x_{j},x_{j+1}]$, and with values in a bounded interval independent of $\epsilon$, such that, when applied to $h^{N}_{\epsilon}$, Newton’s terminates exactly at iteration $k_{\epsilon}=\left\lceil\epsilon^{-2}\right\rceil$ with the first iterate $x_{k_{\epsilon}}$ such that $\|\nabla_{x}f^{{\cal M}.\alpha}_{\epsilon}(x_{k_{\epsilon}})\|\leq\epsilon\sqrt{1+\epsilon^{2}}$.

Proof. One easily verifies from (3.20), (3.21) and (3.13) that the interpolation coefficients, now denoted by $|d_{i,k}|$, are bounded for all $k\in\{0,\ldots,k_{\epsilon}-1\}$ and $i\in\{0,\ldots,5\}$. This observation and (3.21) in turn guarantee that $u_{\epsilon}$ and all its derivatives (including the third) remain bounded on each interval $[0,s_{k}^{u}]$ by constants independent of $\epsilon$. As in Lemma 3.1, we next extend $u_{\epsilon}$ to the whole of IR while preserving this property. We then construct $h^{N}$ using (3.19). From the properties of $f^{{\cal M}.0}_{\epsilon}$ and $u_{\epsilon}$, we deduce that $h^{N}_{\epsilon}$ is twice continuously differentiable and has a range bounded independently of $\epsilon$. Moreover, it satisfies A.0. When applied on $h^{N}_{\epsilon}(x,y)$, Newton’s generates the iterates $(x_{k},y_{k})$ and its gradient at the $k_{\epsilon}$-th iterate is $(\epsilon,\epsilon^{2})$ so that $\|\nabla h^{N}(x_{k_{\epsilon}},y_{k_{\epsilon}})\|=\epsilon\sqrt{1+\epsilon^{2}}$, prompting termination. Before that, the algorithm generates the steps $(s_{k},s_{k}^{u})$, where, because both $f_{k}$ and $u_{k}$ belong to $[{\scriptstyle\frac{1}{2}},1]$ and because of (3.6) with $\alpha=0$,

Thus the absolute value of the third derivative of $h^{N}_{\epsilon}(x,y)$ is given, for $(x,y)$ in the $k$-th segment of the path of iterates, by

where we used the fact that $\|(s_{k},s_{k}^{u})\|\geq\|s_{k}^{u}\|.$ and (3.23). But, in view of (3.15), (3.14) with $\theta_{k}\in[1-\kappa_{rg},1+\kappa_{rg}]$, (3.23), $\epsilon\leq 1$ and the boundedness of the $d_{i,k}$, the last right-hand side of (3.24) is bounded by a constant independent of $\epsilon$. Thus the third derivative of $h^{N}_{\epsilon}(x,y)$ is bounded on every segment by the same constant, and, as a consequence, the Hessian of $h^{N}_{\epsilon}(x,y)$ is Lipschitz continuous of each segment, as desired. $\Box$

Note that the same result also holds for any method in ${\cal M}.0$ with $M_{k}$ small enough to guarantee that $s_{k}$ is bounded away from zero for all $k$.

Complexity and optimality for methods in ℳ.αformulae-sequenceℳ𝛼{\cal M}.\alpha

We now consider the consequences of the examples derived in Section 3 on the evaluation complexity analysis of the various methods identified in Section 2 as belonging to ${\cal M}.\alpha$.

First note that the third part of (3.3) ensures that $H_{k}>0$ so that the Newton iteration is well-defined for the choice (2.23). This choice corresponds to setting $\theta_{k}=1$ for all $k\geq 0$ in the example of Section 3. So we first conclude from Theorem 3.2 that Newton’s method may require $\epsilon^{-(2+\alpha)/(1+\alpha)}$ evaluations when applied on the resulting objective function $f^{{\cal M}.\alpha}_{\epsilon}$ satisfying A.$\alpha$ to generate $|g_{k}|\leq\epsilon$. However, Theorem 3.3 provides the stronger result that it may in fact require $\epsilon^{-2}$ evaluations (as a method in ${\cal M}.0$) for nearly the same task (we traded Lipschitz continuity of the Hessian on the whole space for that along the path of iterates). As a consequence we obtain that Newton’s method is not optimal in ${\cal M}.\alpha$ as far as worst-case evaluation complexity is concerned.