Figure 7.1 ended with a dashed arrow: from the point \((10,1)\) on an ill-conditioned quadratic, where the gradient method needed over a hundred steps, one step of a different method reached the minimizer exactly. The gradient method builds its step from a model that assumes the same curvature \(L\) in every direction. What if the model used the actual curvature, direction by direction?

That is Newton’s method. It replaces the crude quadratic upper bound of the descent lemma by the true second-order Taylor expansion and jumps to the minimizer of that. Near a solution the result is spectacular: the number of correct digits doubles at every step. Far from a solution the same step can be useless or harmful, and each step costs a Hessian and a linear solve. This chapter proves the local convergence theorem with explicit constants, shows by example how the pure method fails globally and how damping repairs it, and then develops quasi-Newton methods, which recover most of the speed from gradient information alone.

8.1 The Newton step

Let \(f\) be twice continuously differentiable. Its second-order Taylor model at \(x\) is

If \(\nabla^2f(x)\succ 0\) , this is a strictly convex quadratic in \(d\) , and by Theorem 3.7(a) its unique minimizer solves \(\nabla^2f(x)\,d=-\nabla f(x)\) .

Setting the gradient of the model to zero is the same as linearising the equation \(\nabla f(x)=0\) and solving the linearisation. Newton’s method for minimization is therefore Newton’s method for root finding, familiar from numerical analysis (math.numerical-analysis.newton-fixed-point), applied to the gradient. That identification carries a warning: the method seeks stationary points, and by itself it does not distinguish minimizers from saddles or maximizers.

Affine invariance is the property the gradient method lacks. Exercise 7.14 showed that rescaling the variables can change the condition number of a problem from \(10\) to \(1\) , and with it the speed of the gradient method. Newton’s method is indifferent to such rescalings: it behaves on an elongated valley exactly as it does on a round bowl.

8.2 Local quadratic convergence

For a function that is not quadratic the model is only approximately right, and its error is governed by how fast the Hessian changes. The theorem below makes this precise. In its statement and proof, \(\lVert A\rVert\) for a matrix \(A\) denotes the operator norm, the largest value of \(\lVert Av\rVert\) over unit vectors \(v\) ; for a symmetric matrix it is the largest absolute value of an eigenvalue.

Squaring the error at each step is quadratic convergence. If \(\tfrac Mm\lVert x_k-x^\star\rVert=10^{-1}\) , then at the following steps the same quantity is at most \(10^{-2}\) , \(10^{-4}\) , \(10^{-8}\) : the number of correct digits roughly doubles each time. Compare linear convergence, where it grows by a fixed increment.

Notice what the constants say. The radius \(m/(2M)\) of guaranteed convergence is large when the curvature at the solution is strong and the Hessian varies slowly. The condition number \(L/m\) that dominated Chapter 7 does not appear at all. And the theorem is local: it says nothing about starting points outside the ball.

8.3 Far from the solution: damping

8.4 When the Hessian is not positive definite

Outside the convex setting the Hessian at an iterate may have negative eigenvalues. Then the quadratic model has no minimizer, the Newton step is at best a stationary point of the model, and it need not be a descent direction.

8.5 Quasi-Newton methods

Newton’s method needs the Hessian, which for a function of \(n\) variables has \(n(n+1)/2\) distinct entries and may be unavailable or expensive. Quasi-Newton methods build an approximation to it from the gradients the method computes anyway.

