15
$\begingroup$

I am teaching a numerical analysis survey class and am seeking motivation for the BFGS method for students with limited background/intuition in optimization!

While I don't have time to prove rigorously that everything converges, I'm looking to give a reasonable motivation for why the BFGS Hessian update might appear. As an analogy, Broyden's root-finding method (my writeup is here) can be motivated by asking that your current approximation of the Jacobian minimizes the difference $\|J_k-J_{k-1}\|^2_{\textrm{Fro}}$ with the old Jacobian subject to the constraint that it takes into account the latest secant: $J_k(\vec x_k-\vec x_{k-1})=f(\vec x_k)-f(\vec x_{k-1})$.

Derivations of BFGS updates seem far more involved and murky! In particular, I'd like not to assume a priori that the update should be rank-2 or take a particular form. Is there a short variational-looking motivation for the BFGS Hessian update like the one for Broyden?

$\endgroup$
  • 4
    $\begingroup$ If you'll allow an arbitrary update, then you could just use the full Hessian in Newton's method. One major computational advantage of a low rank update is that it allows you to update the factorization of the approximate Hessian very quickly. $\endgroup$ – Brian Borchers Sep 12 '13 at 0:09
12
$\begingroup$

The derivation of the BFGS is more intuitive when one considers (strictly) convex cost functionals:

However, some background information is necessary: Assume, one wants to minimize a convex functional $$ f(x) \to \min_{x\in \mathbb R^n}. $$ Say there is an approximate solution $x_k$. Then, one approximates the minimum of $f$ by the minimum of the truncated Taylor expansion $$ f(x_k+p) \approx f(x_k) +\nabla f(x_k)^Tp + \frac{1}{2}p^T H(x_k)p. \quad(*) $$ That is, one looks for $p$ such that $(*)$ is minimal and sets $x_{k+1} := x_k + p$. Computing the gradient of $(*)$ -- "with respect to $p$" -- and setting it to zero gives the relation $$ H(x_k)[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k), $$ where $H$ is the 'Jacobian of the gradient' or the Hessian matrix.

Since the computation and inversion of the Hessian is expensive...


...a short answer

(cf. Broyden's update) might be that the BFGS update $H_{k+1}^{-1}$ minimizes $$ \|H_k^{-1} - H^{-1}\|_W $$ in a smartly chosen weighted Frobenius norm, subject to

  1. $H[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k)$ -- this is what one is out for -- and
  2. $H^T = H$, because the Hessian is symmetric.

Then the choice of the weight $W$ in $\|H\|_W := \|W^{1/2}HW^{1/2}\|_F$ as the inverse of the averaged Hessian $G:=\int_0^1 H(x_k + \tau p) d\tau$, cf. here for the statement but without proof, gives the BFGS update formula (with $\alpha_k = 1$).

The major points are:

  • One tries to approximate the solution for the actual costs by the solution for a quadratic approximation
  • Computation of the Hessian, and its inverse, is expensive. One prefers simple updates.
  • The update is chosen optimal for the inverse rather than the actual Hessian.
  • That it is a rank-2 update is a consequence of the particular choice of the weights in the Frobenius norm.

A longer answer, should include how to choose the weights, how to make this work for nonconvex problems (where a curvature condition appears that requires a scaling of the search direction $p$), and how to derive actual the formula for the update. A reference is here (in German).

$\endgroup$
  • $\begingroup$ Thanks so much, this is great (and more or less what I expected based on the discussion in Nocedal&Wright). The one remaining question I have is: why do we choose $W$ and the norm as we do? I get that it has to do with units, but there are lots of potential choice of $W$ and norms that do this. $\endgroup$ – Justin Solomon Sep 14 '13 at 18:35
  • $\begingroup$ Yes, true. Well, I don't know. One answer is that it gives the simple to compute and well working update formula. Historically, this approach to the update -- minimizing the difference in the update -- was the one by Shanno. It was a referee (Goldfarb) who found that a particular choice of the weights leads to the formula of Broyden and Fletcher. See this PhD thesis Historical development of the BFGS secant method ... for the intuitions of the developers of the BFGS. However, all 3 approaches are quite abstract. $\endgroup$ – Jan Sep 16 '13 at 17:32
  • 1
    $\begingroup$ Interesting, thanks for the guidance! My current writeup (with some math mistakes that need help) is here: graphics.stanford.edu/courses/cs205a-13-fall/assets/notes/… (if you would like credit for your help I'm happy to provide it -- please email me with suitable contact info) $\endgroup$ – Justin Solomon Sep 17 '13 at 15:36
  • $\begingroup$ @jan Why is your equation $$ H(x_k)[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k)$$ and not $$H(x_{k+1})[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k)?$$ Isn't the secant condition given by $H_{k+1}s_k =y_k$, where $s_k=x_{k+1}-x_k, y_k=\nabla f_{k+1}-\nabla f_k$. Thanks! $\endgroup$ – Jeff Faraci May 12 '17 at 3:37

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.