BFGS vs. Conjugate Gradient Method

Question

What considerations should I be making when choosing between BFGS and conjugate gradient for optimization? The function I am trying to fit with these variables are exponential functions; however, the actual objective function involves integration, among other things, and is very costly if that helps at all.

Answer 1

J.M. is right about storage. BFGS requires an approximate Hessian, but you can initialize it with the identity matrix and then just calculate the rank-two updates to the approximate Hessian as you go, as long as you have gradient information available, preferably analytically rather than through finite differences. BFGS is a quasi-Newton method, and will converge in fewer steps than CG, and has a little less of a tendency to get "stuck" and require slight algorithmic tweaks in order to achieve significant descent for each iteration.

In contrast, CG requires matrix-vector products, which may be useful to you if you can calculate directional derivatives (again, analytically, or using finite differences). A finite difference calculation of a directional derivative will be much cheaper than a finite difference calculation of a Hessian, so if you choose to construct your algorithm using finite differences, just calculate the directional derivative directly. This observation, however, doesn't really apply to BFGS, which will calculate approximate Hessians using inner products of gradient information.

In terms of convergence rates, if $n$ is the number of decision variables in your problem, then $n$ CG iterations approximately equals one step of Newton's method. BFGS is a quasi-Newton method, but the same sort of observation should hold; you're likely to get convergence in fewer iterations with BFGS unless there are a couple CG directions in which there is a lot of descent, and then after a few CG iterations, you restart it. CG-like methods are cheaper if matrix-vector products are cheap and your problem is so large that storing the Hessian is difficult or impossible. BFGS involves some more vector-vector products to update its approximate Hessian, so each BFGS iteration will be more expensive, but you'll require fewer of them to reach a local minimum.

I would compare the two algorithms on a small test problem for your application if you know that storage won't be an issue. Without knowing the particular specifics of your problem, my guess is that BFGS will be faster, but you should really test the two algorithms to get a better idea of which will work better.

Finally, a word about automatic differentiation: having some experience with an in house automatic differentiation (AD) facility for Fortran (DAEPACK), I can tell you that AD tools are often finicky. They may not necessarily be able to differentiate the code that they generate themselves. There are two types of AD tools:

• source-to-source AD tools
• operator overloading AD tools

Source-to-source tools are essentially modified compilers that take source code you've written, parse it, and automatically generate new source code that computes the gradient of functions in your source code. Operator overloading AD tools require you to use the overloaded AD operators in your source code so that derivatives can be calculated, which would require additional effort on your part to calculate analytical derivatives with AD.

Answer 2

The associated cost of BFGS may be brought more in line with CG if you use the limited memory variants rather than the full-storage BFGS. This computes the BFGS update for the last $m$ updates efficiently by a series of rank-one updates without needing to store more than the last $m$ solutions and gradients.

In my experience, BFGS with a lot of updates stores information too far away from the current solution to be really useful in approximating the non-lagged Jacobian, and you can actually lose convergence if you store too much. There are "memoryless" variants of BFGS that look a lot like nonlinear conjugate gradients (see the final update described for one of these) for just these reasons. Therefore, if you're willing to do L-BFGS rather than BFGS, the memory issues disappear and the methods are related. Anecdotal evidence points to restarting being a tricky issue, as it is sometimes unnecessary and sometimes very necessary.

Your choice between the two also depends heavily on the problems you are interested in. If you have the resources, you can try both for your problems and decide which works better. For example, I personally don't do optimization with these algorithms, but instead care about the solution of systems of nonlinear equations. For these I have found that NCG works better and is easier to perform nonlinear preconditioning on. BFGS is more robust.

Frankly, my favorite method for these types of things is N-GMRES. This is especially true if your gradient evaluation is very expensive, as in my experience it gives you the most bang for your buck by solving a small minimization problem on the last $m$ iterates to construct a new, lower-residual solution.

Answer 3

In low dimensions, a well implemented BFGS method is generally both faster and more robust than CG, especially if the function is not very far from a quadratic.

Neither BFGS nor CG need any assumption about convexity; only the initial Hessian approximation (for BFGS) resp. the preconditioner (for CG) must be positive definite. But these can always be chosen to be the identity matrix, in low dimensions without much harm. See also https://scicomp.stackexchange.com/a/3213/1117

In the absence of a programmed gradient, it is a big waste of effort to use numerical gradients, especially when function values are expensive. Rather, one should use a derivative-free algorithm. See Rios and Sahinidis 2013 and its accompanying webpage for a recent survey.