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.
BFGS vs. Conjugate Gradient Method
optimization;conjugate gradient
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 toolsoperator overloading AD toolsSource-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.