Newton's method in optimization

Newton's method for minimizing a twice differentiable function uses

The linear system defining one step of Newton's method for $F(x)=0$ is the displayed first-order correction equation. A nonsingular Jacobian matrix gives a unique Newton correction. For an unconstrained stationary-point problem $F=\nabla f$, the system uses the Hessian matrix in place of $DF$.

The correction is the vector obtained by solving the Newton system, added to the current point to give $x_{\mathrm{new}}=x+\delta$. The inverse notation specifies the solution; a numerical implementation normally solves a linear system rather than forming a matrix inverse.

For the Euclidean norm on ${\mathbb{R}}^d$, the regularized radial function $f(z)=\sqrt{1+\Vert z{\Vert }^2}$ has gradient $z/f$ and Hessian $I/f-z{z}^T/f^3$. The Cauchy-Schwarz inequality makes its Hessian a positive-definite matrix, so $f$ is strictly convex with unique minimum at zero. Its inverse matrix is $f(I+z{z}^T)$: multiplication verifies this using $(z{z}^T{)}^2=\Vert z{\Vert }^{2}z{z}^T$ and $f^2=1+\Vert z{\Vert }^2$. Substitution in Newton's method in optimization therefore gives $z_{k+1}=-\Vert z_k{\Vert }^2{z}_k$. Consequently $\Vert z_{k+1}\Vert =\Vert z_k{\Vert }^3$: nonzero starts in the open unit ball have exact cubic convergence, starts on the unit sphere alternate between opposite points, and starts outside it diverge. This example separates strict convexity from global convergence of an undamped iteration.

For $f(x,y)=x^4-4xy+2y^2+4$, the Newton step equations imply $y_{n+1}=x_{n+1}$. Solving the remaining equation gives the displayed scalar recurrence, defined when $3x_n^2\ne 1$. Around $(1,1)$ its error factors exactly asThus any well-defined sequence converging to $(1,1)$ has quadratic convergence, or reaches that point exactly in finitely many steps. The scalar asymptotic error constant is $3/2$; the Euclidean norm error constant on the diagonal is $3/(2\sqrt{2})$. Around $(-1,-1)$, replacing $x$ by $-x$ gives the corresponding conclusion.

A Newton step for Newton's method in optimization is the displacement $s$ solving the displayed linear system, where $H$ is the Hessian matrix and $\nabla f$ the gradient. The next iterate is $p+s$. This makes the first order Taylor expansion of the gradient at the new point vanish. An invertible Hessian matrix determines a unique step; it need not give a descent direction when the Hessian matrix is indefinite.

For a real symmetric invertible matrix $H$, the full undamped Newton step for the displayed quadratic function sends every starting point to the unique stationary point:This follows because the gradient is affine and its first-order expansion is exact. If $H$ is a positive-definite matrix the result is the unique global minimum; a negative-definite matrix gives a global maximum, and an indefinite matrix $H$ gives a saddle point. Thus exact arrival does not by itself show that a minimization method has minimized anything. A line search, damping, or a positive-definite matrix replacing the Hessian matrix changes this exact one-step assertion.

For a twice continuously differentiable real function, the Newton map sends an input $p$ to the next iterate of Newton's method in optimization. It is defined where the Hessian matrix $H(p)$ is invertible. Iterating this map seeks a zero of a function of the gradient; additional information is needed to determine whether a resulting stationary point is a local minimum.

For a twice continuously differentiable real function, define the Newton map in optimization $N(p)=p-H(p{)}^{-1}\nabla f(p)$ wherever its Hessian matrix $H$ is invertible. Every stationary point in this domain is a fixed point, because its gradient is zero. This includes a local maximum and a saddle point of a scalar function, as well as a local minimum. Thus Newton's method in optimization needs a separate minimum classification or a method for ensuring descent when it is used for minimization problem.

For example, $f(x,y)=(x+y^2{)}^2+(x^2+y{)}^2$ has a stationary point at $(-1/2,-1/2)$, with Hessian matrixIts eigenvalues are $-1$ and $7$, so it is a saddle point of a scalar function, but starting Newton's method in optimization there gives a constant sequence. Its value is $1/8$, whereas the global minimum zero is attained at $(0,0)$ and $(-1,-1)$.

For $c>0$ and $a_0>0$, the displayed recurrence relation stays positive and satisfiesAfter the first step, $a_n^2\ge c$, so $a_{n+1}-a_n=(c-a_n^2)/(2a_n)\le 0$. The bounded monotone sequence theorem gives a limit of a sequence $L\ge 0$; the inequality $L^2\ge c>0$ makes $L$ positive, and passage to the limit of a sequence in the recurrence relation gives $L^2=c$. This proves existence of the positive square root without assuming it in the construction. Once $s=\sqrt{c}$ is known, the exact error identity $a_{n+1}-s=(a_n-s{)}^2/(2a_n)$ explains the eventual quadratic convergence.

Let $c=-d<0$ and suppose the recurrence relation $a_{n+1}=(a_n-d/a_n)/2$ is defined with no zero iterates. An eventually constant sign would make $b_n=|a_n|$ satisfy $0<b_{n+1}=(b_n-d/b_n)/2<b_n/2$ on a tail. Thus $b_n\to 0$, although positivity of $b_{n+1}$ requires $b_n^2>d$ throughout that tail. This contradiction proves infinitely many sign changes. The nonzero assumption matters because a zero iterate makes the next step undefined.

