- Broyden-Fletcher-Goldfarb-Shanno algorithm attempts to bring some of the advantages of Newton's method without the computational burden, referred to as Quasi-Newton Methods.
- A limitation of Newton’s method is that it requires the calculation of the inverse of the Hessian matrix. This is a computationally expensive operation and may not be stable depending on the properties of the objective function.
- Quasi-Newton methods are second-order optimization algorithms that approximate the inverse of the Hessian matrix using the gradient, meaning that the Hessian and its inverse do not need to be available or calculated precisely for each step of the algorithm.

BFGS Optimization Algorithm

Newton’s method is based on using a second-order Taylor series expansion to approximate $f(x)$ near point $x^{(0)}$:
$f(x) \approx f(x^{(0)}) + (x-x^{(0)})^T \bigtriangledown _x f(x^{(0)}) + \frac{1}{2}(x-x^{(0)})^TH(f)(x^{(0)})(x-x^{(0)})$
We can solve it for the critical point and get:
$x^* = x^{(0)} - H(f)(x^{(0)})^{-1}\bigtriangledown_xf(x^{(0)})$
So that we can use the equation gotten above to jump to the optimal of the function directly.

University of Michigan - Ann Arbor

Optimization algorithms that also use the Hessian matrix, such as Newton’s method, are called second-order optimization algorithms

Second-order Optimization Algorithm

Goodfellow, I., Bengio, Y., & Courville, A. (2016). $\mathit{Deep \ Learning.}$ MIT Press. Retrieved from [www.deeplearningbook.org](https://www.deeplearningbook.org) 

Deep Learning

Newton's Method

The Conjugate Gradients is a method faster than the method of steepest descent, and it avoids calculation of the inverse Hessian required by Newton's Method. 
Instead of undoing direction search progress made previously and recalculating each step, the method of conjugate gradients looks for a search direction that is conjugate to the previous line search direction.

At t iteration, the next search direction is:
$$d_t = \nabla _\theta f(\theta) + \beta _t d_{t-1}$$
Where $\beta _t$ is a coefficient that controls the direction.
Two popular ways to calculate $\beta _t$ are:
Fletcher-Reeves:
$$\beta _t = \frac{\nabla _\theta f(\theta _t)^\top \nabla _\theta f(\theta _t)}{\nabla _\theta f(\theta _{t-1})^\top \nabla _\theta f(\theta _{t-1})}$$
Polak-Ribière:
$$\beta _t = \frac{(\nabla _\theta f(\theta _t) - \nabla_\theta f(\theta _{t-1}))^\top \nabla _\theta f(\theta _t)}{\nabla _\theta f(\theta _{t-1})^\top \nabla _\theta f(\theta _{t-1})}$$

Learn Before

Related

Learn After