2
$\begingroup$

What is the exact algorithm used in nlm function in R. The documentation says:

Description

This function carries out a minimization of the function f using a Newton-type algorithm. See the references for details.

Then in references:

References

Dennis, J. E. and Schnabel, R. B. (1983) Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs, NJ.

Schnabel, R. B., Koontz, J. E. and Weiss, B. E. (1985) A modular system of algorithms for unconstrained minimization. ACM Trans. Math. Software, 11, 419–440.

Out of these references, first one is a book and I do not know where to look at in the book. Second is a 42 page paper which describes a system of algorithms as implemented in FORTRAN package UNCMIN. I did not read it, but then I am not sure if reading it completely will give answer to my question. (given that I don't know anything about FORTRAN it seems harder to start with).

Then as per the documentation

Source

The current code is by Saikat DebRoy and the R Core team, using a C translation of Fortran code by Richard H. Jones.

So nlm is translated, and not directly built using algorithm. So is there any algorithm/pseudo code for the Fortran code by Richard H.

$\endgroup$
  • $\begingroup$ The Newton-Type method in nlm estimates the gradient numerically then applies Newton Raphson. $\endgroup$ – Halbort Apr 15 '17 at 23:12
  • $\begingroup$ The Newton-Type method in nlm estimates the gradient numerically then applies Newton Raphson. $\endgroup$ – Halbort Apr 16 '17 at 0:26
1
$\begingroup$

Source Code

You can find the source code in

  • a wrapper function nlm: r-source/blob/master/src/library/stats/src/optimize.c
  • the function optif9 (another wrapper) and optdrv performing the algorithm: r-source/src/appl/uncmin.c

Three algorithms and relation with the Dennis and Schnabel reference

The algorithm seems to contain three methods:

Note that this is much like the description of the FORTRAN code:

The novel feature of UNCMIN is that it is a modular system of algorithms, containing three different step selection strategies (line search, dogleg, and optimal step) that may be combined with either analytic or finite difference gradient evaluation, and either analytic, finite difference or BFGS Hessian approximation.

NLM uses line-search

In the source code of the nlm function in the optimize.c file you can see that the first method is chosen explicitly

method = 1; /* Line Search */

Line search is an alternative method to the Newton's method (or the Newton–Raphson method), to find an optimal step to find the root of a function (or stationary point when performed on the derivative of a function). With Newton's method you would compute the stepsize analytically using the reciprocal/inverse of the slope/gradient. With the line search method you use some iterative algorithm to find an optimal stepsize.

$\endgroup$
  • $\begingroup$ Thanks a lot for pointing out the exact sections and the source code. $\endgroup$ – Gaurav Singhal Jan 15 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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