BFGS method

From Glossary

Jump to: navigation, search

This is a method to solve an unconstrained nonlinear program that proceeds as follows.

  1. Start with any symmetric, negative definite matrix, say LaTeX: B^0, and any initial point LaTeX: x^0. Set LaTeX: k = 0
  2. Direction: Solve LaTeX:  B^k d^k = -\nabla f(x^k).
  3. Step size: LaTeX: s^k \in \arg\max \{ f(x^0 + td^k) : t \ge 0 \}.
  4. Change in position: LaTeX:  p^k = s^k d^k.
  5. New point: LaTeX:  x^{k+1} = x^k + p^k.
  6. Change in gradient: LaTeX: q^k = \nabla f(x^{k+1}) - \nabla f(x^k).
  7. Update LaTeX: B^k to form LaTeX: B^{k+1} with the BFGS update.
  8. Let LaTeX: k = k+1 to complete the iteration.

Compare this with the DFP method, and note a key difference is that DFP estimates the inverse hessian, whereas BFGS estimates the hessian (and solves the linear system). There is a correspondance, and empirical evidence suggests, that the BFGS method has less of a problem with error.

Personal tools