Trust Region Unconstrained Optimization for R

University of Minnesota, Twin Cities     School of Statistics     Charlie Geyer's Home Page

Last changed: Tue Oct 25 17:00 CDT 2005

New! The software is now at CRAN. The package name is trust and its CRAN web page is http://cran.r-project.org/package=trust.

This web page provides yet another unconstrained optimization routine for the R statistical computing environment. It's already got two: nlm and optim. But here's another.

The PDF version of the manual can be found at the CRAN web page.

So why another optimization routine? In short, it does well what the others do badly (and vice versa).

• trust requires gradient and Hessian of the objective function. (nlm and optim will calculate using finite differences).
• trust does an eigendecomposition of the Hessian in each iteration (nlm and optim use quasi-Newton and much less memory on large problems).
• trust is guaranteed to converge to a point satisfying the first and second order necessary conditions for a local optimum (gradient zero and Hessian positive semidefinite for minimization or negative semidefinite for maximization). nlm and optim come with no guarantees and often perform badly on difficult problems.
• trust converges at second order if the solution satisfies the second order sufficient conditions for a local optimum (gradient zero and Hessian positive definite for minimization or negative definite for maximization). nlm and optim don't converge quadratically and often produce solutions of limited accuracy.
• trust handles restricted domains so long as the solution is in the interior of the domain. nlm cannot handle any restrictions; the domain must be a full Euclidean space. optim using method = "L-BFGS-B" handles box constraints, but not general constraints.
• trust does not do global optimization, but neither does anything else in R.

trust was written because I was forced to. I had an objective function that was very expensive to compute (a Monte Carlo computation) but analytic derivatives were available (just differentiate the Monte Carlo computation). Moreover, the objective function was really obnoxious, having a banana-shaped ridge. nlm and optim just led to endless waste of time, producing no useful results. It was very depressing. As soon as I had trust region code, it was perfectly clear how obnoxious the objective function was, and we found its local optima efficiently despite the obnoxiousness.

Once trust was available, I made it the default optimizer for the aster contributed package for R. Even though it is supposed to be slow compared to nlm and optim, and it is slow when the basis of comparison is the time to do one iteration, in practice on this class of problems (aster is doing maximum likelihood in an exponential family, hence maximizing a concave function) trust is about 4 times as fast as nlm and about 16 times as fast as optim using either its "CG" or its "L-BFGS-B" method. The evidence is the following simulation study done using Sweave. Here is the PDF output, and here is the Sweave source (Rnw file).