Davidon-Fletcher-Powell Method

Uses a rank two correction,

H_k+1 = H_k + uu^T + vv^T

and preserves positive definiteness.

Start with a symmetric, positive definite, matrix H₀ at a point x₀ with k=0

1.

Set d_k = -H_k g_k

2.

leading to
x_k+1, and g_k+1.

3.

Set q_k = g_k+1 - g_k and compute

$$H_{k+1} = H_k + \frac{p_k p_K^T}{p_k^T q_k} - \frac{H_k q_k q_k^T H_k}{q_k^T H_k q_k}$$

Update k and go to 1.

• Rank two update, since we update with two symmetric matrices.
• Can show that H_k is positive definite
• If f quadratic
  • The directions d_k are F-orthogonal
  • After n steps H_n = F^-1
• The method is a conjugate direction method
• If H₀ = I we have the CG method.

There exists a whole family of rank two updates, the Broyden family. From practical experiences the BFGS method seem to be most popular.