Quasi-Newton method

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.