The idea is clearest in one variable. Between two iterates \(x_{k-1}\) and \(x_k\) , the average of \(f''\) is the difference quotient of \(f'\) . The secant method uses that quotient in place of \(f''(x_k)\) :

8.6 What each iteration costs

Rates of convergence count iterations. The price of an iteration differs enormously between methods, and a fair comparison multiplies the two.

The Newton system should be solved by factoring the Hessian, not by inverting it. For a symmetric positive definite matrix the Cholesky factorization of numerical analysis (math.numerical-analysis.linear-systems) costs about \(n^3/3\) arithmetic operations, roughly \(n^3/6\) multiplications and as many additions, and doubles as a test of positive definiteness, since it fails exactly when the matrix is not positive definite. When the Hessian is sparse or structured the cost can be far below \(n^3\) , and this, more than anything, determines whether Newton’s method is practical for a given large problem. The limited-memory variant of BFGS keeps only the last \(j\) pairs \((s,y)\) , typically between five and twenty, and applies the update formula implicitly; it is the standard choice when \(n\) is in the millions.

Example 8.8: Three methods on one function

Let \(f(x)=\tfrac12(x_1^2+10x_2^2)+\log(1+e^{x_1+x_2})\) . The quadratic part has Hessian eigenvalues \(1\) and \(10\) , and the logarithmic term, by Exercise 2.14, adds a positive semidefinite matrix with largest eigenvalue at most \(\tfrac14\cdot2=\tfrac12\) . So at every point the Hessian eigenvalues lie between \(1\) and \(10.5\) : \(f\) is strongly convex with \(m\ge1\) and smooth with \(L\le10.5\) . Its minimizer, computed to machine precision, is \(x^\star\approx(-0.3935,-0.0393)\) .

From \(x_0=(3,-1)\) the distance to the minimizer is \(3.53\) . The pure Newton method gives the distances

\[ 2.1\times10^{-1},\qquad1.4\times10^{-3},\qquad4.6\times10^{-8} \]

after one, two, and three steps. The ratios of each distance to the square of the one before are about \(0.031\) and \(0.024\) , so a fourth step should give about \(0.024\cdot(4.6\times10^{-8})^2\approx5\times10^{-17}\) ; a computation in extended precision confirms \(5.1\times10^{-17}\) , which is below the resolution of ordinary double-precision arithmetic, where the fourth iterate is simply correct to the last digit. The gradient method with \(\alpha=1/L=1/10.5\) gives \(1.00\) after \(10\) steps, \(0.285\) after \(20\) , and \(0.023\) after \(40\) , a reduction by a factor of about \(0.88\) per step, consistent with the bound \(\sqrt{1-m/L}\approx0.95\) of Theorem 7.7 and with the actual curvature at the solution.

Figure 8.1 is the picture to remember when choosing among these methods. If iterations are cheap and moderate accuracy suffices, the straight line is acceptable. If high accuracy is needed or the problem is badly conditioned, the curved lines win by orders of magnitude, provided the cost per iteration in the table above can be afforded.

All three methods assume that the iterate may move freely. The next chapter puts back the constraints and the nondifferentiable terms, and shows how the gradient step can be adapted to both with one new operation.

Exercises

1. Compute the Newton step for \(f(x)=x_1^2+x_1x_2+x_2^2-3x_1\) at the point \((0,0)\) by solving the linear system of Definition 8.1 without forming an inverse, and verify that the step lands on the minimizer found in Example 3.4.

   Answer

   At \((0,0)\) the gradient is \((-3,0)\) and the Hessian is \(\begin{pmatrix}2&1\\1&2\end{pmatrix}\) . The system \(2d_1+d_2=3\) , \(d_1+2d_2=0\) gives \(d_2=-1\) , \(d_1=2\) , so \(x+d_{\mathrm N}=(2,-1)\) , the minimizer of Example 3.4. The function is quadratic, so one step suffices (Proposition 8.2(c)).

2. For \(f(x)=x-\log x\) on \(x>0\) derive the Newton iteration, show that the error \(e_k=1-x_k\) satisfies \(e_{k+1}=e_k^2\) exactly, compute four iterates from \(x_0=0.5\) , and determine the set of starting points from which the pure iteration converges.

   Solution

   Here \(f'(x)=1-1/x\) and \(f''(x)=1/x^2>0\) , so \(f\) is strictly convex on \(x>0\) with minimizer \(x^\star=1\) . The Newton step is \(-f'(x)/f''(x)=-(1-1/x)x^2=x-x^2\) , so

   \[ x_{k+1}=x_k+x_k-x_k^2=2x_k-x_k^2 . \]

   For the error \(e_k=1-x_k\) : \(e_{k+1}=1-2x_k+x_k^2=(1-x_k)^2=e_k^2\) . The error is squared exactly at every step, with constant \(1\) .

   From \(x_0=0.5\) , \(e_0=0.5\) , so the errors are \(0.25\) , \(0.0625\) , \(0.00390625\) , \(1.526\times10^{-5}\) and the iterates are

   \[ x_1=0.75,\qquad x_2=0.9375,\qquad x_3=0.99609375,\qquad x_4\approx0.99998474 . \]

   Since \(e_k=e_0^{2^k}\) , the iteration converges if and only if \(\lvert e_0\rvert<1\) , that is, \(0<x_0<2\) . This also keeps the iterates in the domain: \(x_{k+1}=x_k(2-x_k)\) is positive exactly when \(0<x_k<2\) . At \(x_0=2\) the first step lands on \(0\) , outside the domain, and for \(x_0>2\) it lands on a negative number. So the basin of the pure method is the interval \((0,2)\) ; a line search that also rejects points outside the domain would extend convergence to every positive start.

3. Prove that the Newton decrement satisfies \(\tfrac12\lambda(x)^2=f(x)-\min_dq_x(d)\) , and evaluate \(\lambda(x)^2\) for \(f(x)=\tfrac12(x_1^2+4x_2^2)\) at \(x=(4,1)\) , comparing \(\tfrac12\lambda(x)^2\) with \(f(x)-f^\star\) .

   Solution

   Write \(g=\nabla f(x)\) and \(H=\nabla^2f(x)\succ 0\) . The model \(q_x(d)=f(x)+g^{\top}d+\tfrac12d^{\top}Hd\) is a strictly convex quadratic in \(d\) , minimized by Theorem 3.7(a) at \(d=-H^{-1}g\) . Its minimum value is

   \[ f(x)-g^{\top}H^{-1}g+\tfrac12g^{\top}H^{-1}HH^{-1}g=f(x)-\tfrac12g^{\top}H^{-1}g=f(x)-\tfrac12\lambda(x)^2 . \]

   So \(f(x)-\min_dq_x(d)=\tfrac12\lambda(x)^2\) .

   For \(f(x)=\tfrac12(x_1^2+4x_2^2)\) at \((4,1)\) : \(g=(4,4)\) and \(H\) is diagonal with entries \(1\) and \(4\) , so \(\lambda^2=16/1+16/4=20\) and \(\tfrac12\lambda^2=10\) . The true gap is \(f(4,1)-f^\star=8+2-0=10\) . They agree exactly because \(f\) is quadratic and the model is \(f\) itself. For a general function \(\tfrac12\lambda(x)^2\) is an estimate of \(f(x)-f^\star\) that becomes accurate near the minimizer, which is why \(\lambda(x)^2\le2\varepsilon\) is a natural stopping test for Newton’s method; unlike the gradient norm, it is unchanged by a linear change of variables.

4. Show that the pure Newton iteration for \(f(x)=x^6\) is \(x_{k+1}=\tfrac45x_k\) , state the kind of convergence this is, and identify the hypothesis of Theorem 8.3 that fails.

   Answer

   \(f'=6x^5\) and \(f''=30x^4\) , so \(x_{k+1}=x_k-x_k/5=\tfrac45x_k\) : linear convergence with factor \(0.8\) . The hypothesis \(m>0\) fails, since \(f''(0)=0\) .

5. For \(f(x)=\log(e^{x}+e^{-x})\) show that the pure Newton iteration is \(x_{k+1}=x_k-\tfrac12\sinh(2x_k)\) , and that it converges exactly when \(\lvert x_0\rvert<x_c\) , where \(x_c\approx1.0887\) is the positive solution of \(\sinh(2x)=4x\) .

   Solution

   With \(f(x)=\log(e^{x}+e^{-x})\) we get \(f'(x)=\tanh x\) and \(f''(x)=1/\cosh^2x\) . The Newton step is \(-\tanh x\cosh^2x=-\sinh x\cosh x=-\tfrac12\sinh(2x)\) , so \(x_{k+1}=\phi(x_k)\) with \(\phi(x)=x-\tfrac12\sinh(2x)\) .

   The map \(\phi\) is odd, and for \(x>0\) it satisfies \(\phi(x)<x\) , because \(\sinh(2x)>0\) , and in fact \(\phi(x)<0\) , because \(\sinh(2x)>2x\) . So the iterates alternate in sign and \(\lvert x_{k+1}\rvert=\tfrac12\sinh(2\lvert x_k\rvert)-\lvert x_k\rvert\) . Hence \(\lvert x_{k+1}\rvert<\lvert x_k\rvert\) exactly when \(\sinh(2\lvert x_k\rvert)<4\lvert x_k\rvert\) . The function \(\sinh(2x)-4x\) is negative for small positive \(x\) (its derivative at \(0\) is \(-2\) ), is convex for \(x>0\) , and tends to infinity, so it has exactly one positive zero \(x_c\) ; numerically \(x_c\approx1.0887\) .

   If \(\lvert x_0\rvert<x_c\) , the absolute values decrease and stay below \(x_c\) ; a decreasing sequence of nonnegative numbers has a limit \(a\) , which by continuity satisfies \(a=\tfrac12\sinh(2a)-a\) , and the only solution in \([0,x_c)\) is \(a=0\) . So the method converges. If \(\lvert x_0\rvert=x_c\) the iterates cycle between \(x_c\) and \(-x_c\) . If \(\lvert x_0\rvert>x_c\) the absolute values increase, and since there is no fixed value above \(x_c\) they diverge. The function is smooth and strictly convex, and still the pure method has a bounded basin.

6. For \(f(x)=e^{x}-2x\) at \(x_0=-3\) compute the Newton step, show that the full step increases \(f\) enormously, and carry out backtracking with \(c=0.25\) and \(\beta=0.5\) to find the accepted step size and the new point.

   Solution

   At \(x_0=-3\) : \(f'(x_0)=e^{-3}-2\approx-1.9502\) , \(f''(x_0)=e^{-3}\approx0.0498\) , and \(f(x_0)=e^{-3}+6\approx6.0498\) . The Newton step is \(d=-f'/f''\approx39.171\) . The curvature is tiny, so the model is very flat and its minimizer is far away.

   The full step lands on \(x\approx36.17\) , where \(f\approx5\times10^{15}\) . The backtracking test is \(f(x_0+td)\le f(x_0)+0.25\,t\,f'(x_0)d\approx6.0498-19.098\,t\) .

   \(t=1\) : \(f\approx5\times10^{15}\) , required \(\le-13.05\) . Fail. \(t=0.5\) : the point is \(16.59\) , \(f\approx1.6\times10^{7}\) , required \(\le-3.50\) . Fail. \(t=0.25\) : the point is \(6.79\) , \(f\approx877.8\) , required \(\le1.28\) . Fail. \(t=0.125\) : the point is \(1.896\) , \(f\approx2.869\) , required \(\le3.663\) . Pass.

   The accepted step size is \(t=0.125\) and the new point is \(x_1\approx1.896\) . From there the pure iteration \(x-1+2e^{-x}\) gives \(1.197\) , \(0.801\) , \(0.699\) , and then converges quadratically to \(\log2\) as in Example 8.2. Three failed trials cost three function evaluations, far less than the damage the full step would have done.

7. For \(f(x)=x^3-3x\) at \(x=-0.5\) compute the Newton step and show that it moves toward the local maximizer \(x=-1\) ; explain this in terms of the sign of \(f''\) and the nature of the quadratic model.

   Answer

   \(f'(-0.5)=-2.25\) and \(f''(-0.5)=-3\) , so the step is \(-f'/f''=-0.75\) and the new point is \(-1.25\) , on the far side of the local maximizer \(-1\) , to which the iteration then converges. With \(f''<0\) the quadratic model is a downward parabola; its only stationary point is its maximum, and that is where the Newton step goes.

8. Explain why Newton’s method for minimizing \(f\) coincides with Newton’s root-finding method applied to \(\nabla f\) , and why this means the iteration can converge to a saddle point; illustrate by running three steps on \(f(x,y)=x^3-3x+y^2\) from \((-0.9,\,0.2)\) .

   Hint

   The Newton step solves the linearisation of \(\nabla f(x)=0\) , and the equation \(\nabla f=0\) does not know which kind of stationary point it describes. Here the variables decouple: \(x^+=(x^2+1)/(2x)\) and \(y^+=0\) . From \((-0.9,0.2)\) the iterates are \((-1.00556,0)\) , \((-1.0000154,0)\) , and then \((-1,0)\) to ten digits: the saddle of Example 3.1.

9. For \(f(x)=e^{x}-2x\) and the ball of radius \(r=0.2\) about \(x^\star=\log2\) , compute \(m\) and a valid Lipschitz constant \(M\) , check that \(m/(2M)\ge r\) , and verify the inequality of Theorem 8.3 for the Newton step taken from \(x=x^\star+0.2\) .

   Solution

   Here \(m=f''(x^\star)=e^{\log2}=2\) . On the ball \([x^\star-0.2,\ x^\star+0.2]\) , the Hessian \(f''(x)=e^{x}\) has derivative \(e^{x}\le e^{\log2+0.2}=2e^{0.2}\approx2.443\) , so by the mean value theorem \(\lvert f''(x)-f''(y)\rvert\le2.443\,\lvert x-y\rvert\) there. Take \(M=2.443\) . Then \(m/(2M)\approx0.409\ge0.2=r\) , so the theorem applies to every starting point in the ball.

   Take \(x=x^\star+0.2\approx0.89315\) , with error \(e=0.2\) . Since \(e^{-x}=\tfrac12e^{-0.2}\approx0.40937\) , the Newton iterate is

   \[ x^+=x-1+2e^{-x}\approx0.89315-1+0.81873=0.71188, \]

   with error \(\lvert x^+-x^\star\rvert\approx0.01873\) . The theorem’s bound is \(\tfrac Mm e^2=1.2214\cdot0.04\approx0.0489\) . Indeed \(0.01873\le0.0489\) , and also \(0.01873\le\tfrac12\cdot0.2\) . The observed ratio \(0.01873/0.04\approx0.47\) is close to the asymptotic constant \(\tfrac12\) of Example 8.2 and well inside the guaranteed constant, which had to allow for the worst behaviour of the Hessian anywhere in the ball.

10. Apply the secant method of Section 8.5 to \(f(x)=x-\log x\) starting from \(x_0=0.5\) and \(x_1=0.75\) , computing \(x_2\) and \(x_3\) , and compare the errors with those of the Newton iteration in Exercise 2.

    Answer

    With \(f'(x)=1-1/x\) : \(f'(0.5)=-1\) , \(f'(0.75)=-\tfrac13\) , \(b_1=(\tfrac23)/0.25=\tfrac83\) , so \(x_2=0.75+\tfrac13\cdot\tfrac38=0.875\) . Then \(f'(0.875)=-\tfrac17\) , \(b_2=(\tfrac13-\tfrac17)/0.125=\tfrac{32}{21}\) , and \(x_3=0.875+\tfrac17\cdot\tfrac{21}{32}=0.96875\) . The errors \(0.125\) and \(0.03125\) are each the product of the two preceding errors; Newton from \(0.75\) gives errors \(0.0625\) and \(0.0039\) .

11. For \(H=I\) , \(s=(1,0)\) , and \(y=(2,1)\) , compute the BFGS update \(H^+\) from Definition 8.6 and verify by direct calculation that it is symmetric, satisfies \(H^+y=s\) , and is positive definite.

    Solution

    Here \(y^{\top}s=2\cdot1+1\cdot0=2>0\) , so \(\rho=\tfrac12\) . Compute the two factors:

    \[ I-\rho\,sy^{\top}=\begin{pmatrix}1&0\\0&1\end{pmatrix}-\tfrac12\begin{pmatrix}2&1\\0&0\end{pmatrix}=\begin{pmatrix}0&-\tfrac12\\0&1\end{pmatrix},\qquad I-\rho\,ys^{\top}=\begin{pmatrix}0&0\\-\tfrac12&1\end{pmatrix}. \]

    With \(H=I\) the first term of the update is their product, \(\begin{pmatrix}\tfrac14&-\tfrac12\\-\tfrac12&1\end{pmatrix}\) , and the second term is \(\rho\,ss^{\top}=\begin{pmatrix}\tfrac12&0\\0&0\end{pmatrix}\) . Therefore

    \[ H^+=\begin{pmatrix}\tfrac34&-\tfrac12\\-\tfrac12&1\end{pmatrix}. \]

    It is symmetric. Secant equation: \(H^+y=(\tfrac34\cdot2-\tfrac12\cdot1,\ -\tfrac12\cdot2+1\cdot1)=(1,0)=s\) . Positive definiteness: the trace is \(\tfrac74>0\) and the determinant is \(\tfrac34-\tfrac14=\tfrac12>0\) , so both eigenvalues are positive. All three conclusions of Proposition 8.7 are confirmed. The update has reduced the first diagonal entry from \(1\) to \(\tfrac34\) : the gradient changed by \(2\) units along a step of \(1\) unit in the first coordinate, indicating curvature larger than \(1\) there, so the inverse-curvature estimate goes down.

12. Let \(f\) be differentiable and \(m\) -strongly convex. Prove that \((\nabla f(x)-\nabla f(z))^{\top}(x-z)\ge m\lVert x-z\rVert^2\) for all \(x,z\) , and deduce that the curvature condition \(y^{\top}s>0\) of Definition 8.6 holds for every nonzero step.

    Solution

    By Proposition 2.9, for all \(x,z\) ,

    \[ f(z)\ge f(x)+\nabla f(x)^{\top}(z-x)+\frac m2\lVert z-x\rVert^2,\qquad f(x)\ge f(z)+\nabla f(z)^{\top}(x-z)+\frac m2\lVert x-z\rVert^2 . \]

    Add the two inequalities. The function values cancel, leaving

    \[ 0\ge\nabla f(x)^{\top}(z-x)+\nabla f(z)^{\top}(x-z)+m\lVert x-z\rVert^2=-(\nabla f(x)-\nabla f(z))^{\top}(x-z)+m\lVert x-z\rVert^2, \]

    which is the claim. Now take \(x=x_{k+1}\) and \(z=x_k\) , so that \(x-z=s_k\) and \(\nabla f(x)-\nabla f(z)=y_k\) . The inequality reads \(y_k^{\top}s_k\ge m\lVert s_k\rVert^2\) , which is positive whenever \(s_k\ne 0\) . So on a strongly convex function every BFGS update is well defined and, by Proposition 8.7, preserves positive definiteness, whatever line search is used. The inequality proved here says that the gradient of a strongly convex function is strongly monotone; it is the multivariable version of the statement that \(f'\) increases at rate at least \(m\) .

13. A program computes each Newton step for a dense problem with \(n=5000\) variables as the product of an explicitly computed inverse Hessian with the gradient. Explain what is wasteful and what is risky about this, and say what should be computed instead.

    Hint

    Inverting costs about three times as much as a Cholesky factorization and yields a matrix that is then used only once, in a product with one vector; it also amplifies rounding errors more than triangular solves do. Factor the Hessian and solve two triangular systems. If the factorization breaks down, the Hessian was not positive definite, which is itself information the algorithm needs.

14. A dense strongly convex quadratic-like problem has \(n=1000\) variables. One gradient iteration costs about \(n^2\) operations and one Newton iteration about \(n^3/3\) . Estimate the total work for each method to reduce the error by a factor \(10^{-6}\) when \(\kappa=10^4\) and when \(\kappa=10\) , assuming Newton needs \(6\) iterations, and say which method is preferable in each case.

    Solution

    Use the estimate after Theorem 7.7: the squared error contracts by \(1-1/\kappa\) per gradient step, so reducing the error by \(10^{-6}\) , that is, the squared error by \(10^{-12}\) , takes about \(\kappa\log(10^{12})\approx27.6\,\kappa\) iterations.

    For \(\kappa=10^4\) : about \(2.8\times10^{5}\) gradient iterations at \(n^2=10^6\) operations each, a total near \(2.8\times10^{11}\) . Newton: \(6\) iterations at \(n^3/3\approx3.3\times10^{8}\) each, a total near \(2\times10^{9}\) . Newton is cheaper by a factor of more than \(100\) .

    For \(\kappa=10\) : about \(276\) gradient iterations, a total near \(2.8\times10^{8}\) , against the same \(2\times10^{9}\) for Newton. The gradient method is cheaper by a factor of about \(7\) .

    The break-even is at \(\kappa\) near \(70\) for this problem size. The comparison omits the cost of forming the Hessian, which for a dense problem is of the same order as factoring it, and it assumes dense linear algebra; sparsity can make the Newton step far cheaper. The conclusion that survives such refinements is qualitative: the worse the conditioning and the higher the accuracy required, the stronger the case for second-order information, and quasi-Newton methods occupy the middle ground at \(n^2\) per iteration with no Hessian.

15. Theorem 8.3 assumes that \(\nabla^2f(x^\star)\) is positive definite. Use Theorem 3.4 to say what this implies about \(x^\star\) , and explain why observing that a Newton iteration has converged does not by itself show that the limit is a minimizer.

    Hint

    By Theorem 3.4 a stationary point with positive definite Hessian is a strict local minimizer, so the theorem’s hypotheses already guarantee what the limit is. Without that hypothesis the iteration is root finding on \(\nabla f\) , and Exercise 8.8 shows it converging to a saddle. Check the Hessian at the limit, or use a method that enforces decrease of \(f\) .

16. Let \(H\) be symmetric with smallest eigenvalue \(\mu\) , possibly negative, and let \(g\ne 0\) . Prove that for every \(\tau>-\mu\) the direction \(d=-(H+\tau I)^{-1}g\) satisfies \(g^{\top}d<0\) , and show that \(\tau d\to-g\) as \(\tau\to\infty\) .

    Solution

    Let \(\mu\) be the smallest eigenvalue of \(H\) and \(\tau>-\mu\) . The eigenvalues of \(H+\tau I\) are those of \(H\) shifted by \(\tau\) , so the smallest is \(\mu+\tau>0\) and \(H+\tau I\) is positive definite. The inverse of a positive definite matrix is positive definite, since its eigenvalues are the reciprocals. Therefore

    \[ g^{\top}d=-g^{\top}(H+\tau I)^{-1}g<0\qquad\text{for }g\ne 0 . \]

    For the limit, factor out \(\tau\) : \(\tau d=-\tau(H+\tau I)^{-1}g=-\bigl(\tfrac1\tau H+I\bigr)^{-1}g\) . As \(\tau\to\infty\) the matrix \(\tfrac1\tau H+I\) tends to \(I\) , and matrix inversion is continuous at \(I\) , so \(\tau d\to-g\) . In words: for large \(\tau\) the modified direction is approximately \(-g/\tau\) , a short step along the negative gradient. For \(\tau\) just large enough to restore definiteness, it stays close to the Newton direction in the subspace where the curvature was already positive. The parameter \(\tau\) thus trades trust in the quadratic model against the safety of steepest descent, which is the idea behind trust-region methods.

17. Show that one pure Newton step for the least-squares objective \(\lVert Ax-b\rVert^2\) , with the columns of \(A\) independent, leads from any starting point to the solution of the normal equations, and relate this to Proposition 8.2(c).

    Hint

    The objective is the quadratic with \(P=2A^{\top}A\succ 0\) and \(q=-2A^{\top}b\) , so Proposition 8.2(c) applies: \(x+d_{\mathrm N}=-P^{-1}q=(A^{\top}A)^{-1}A^{\top}b\) .

18. Three algorithms report the error sequences (a) \(10^{-1},10^{-2},10^{-3},10^{-4}\) ; (b) \(10^{-1},10^{-2},10^{-4},10^{-8}\) ; (c) \(10^{-1},5\times10^{-2},3.3\times10^{-2},2.5\times10^{-2}\) . Classify each as sublinear, linear, or quadratic, and for each estimate the error after two more iterations.

    Answer

    (a) Linear with factor \(0.1\) ; next errors \(10^{-5}\) , \(10^{-6}\) . (b) Quadratic with \(e_{k+1}=e_k^2\) ; next errors \(10^{-16}\) , \(10^{-32}\) . (c) Sublinear, \(e_k\approx0.1/k\) ; next errors about \(2\times10^{-2}\) and \(1.7\times10^{-2}\) .

19. Apply the backtracking Newton iteration to \(f(x)=\tfrac12x^2\) from \(x_0=1\) with the inadmissible parameter \(c=0.75\) and with \(\beta=0.5\) : show that the step \(t=1\) is rejected and \(t=0.5\) accepted at every iteration, give the resulting rate of convergence, and explain why Definition 8.4 requires \(c<\tfrac12\) by finding the largest \(c\) for which the unit step is accepted on this function.

    Solution

    For \(f(x)=\tfrac12x^2\) the gradient is \(x\) and the Hessian is \(1\) , so the Newton step is \(d=-x\) and the decrement is \(\lambda(x)^2=x^2\) . A trial step \(t\) leads to \((1-t)x\) , and the sufficient-decrease test \(f(x+td)\le f(x)-c\,t\,\lambda(x)^2\) reads

    \[ \tfrac12(1-t)^2x^2\le\tfrac12x^2-c\,t\,x^2 . \]

    For \(x\ne0\) , divide by \(x^2\) and expand: \(t^2-2t\le-2ct\) , that is, \(t\le2(1-c)\) . The test does not depend on \(x\) , so the same trials succeed and fail at every iteration.

    With \(c=0.75\) the test is \(t\le0.5\) . The trial \(t=1\) fails; the next trial \(t=0.5\) passes, with equality. So every iteration takes \(t=0.5\) and \(x_{k+1}=\tfrac12x_k\) : from \(x_0=1\) the iterates are \(0.5\) , \(0.25\) , \(0.125\) , and the convergence is linear with factor \(\tfrac12\) , although the function is quadratic and a single full step would have reached the minimizer.

    The unit step passes the test exactly when \(1\le2(1-c)\) , that is, when \(c\le\tfrac12\) . So \(\tfrac12\) is the largest admissible value on this function, and it is admissible here only because the quadratic model is exact, the full step decreasing \(f\) by exactly \(\tfrac12\lambda^2\) . For a general function the decrease achieved by a full step near the solution is \(\tfrac12\lambda^2\) up to a relative error that tends to zero but can have either sign, so the unit step is guaranteed to pass eventually only if \(c\) is strictly less than \(\tfrac12\) . That is the restriction in Definition 8.4, and it is a hypothesis of Theorem 8.5.