14
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Could you provide a hyperlink for the PORT algorithm? Also, this may be too broad a question in its current form. – Reviewer $\endgroup$
    – Jim
    Apr 14, 2018 at 20:32
  • 2
    $\begingroup$ Yes the PORT routine can be found here ms.mcmaster.ca/~bolker/misc/port.pdf . I was using these optimization tools to estimate a CES production function in the micEconCES package. That's why I was wondering if any of these methods does have a special advantage over the others when doing so $\endgroup$
    – macro123
    Apr 15, 2018 at 0:45
  • 3
    $\begingroup$ @Jim - PORT is a 40 or so year old FORTRAN implementation of Levenberg-Marquardt. $\endgroup$
    – jbowman
    Apr 15, 2018 at 2:02
  • 2
    $\begingroup$ The answer by @jbowman adresses your question well. Are you sure about the "-B" part of L-BFGS-B? There is a L-BFGS without a B. It is widely used [in machine learning] because it is more memory-efficient than plain vanilla BFGS. $\endgroup$
    – Jim
    Apr 15, 2018 at 8:59
  • $\begingroup$ @Jim - you're right (+1), it's a limited-memory modification, but the big difference is the box constraints. I did not know it was widely used in machine learning because of memory efficiency, as I didn't know memory efficiency was much of a thing any more (and I work with big data)! I'll update my answer below appropriately. $\endgroup$
    – jbowman
    Apr 15, 2018 at 15:11

2 Answers 2

14
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Wow, that linked answer is almost exactly 7 years old.... $\endgroup$
    – Hong Ooi
    Apr 16, 2018 at 12:27
  • $\begingroup$ " 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" I hope you mean that it does that if some option special option is enabled. Otherwise it sounds quite evil. If you supply a gradient it is probably because you can supply a much faster one. If it then did an explicit check by calling the function in some obscure way I would be really pissed. $\endgroup$
    – Kvothe
    Feb 10, 2021 at 16:47
11
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I'm not sure why you think PORT is solving nonlinear least-squares. From the first page of the pdf that OP linked to in a comment: "Given a function $f$ of $p$ variables, the optimization routines attempt to find a $p$-vector $x*$ that minimizes $f(x)$." $\endgroup$
    – Hong Ooi
    Apr 15, 2018 at 4:59
  • 1
    $\begingroup$ At a guess, I'd say that OP is talking about the PORT underlying R's nlminb function which does the same thing as optim: general nonlinear optimisation. The underlying routines for both these functions are all several decades old. $\endgroup$
    – Hong Ooi
    Apr 15, 2018 at 5:00
  • $\begingroup$ If you read more of the documentation, it talks about "regression" and "estimated confidence intervals" for the parameters. One of the return values is the Levenberg-marquardt $\lambda$ parameter. The code is Fortran and the document is from 1990. Maybe I'm wrong but it did look to me like nonlinear least squares; I'll look more tomorrow my time. $\endgroup$
    – jbowman
    Apr 15, 2018 at 5:12
  • $\begingroup$ Right I am very interested to know whether L-BFGS-B with a high enough value for the number of entries to keep is approximately as fast as a BFGS-B would be if it existed. (Let's say we compare BFGS and L-BFGS-B with large bounds far away from the area of interest.) $\endgroup$
    – Kvothe
    Feb 10, 2021 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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