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.

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.