BFGS method

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]