User:Numerical one/sandbox

In numerical optimization, the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm is an iterative method for solving unconstrained nonlinear optimization problems.

The BFGS method belongs to quasi-Newton methods, a class of hill-climbing optimization techniques that seek a stationary point of a (preferably twice-continuously differentiable) function using only gradient evaluations (or approximate gradient evaluations). For such problems, a necessary condition for optimality at a point $x^{*}$is that the gradient at f at $x^{*}$is zero, i.e., $\nabla f(x^{*})=0$. Under certain conditions, the BFGS method exhibits superlinear convergence. (citation needed) For large problems, limited-memory BFGS (L-BFGS) is commonly used. The BFGS-B variant handles simple box constraints.

The BFGS method is one of the most popular types of quasi-Newton methods. In the case of large scale optimization (i.e., when the number of variables is greater than, for example, 10,000), limited-memory BFGS (L-BFGS) may be used. Other variants include BFGS-B, which handles simple box constraints. citation needed!

The algorithm is named after Charles George Broyden, Roger Fletcher, Donald Goldfarb and David Shanno. (I think we can say more about how these authors found this!)

Rationale

The BFGS algorithm is a quasi-Newton method for unconstrained optimization where the Hessian is approximated using the BFGS update formula. The BFGS algorithm is used to solve problems of the form

minimize $f(x)$subject to $x\in \Re ^{n},$where $f:\Re ^{n}\rightarrow \Re .$This algorithm is an iterative method where the search direction is computed as the solution of minimizing a quadratic approximation to $f(x)$at the current iterate $x_{k},$i.e., $B_{k}p_{k}=-g_{k},$where $g_{k}=\nabla f(x_{k})$and $B_{k}$is the BFGS matrix that approximates the Hessian $\nabla ^{2}f(x_{k}).$ Typically, a line search is then used to compute $\alpha _{k}$so that the next iterate is defined as $x_{k+1}=x_{k}+\alpha _{k}p_{k}.$

Derivation

Like all traditional quasi-Newton matrices, the BFGS matrix $B_{k}$satisfies the so-called secant or quasi-Newton condition: $B_{k+1}s_{k}=y_{k},$where $s_{k}=x_{k+1}-x_{k}$and $y_{k}=\nabla f(x_{k+1})-f(x_{k}).$The BFGS update is a symmetric update that is derived by considering a rank-two change to the previous approximate Hessian, i.e., $B_{k+1}=B_{k}+\alpha uu^{T}+\beta vv^{T},$where $u$and $v$are $(n\times 1)$vectors. One can show that choosing $u=y_{k}$and $v=B_{k}s_{k}$then $\alpha ={\frac {1}{y_{k}^{T}s_{k}}}$and $\beta =-{\frac {1}{s_{k}^{T}B_{k}s_{k}}}$in order that the quasi-Newton condition holds. Thus, the BFGS update is

$B_{k+1}=B_{k}+{\frac {1}{y_{k}^{T}s_{k}}}y_{k}y_{k}T-{\frac {1}{s_{k}^{T}B_{k}s_{k}}}B_{k}s_{k}s_{k}^{T}B_{k}.$

It can be shown that if the initial $B_{0}$is positive definite and $y_{k}^{T}s_{k}>0$for all $k,$then the sequence of matrices $\{B_{k}\}$will be positive definite. A Wolfe line search is typically used in conjunction with the BFGS algorithm since it guarantees $y_{k}^{T}s_{k}>0.$ (citation needed!)