BFGS method

From DDWiki

Jump to: navigation, search

Broyden-Fletcher-Goldfarb-Shanno (BFGS) method is a numerical algorithm to find optimal solution for unconstrained nonlinear problem, where it has been considered one of the most efficient approaches.

BFGS belongs to quasi-Newton method, which utilizes first-order gradient information to generate approximate Hessian matrix. Avoiding the calculation of exact Hessian (2nd-order gradient) can save significant computational cost during iteration process of optimization.

Formulation

\mathbf{B}^*=\mathbf{B}-\frac{\mathbf{Bpp}^T\mathbf{B}}{\mathbf{p}^T\mathbf{Bp}}+\frac{\mathbf{\eta \eta}^T}{\mathbf{p \eta}}

where B is the approximate Hessian matrix used in iteration

\mathbf{p}=\mathbf{x}^q-\mathbf{x}^{q-1}
\eta = \theta \mathbf{y} +(1-\theta) \mathbf{Bp}
\mathbf{y}= \nabla_x \phi(x^q,\lambda^q)- \nabla_x \phi(x^{q-1},\lambda^{q-1})
\phi = f(\mathbf{x})+\sum^{m}_{j=1}\lambda_{j} g_j(\mathbf{x})) + \sum^{l}_{k=1}\lambda_{m+k} h_k(\mathbf{x})
\mathbf{\theta}=1.0 if \mathbf{py} \ge 0.2 \mathbf{p}^T\mathbf{Bp}
\theta=\frac{0.8\mathbf{p}^T\mathbf{Bp}}{\mathbf{p^TBp-py}} if \mathbf{py} < 0.2 \mathbf{p}^T\mathbf{Bp}

References

  • G.N. Vanderplaats, Numerical Optimization techniques for Engineering Design with Applications, 1984, McGraw-Hill Inc.
  • S.S. Rao, Engineering Optimization: Theory and Practice, 1996, 3rd Ed., John Wiley & Sons, Inc.
Retrieved from "http://ddl.me.cmu.edu/ddwiki/index.php/BFGS_method"