If ${\nabla }^{2}f⪰mI$ and the Hessian is $M$-Lipschitz near a minimizer $x^{\ast }$, thenThus a sufficiently close initial point has an error exponent that doubles at each iteration.

A Quasi-Newton method replaces the Hessian matrix in Newton's method in optimization by a matrix $B_k$ learned from successive gradients. Solving $B_k{s}_k=-\nabla f(x_k)$ gives a descent direction whenever $B_k$ is a positive-definite symmetric matrix and the gradient is nonzero. After choosing a step size, one updates $B_k$ to satisfy the Quasi-Newton secant equation, rather than calculating every second derivative again.

For a convergent quasi-Newton method sequence $x_k\to x_{\ast }$ with $\nabla f(x_{\ast })=0$, nonsingular $H_{\ast }={\nabla }^{2}f(x_{\ast })$, and continuous Hessian nearby, the displayed condition implies q-superlinear convergence. Here $B_k{s}_k=-\nabla f(x_k)$ and $s_k=x_{k+1}-x_k$. The condition requires Hessian accuracy only along the actual steps, rather than convergence of the full matrix approximations. It is associated with John E. Dennis and Jorge Moré.

Indeed, the first-order expansion of the gradient gives $\nabla f(x_{k+1})=-(B_k-H_{\ast })s_k+o(\Vert s_k\Vert )=o(\Vert s_k\Vert )$. Nonsingularity of $H_{\ast }$ gives $\Vert x-x_{\ast }\Vert \le C\Vert \nabla f(x)\Vert$ locally. Consequently $\Vert e_{k+1}\Vert \le {\epsilon }_k(\Vert e_k\Vert +\Vert e_{k+1}\Vert )$ with ${\epsilon }_k\to 0$. Rearrangement proves $\Vert e_{k+1}\Vert /\Vert e_k\Vert \to 0$. Finite termination is understood separately from ratios with zero denominators.

A quasi-Newton method that maintains a symmetric curvature approximation for differentiable optimization. For a positive-definite symmetric matrix $H$ approximating inverse curvature, step $s$, gradient change $y$ and $\rho =1/(y^{\mathsf{T}}s)>0$, its inverse update isMultiplying by $y$ gives $H_{+}y=s$, the inverse form of the Quasi-Newton secant equation. The update is a symmetric matrix. For any nonzero $v$,Both terms are nonnegative, and both can vanish only if $s^{\mathsf{T}}v=0$ and then $v=0$. Thus positive definiteness is preserved when $y^{\mathsf{T}}s>0$, making $-H_{+}\nabla f$ a descent direction away from a stationary point. Full updates use quadratic storage in the dimension; the method does not require explicit Hessian matrix evaluations. Superlinear convergence requires additional local smoothness and line search assumptions.^[ref]

Limited-memory BFGS is a quasi-Newton method that applies an inverse-Hessian matrix approximation without storing a dense square matrix. It retains only a fixed number $\ell$ of recent secant pairs $s_k=x_{k+1}-x_k$ and $y_k=\nabla f(x_{k+1})-\nabla f(x_k)$. The standard two-loop recursion computes the search direction using $O(\ell d)$ storage and arithmetic in dimension $d$.

With a positive-definite initial metric and safeguarded curvature updates, the step is $x_{k+1}=x_k-{\alpha }_k{H}_k\nabla f(x_k)$, with ${\alpha }_k$ chosen by a line search. It is useful when full-memory BFGS would require too much storage. Fixed-memory convergence results typically give linear convergence under strong convexity, bounded metric and suitable line search assumptions; one must not automatically transfer the full-memory superlinear theorem. In a nonconvex problem, a local method does not by itself certify a global minimum.^[ref]

For $p_k=x_{k+1}-x_k$ and $y_k=\nabla f(x_{k+1})-\nabla f(x_k)$, the Quasi-Newton secant equation requires $B_{k+1}{p}_k=y_k$. It reproduces the observed change of gradient along the latest step. If $B_{k+1}$ is a positive-definite symmetric matrix and $p_k\ne 0$, necessarily $p_k^T{y}_k=p_k^T{B}_{k+1}{p}_k>0$. A line search satisfying the weak Wolfe conditions ensures this: with $p_k={\alpha }_k{s}_k$,This necessary curvature condition is also sufficient for the existence of some positive-definite symmetric matrix mapping $p_k$ to $y_k$. In an orthonormal basis whose first vector is $p_k/\Vert p_k\Vert$, its first column must be $(a,b{)}^T=y_k/\Vert p_k\Vert$, with $a=p_k^T{y}_k/\Vert p_k{\Vert }^2>0$. The block matrix with first row $(a,b^T)$ and lower-right block $b{b}^T/a+I$ has a positive Schur complement, so is positive-definite.

Suppose $f$ is bounded below, $0\prec B_k⪯MI$ for one fixed $M$, $B_k{s}_k=-\nabla f(x_k)$, and $x_{k+1}=x_k+{\alpha }_k{s}_k$ satisfies the Armijo condition with ${\alpha }_k\ge C>0$. ThenA telescoping sum proves the displayed convergence of a nonnegative series and hence $\nabla f(x_k)\to 0$. A uniform positive lower bound on the eigenvalues of $B_k$ is unnecessary for this conclusion. The conclusion is first-order stationarity; without further assumptions it does not assert convergence of the iterates or attainment of a global minimum.