A quasi-Newton method for unconstrained optimization

We will assume that f and $\bold{x}^*$ satisfy the following assumptions:

1.

f is twice continuously differentiable

2.

$\nabla f(\bold{x}^*) = 0$

3.

$\nabla^2 f(\bold{x}^*)$ is symmetric positive definite

The Newton methods update the current iteration $\bold{x}_n$ by the formula

$$\bold{x}_{n+1}=\bold{x}_n - \lambda_n \bold{H}_n^{-1}\nabla f(\bold{x}_n),$$ (1)

where $\lambda_n$ is given by a line search that ensures sufficient decrease. Quasi-Newton methods update an approximation of the Hessian $\bold{H}_n^{-1}$ as the iterations progress. A possible update is the BFGS method Broyden (1969); Fletcher (1970); Goldfarb (1970); Shanno (1970), which overcomes some limitations of the earlier Broyden's method Broyden (1965). In particular, the Broyden's update does not keep the spd structure of the Hessian. This structure not only ensures the existence of a local minimizer but also allows the convergence of the updated solution $\bold{x}_{n+1}$ to the minimum Kelley (1999). The BFGS update is a rank-two update given by

$$\bold{H}_{n+1}=\bold{H}_n+\frac{\bold{yy}^T}{\bold{y}^T\bold... ...old{s}) (\bold{H}_n\bold{s})^T}{\bold{s}^T\bold{H}_n\bold{s}},$$ (2)

with $\bold{s}=\bold{x}_{n+1}-\bold{x}_n$ and $\bold{y}=\nabla f(\bold{x}_{n+1})-\nabla f(\bold{x}_n)$.In practice, it is very useful to express the previous equation in terms of the inverse matrices. We then have

$$\bold{H}_{n+1}^{-1}=\left(\bold{I}-\frac{\bold{sy}^T}{\bold{... ...y}^T\bold{s}}\right)+ \frac{\bold{ss}^T}{\bold{y}^T\bold{s}}.$$ (3)