Broyden-Fletcher-Goldfarb-Shanno Algorithm

A Broyden-Fletcher-Goldfarb-Shanno Algorithm is a memoriless quasi-Newton algorithm that ...

• AKA: BFGS.
• See: L-BFGS, Numerical Analysis, Optimization (Mathematics), Iterative Method, Nonlinear Optimization, Approximation Theory, Newton's Method in Optimization, Hill Climbing, Stationary Point, Kuhn–Tucker Conditions, Gradient, Taylor Expansion.

---

---

References

2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Broyden–Fletcher–Goldfarb–Shanno_algorithm Retrieved:2015-6-24.
  • In numerical optimization, the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm is an iterative method for solving unconstrained nonlinear optimization problems.

    The BFGS method approximates Newton's method, a class of hill-climbing optimization techniques that seeks a stationary point of a (preferably twice continuously differentiable) function. For such problems, a necessary condition for optimality is that the gradient be zero.

    Newton's method and the BFGS methods are not guaranteed to converge unless the function has a quadratic Taylor expansion near an optimum. These methods use both the first and second derivatives of the function. However, BFGS has proven to have good performance even for non-smooth optimizations. In quasi-Newton methods, the Hessian matrix of second derivatives doesn't need to be evaluated directly. Instead, the Hessian matrix is approximated using rank-one updates specified by gradient evaluations (or approximate gradient evaluations). Quasi-Newton methods are generalizations of the secant method to find the root of the first derivative for multidimensional problems. In multi-dimensional problems, the secant equation does not specify a unique solution, and quasi-Newton methods differ in how they constrain the solution. The BFGS method is one of the most popular members of this class. Also in common use is L-BFGS, which is a limited-memory version of BFGS that is particularly suited to problems with very large numbers of variables (e.g., >1000). The BFGS-B variant handles simple box constraints.

2014

• http://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html#broyden-fletcher-goldfarb-shanno-algorithm-method-bfgs
  • QUOTE: In order to converge more quickly to the solution, this routine uses the gradient of the objective function. If the gradient is not given by the user, then it is estimated using first-differences. The Broyden-Fletcher-Goldfarb-Shanno (BFGS) method typically requires fewer function calls than the simplex algorithm even when the gradient must be estimated.

    To demonstrate this algorithm, the Rosenbrock function is again used. The gradient of the Rosenbrock function is the vector: [math]\displaystyle{ ∂f∂xj==∑i=1N200(xi−x2i−1)(δi,j−2xi−1δi−1,j)−2(1−xi−1)δi−1,j.200(xj−x2j−1)−400xj(xj+1−x2j)−2(1−xj) }[/math].

    This expression is valid for the interior derivatives. Special cases are <mat> ∂f∂x0∂f∂xN−1==−400x0(x1−x20)−2(1−x0),200(xN−1−x2N−2)</math>.

    A Python function which computes this gradient is constructed by the code-segment:

>>> def rosen_der(x):
…     xm = x[1:-1]
…     xm_m1 = x[:-2]
…     xm_p1 = x[2:]
…     der = np.zeros_like(x)
…     der[1:-1] = 200*(xm-xm_m1**2) - 400*(xm_p1 - xm**2)*xm - 2*(1-xm)
…     der[0] = -400*x[0]*(x[1]-x[0]**2) - 2*(1-x[0])
…     der[-1] = 200*(x[-1]-x[-2]**2)
…     return der

---