I'm trying to implement the Broyden-Fletcher-Goldfarb-Shanno method to find the minimum of a function. I need two initial guesses $x_{-1}$ & $x_0$ and an initial Hessian Matrix approximation $B_0$. The only requirements I find for $B_0$ is that if the Hessian is symmetric positive definite, so too should $B_0$. Looking at wikipedia, I see that a typical initial approximation is $B_0=I$ (the identity matrix). Is this always a good initial $B_0$? Is there any reason why I might want to choose anything other than $I$? Would other choices of B, satisfying the same matrix properties, greatly affect the convergence of the method?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
If you have a justified Hessian approximation, it is better to use it rather than the arbitrary $B_0=I$.
Edit: The rationale is that if you start close to the solution $x^*$, the initial rate of convergence is (for any $r>0$) $r+1$-step linear with a $r+1$-step convergence factor of $q=\|B_0^{-1}f''(x^*)-G\|$ if this is $<1$ for some rank $r$ correction $G$ of the identity matrix. Thus trying to make this small is very valuable. (This is equivalent to preconditioning the system.) The convergence factor improves with time and ultimately approaches zero (superlinear convergence), but in many real problems (especially high-dimensional ones), one never makes enough iterations to reach the superlinear regime. Thus the initial speed is quite important.
One important case is when solving nonlinear least squares problems (minimize $\|F(x)\|_2^2$), where the Gauss-Newton approximation $B_0=F'(x_0)^TF'(x_0)$ of the initial Hessian can be computed without the need for second derivatives. Using it makes the BFGS method affine invariant, i.e., invariant under linear transformations of $x$ like Newton's method, which is usually very beneficial.
Another important case is when you solve a sequence of related problems. Often, restarting the solver with the final Hessian approximation of the previous problem significantly reduces the number of iterations needed.
-
1$\begingroup$ If the hessian is expected to be symmetric positive definite, any symmetric positive definite matrix $B_0$ will still lead to convergence, but the rate of convergence rests on how closely $B_0$ resembles the Hessian? $\endgroup$– PaulSep 5, 2012 at 17:20
-
1$\begingroup$ No, eventually, BFGS forgets about the starting matrix, so convergence as $k\rightarrow \infty$ always has the same order. But that's of course not interesting because you never do infinitely many steps. $\endgroup$ Sep 6, 2012 at 3:27
-