Advantages/Disadvantages of BFGS vs. L-BFGS-B vs. PORT

Question

I am looking for advantages and disadvantages of the Broyden-Fletcher-Goldfarb-Shanno algorithm (BFGS), the L-BFGS-B and PORT algorithm in optimization. Which one promises the best results and why?

Answer 1

I infer from your question that you're an R user, and you want to know whether to use optim (which has BFGS and L-BFGS-B options) or nlminb (which uses PORT).

See my answer here. The relevant bit:

• optim can use a number of different algorithms including conjugate gradient, Newton, quasi-Newton, Nelder-Mead and simulated annealing. The last two don't need gradient information and so can be useful if gradients aren't available or not feasible to calculate (but are likely to be slower and require more parameter fine-tuning, respectively). It also has an option to return the computed Hessian at the solution, which you would need if you want standard errors along with the solution itself.

• nlminb uses a quasi-Newton algorithm that fills the same niche as the "L-BFGS-B" method in optim. In my experience it seems a bit more robust than optim in that it's more likely to return a solution in marginal cases where optim will fail to converge, although that's likely problem-dependent. It has the nice feature, if you provide an explicit gradient function, of doing a numerical check of its values at the solution. If these values don't match those obtained from numerical differencing, nlminb will give a warning; this helps to ensure you haven't made a mistake in specifying the gradient (easy to do with complicated likelihoods).

However, for modern work you should be able to do better than either of these, as the underlying routines are all several decades old. See the Optimization task view on CRAN for a list of general optimizer packages. In particular, I'd recommend the nloptr, minqa and lbfgsb3 packages. Also, Rcgmin, Rvmmin and Rtnmin provide replacements for the routines built into optim. Finally, optimr is a shell that lets you call other optimization functions using the same interface.

nloptr and minqa are both used by the very popular lme4 package for mixed modelling, so there's a vote of confidence if you need it.

Answer 2

The three algorithms don't attempt to solve the same problem, so choosing between them will depend on what problem you ARE trying to solve.

BFGS attempts to solve a general nonlinear optimization problem without any constraints. You can think of it as an approximation to Newton's method, where the approximation is a clever "estimation" of the Hessian that updates with each iteration.

L-BFGS-B is a variant of BFGS that allows the incorporation of "box" constraints, i.e., constraints of the form $a_i \leq \theta_i \leq b_i$ for any or all parameters $\theta_i$. Obviously, if you don't have any box constraints, you shouldn't bother to use L-BFGS-B, and if you do, you shouldn't use the unconstrained version of BFGS.

ETA: Jim points out in comments above that L-BFGS-B uses a limited memory version of BFGS as well as incorporating box constraints. This could be important for your application, or not. I haven't run into memory constraints in a long time, but that is a function of my application area and work environment, and, as Jim observes, "it is widely used[in machine learning] because it is more memory efficient than plain vanilla BFGS".

PORT is a particular implementation of the Levenberg-Marquardt algorithm, and solves a nonlinear least squares problem. Note that in this case the objective function is fixed, namely, $\sum_{i=1}^N(y_i-f(\theta,x_i))^2$, although you still get to specify $f$. Obviously if this is not your objective function you can't use PORT! But if it is, then you should use L-M in preference to the less-specialized BFGS algorithms.