[R] BFGS versus L-BFGS-B

[Prof. John C Nash]

Bert has put a finger on one of the key questions: Are we there yet?

Global optima are very difficult to find in many, possibly most problems.
We can check for local optima. In package optimx (currently resetting it on CRAN due to a
variable naming glitch with Rvmmin -- should be there in a couple of days) we carry out
the Kuhn Karush Tucker tests, but even these have scale dependencies. On R-forge there's a
new package under our optimization and solving packages project called kktc that separates
off the tests. However, that's only a start.

Constraints require us to do more work, too.

A couple of very large scale problems have been noted. The minimization of energy for
collections of atoms or molecules was suggested, but my experience with that type of
problem is that it has a huge number of local minima and is not amenable to the techniques
that the original poster had in mind, and certainly optim(BFGS) nor Rcgmin nor
optim(L-BFGS-B) are appropriate as they stand, though they may be helpful in some sort of
polyalgorithm.

ALso I did not post, but mentioned in private emails, that L-BFGS-B and Rcgmin should
offer much lower memory demands for problems in large numbers of parameters than
optim(BFGS) which has an explicit inverse Hessian approximation i.e., n*n doubles to
store. BFGS and L-BFGS-B have very different internals.

JN


On 02/25/2011 08:46 PM, Bert Gunter wrote:
> Thanks to all for clarifications. So I'm off base, but whether waaay
> off base depends on whether there is a reasonably well defined optimum
> to converge to. Which begs the question, I suppose: How does one know
> whether one has converged to such an optimum?  This is always an
> issue, of course, even for a few parameters; but maybe more so with so
> many.
> 
> -- Bert
> 
> On Fri, Feb 25, 2011 at 3:35 PM, Ravi Varadhan <rvaradhan at jhmi.edu> wrote:
>> I have worked on a 2D image reconstruction problem in PET (positron emission
>> tomography) using a Poisson model.  Here, each pixel intensity is an unknown
>> parameter.  I have solved problems of size 128 x 128 using an accelerated EM
>> algorithm.  Ken Lange has shown that you can achieve term by term separation
>> using a minorization inequality, and hence the problem simplifies greatly.
>>
>> Ravi.
>>
>> -------------------------------------------------------
>> Ravi Varadhan, Ph.D.
>> Assistant Professor,
>> Division of Geriatric Medicine and Gerontology School of Medicine Johns
>> Hopkins University
>>
>> Ph. (410) 502-2619
>> email: rvaradhan at jhmi.edu
>>
>> -----Original Message-----
>> From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org] On
>> Behalf Of Prof. John C Nash
>> Sent: Friday, February 25, 2011 5:55 PM
>> To: Bert Gunter
>> Cc: r-help at r-project.org
>> Subject: Re: [R] BFGS versus L-BFGS-B
>>
>> For functions that have a reasonable structure i.e., 1 or at most a few
>> optima, it is
>> certainly a sensible task. Separable functions are certainly nicer (10K 1D
>> minimizations),
>> but it is pretty easy to devise functions e.g., generalizations of
>> Rosenbrock, Chebyquad
>> and other functions that are high dimension but not separable.
>>
>> Admittedly, there are not a lot of real-world examples that are publicly
>> available. More
>> would be useful.
>>
>> JN
>>
>>
>> On 02/25/2011 05:06 PM, Bert Gunter wrote:
>>> On Fri, Feb 25, 2011 at 12:00 PM, Brian Tsai <btsai00 at gmail.com> wrote:
>>>> Hi John,
>>>>
>>>> Thanks so much for the informative reply!  I'm currently trying to
>> optimize
>>>> ~10,000 parameters simultaneously - for some reason,
>>>
>>> -- Some expert (Ravi, John ?) please correct me, but: Is the above not
>>> complete nonsense? I can't imagine poking around usefully  in 10K
>>> dimensional space for an extremum unless maybe one can find the
>>> extremum by 10K separate 1-dim optimizations. And maybe not then
>>> either.
>>>
>>> Am I way offbase here, or has Brian merely described just another
>>> inefficient way to produce random numbers?
>>>
>>> -- Bert
>>
>> ______________________________________________
>> R-help at r-project.org mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
>> and provide commented, minimal, self-contained, reproducible code.