R devel - Oct 2016 - optim(…?=, =?utf-8?Q?method=‘L-BFGS-B’) stops with an error message while violating the lower bound

Hi, Mark et al.:


       Thanks, Mark.


       Three comments:


             1.  Rvmmin was one of the methods I tried after Ravi 
directed me to optimx.  It returned NAs for essentially everything. See 
my email of this subject stamped 4:43 PM Central time = 21:43 UTC.


             2.  It would be interesting to know if the current 
algorithm behind optim and optimx with method='L-BFGS-B' incorporates 
Morales and Nocedal (2011) 'Remark on ?Algorithm 778: L-BFGS-B: Fortran 
Subroutines for Large-Scale Bound Constrained Optimization?'.  I created 
this vignette and started this threat hoping that someone on the R Core 
team might decide it's worth checking things like that.


             3.  The vignette mentioned below was extracted from a 
larger vignette fitting several models that seem to encounter 
convergence problems.  I should probably switch to optimx using all the 
methods that offers for constrained optimization, including nminb.


       Best Wishes,
       Spencer Graves


On 10/8/2016 5:00 PM, Mark Leeds wrote:
> Hi Spencer: See the link below about L-BFGS-B below because  I had 
> problems
> with it a good while back (and I think the link description is the 
> cause but I can't prove it )  so  eventually I moved to the  Rvmmin(b) 
> package. It's a package but really an algorithm. Rvmmin(b) uses a 
> variable-metric algorithm similar to that of L-BFGS-B but without the 
> problem below. It's not surprisingly a creation of John Nash and quite 
> impressive based on my experience. Just like L-BFGS, it can implement 
> box constraints by adding the b.
>
> http://users.eecs.northwestern.edu/~morales/PSfiles/acm-remark.pdf 
>
<http://users.eecs.northwestern.edu/%7Emorales/PSfiles/acm-remark.pdf>
>
>
>
>
>
>
>
> On Sat, Oct 8, 2016 at 2:50 PM, Spencer Graves 
> <spencer.graves at prodsyse.com <mailto:spencer.graves at
prodsyse.com>> wrote:
>
>     Hello:
>
>
>           The development version of Ecdat on R-Forge contains a
>     vignette in which optim(?, method=?L-BFGS-B?) stops with an error
>     message while violating the lower bound.
>
>
>           To see all the details, try the following:
>
>
>     install.packages("Ecdat",
repos="http://R-Forge.R-project.org
>     <http://R-Forge.R-project.org>")
>
>
>           Then do "help(pac=Ecdat)" -> "User guides,
package vignettes
>     and other documentation" ->
"Ecdat::AverageIncomeModels".
>
>
>           I've found other optimizers that will get around the problem
>     in this case but none that performs as well as optim with many
>     other problems.
>
>
>           Thanks,
>           Spencer Graves
>
>
>     p.s.  I've also tested bobyqa{minqa} or nloptr{nloptr},
>     recommended in a vignette in the lme4 package.  These did better
>     than optim in this example but worse in others I tried.
>
>     ______________________________________________
>     R-devel at r-project.org <mailto:R-devel at r-project.org>
mailing list
>     https://stat.ethz.ch/mailman/listinfo/r-devel
>     <https://stat.ethz.ch/mailman/listinfo/r-devel>
>
>

	[[alternative HTML version deleted]]

Hi Spencer:

1)  I can't help much as far as your results but one thing you could do is
check what
the convergence flag of Rvmmin is. There are difference ones depending
on what happened during the optimization and they're pretty helpful IIRC.
But that may require running Rvmmin directly rather than in optimx.
I did a lot of optimizations ( hundreds ) at one point and I never saw it
return NA ??

2) I wasn't sure about 2) either so I figured it was safer to get away from
L-BFGS-B.








On Sat, Oct 8, 2016 at 7:03 PM, Spencer Graves <spencer.graves at
prodsyse.com>
wrote:
> Hi, Mark et al.:
>
>
>       Thanks, Mark.
>
>
>       Three comments:
>
>
>             1.  Rvmmin was one of the methods I tried after Ravi directed
> me to optimx.  It returned NAs for essentially everything.  See my email of
> this subject stamped 4:43 PM Central time = 21:43 UTC.
>
>
>             2.  It would be interesting to know if the current algorithm
> behind optim and optimx with method='L-BFGS-B' incorporates Morales
and
> Nocedal (2011) 'Remark on ?Algorithm 778: L-BFGS-B: Fortran Subroutines
for
> Large-Scale Bound Constrained Optimization?'.  I created this vignette
and
> started this threat hoping that someone on the R Core team might decide
> it's worth checking things like that.
>
>
>             3.  The vignette mentioned below was extracted from a larger
> vignette fitting several models that seem to encounter convergence
> problems.  I should probably switch to optimx using all the methods that
> offers for constrained optimization, including nminb.
>
>
>       Best Wishes,
>       Spencer Graves
>
>
>
> On 10/8/2016 5:00 PM, Mark Leeds wrote:
>
> Hi Spencer: See the link below about L-BFGS-B below because  I had problems
> with it a good while back (and I think the link description is the cause
> but I can't prove it )  so  eventually I moved to the  Rvmmin(b)
package.
> It's a package but really an algorithm. Rvmmin(b) uses a
variable-metric
> algorithm similar to that of L-BFGS-B but without the problem below.
It's
> not surprisingly a creation of John Nash and quite impressive based on my
> experience. Just like L-BFGS, it can implement box constraints by adding
> the b.
>
> http://users.eecs.northwestern.edu/~morales/PSfiles/acm-remark.pdf
>
>
>
>
>
>
>
> On Sat, Oct 8, 2016 at 2:50 PM, Spencer Graves <
> spencer.graves at prodsyse.com> wrote:
>
>> Hello:
>>
>>
>>       The development version of Ecdat on R-Forge contains a vignette
in
>> which optim(?, method=?L-BFGS-B?) stops with an error message while
>> violating the lower bound.
>>
>>
>>       To see all the details, try the following:
>>
>>
>> install.packages("Ecdat",
repos="http://R-Forge.R-project.org")
>>
>>
>>       Then do "help(pac=Ecdat)" -> "User guides,
package vignettes and
>> other documentation" -> "Ecdat::AverageIncomeModels".
>>
>>
>>       I've found other optimizers that will get around the problem
in
>> this case but none that performs as well as optim with many other
problems.
>>
>>
>>       Thanks,
>>       Spencer Graves
>>
>>
>> p.s.  I've also tested bobyqa{minqa} or nloptr{nloptr}, recommended
in a
>> vignette in the lme4 package.  These did better than optim in this
example
>> but worse in others I tried.
>>
>> ______________________________________________
>> R-devel at r-project.org mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-devel
>
>
>
>
	[[alternative HTML version deleted]]

Spencer,
Another option is to try the "lbfgs" package.  Hans Werner Borchers
has told me that this is a good implementation of L-BFGS.
Best,
Ravi
________________________________________
From: R-devel <r-devel-bounces at r-project.org> on behalf of Spencer
Graves <spencer.graves at prodsyse.com>
Sent: Saturday, October 8, 2016 7:03 PM
To: Mark Leeds
Cc: R-devel
Subject: Re: [Rd] optim(?, method=?L-BFGS-B?) stops with an error message while
violating the lower bound

Hi, Mark et al.:


       Thanks, Mark.


       Three comments:


             1.  Rvmmin was one of the methods I tried after Ravi
directed me to optimx.  It returned NAs for essentially everything. See
my email of this subject stamped 4:43 PM Central time = 21:43 UTC.


             2.  It would be interesting to know if the current
algorithm behind optim and optimx with method='L-BFGS-B' incorporates
Morales and Nocedal (2011) 'Remark on ?Algorithm 778: L-BFGS-B: Fortran
Subroutines for Large-Scale Bound Constrained Optimization?'.  I created
this vignette and started this threat hoping that someone on the R Core
team might decide it's worth checking things like that.


             3.  The vignette mentioned below was extracted from a
larger vignette fitting several models that seem to encounter
convergence problems.  I should probably switch to optimx using all the
methods that offers for constrained optimization, including nminb.


       Best Wishes,
       Spencer Graves


On 10/8/2016 5:00 PM, Mark Leeds wrote:
> Hi Spencer: See the link below about L-BFGS-B below because  I had
> problems
> with it a good while back (and I think the link description is the
> cause but I can't prove it )  so  eventually I moved to the  Rvmmin(b)
> package. It's a package but really an algorithm. Rvmmin(b) uses a
> variable-metric algorithm similar to that of L-BFGS-B but without the
> problem below. It's not surprisingly a creation of John Nash and quite
> impressive based on my experience. Just like L-BFGS, it can implement
> box constraints by adding the b.
>
> http://users.eecs.northwestern.edu/~morales/PSfiles/acm-remark.pdf
>
<http://users.eecs.northwestern.edu/%7Emorales/PSfiles/acm-remark.pdf>
>
>
>
>
>
>
>
> On Sat, Oct 8, 2016 at 2:50 PM, Spencer Graves
> <spencer.graves at prodsyse.com <mailto:spencer.graves at
prodsyse.com>> wrote:
>
>     Hello:
>
>
>           The development version of Ecdat on R-Forge contains a
>     vignette in which optim(?, method=?L-BFGS-B?) stops with an error
>     message while violating the lower bound.
>
>
>           To see all the details, try the following:
>
>
>     install.packages("Ecdat",
repos="http://R-Forge.R-project.org
>     <http://R-Forge.R-project.org>")
>
>
>           Then do "help(pac=Ecdat)" -> "User guides,
package vignettes
>     and other documentation" ->
"Ecdat::AverageIncomeModels".
>
>
>           I've found other optimizers that will get around the problem
>     in this case but none that performs as well as optim with many
>     other problems.
>
>
>           Thanks,
>           Spencer Graves
>
>
>     p.s.  I've also tested bobyqa{minqa} or nloptr{nloptr},
>     recommended in a vignette in the lme4 package.  These did better
>     than optim in this example but worse in others I tried.
>
>     ______________________________________________
>     R-devel at r-project.org <mailto:R-devel at r-project.org>
mailing list
>     https://stat.ethz.ch/mailman/listinfo/r-devel
>     <https://stat.ethz.ch/mailman/listinfo/r-devel>
>
>

        [[alternative HTML version deleted]]

______________________________________________
R-devel at r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-devel

>>>>> Spencer Graves <spencer.graves at prodsyse.com>
>>>>>     on Sat, 8 Oct 2016 18:03:43 -0500 writes:
[.............]

    >              2.  It would be interesting to know if the
    > current algorithm behind optim and optimx with
    > method='L-BFGS-B' incorporates Morales and Nocedal (2011)
    > 'Remark on ?Algorithm 778: L-BFGS-B: Fortran Subroutines
    > for Large-Scale Bound Constrained Optimization?'.  I
    > created this vignette and started this threat hoping that
    > someone on the R Core team might decide it's worth
    > checking things like that.

well I hope you mean "thread" rather "threat"  ;-)

I've now looked at the reference above, which is indeed quite
interesting.
	doi 10.1145/2049662.2049669
	--> http://dl.acm.org/citation.cfm?doid=2049662.2049669
A "free" (pre-publication I assume) version of the manuscript is
  http://www.eecs.northwestern.edu/~morales/PSfiles/acm-remark.pdf

The authors, Morales and Nocedal, the 2nd one being one of the
original L-BFGS-B(1997) paper, make two remarks, the 2nd one
about the "machine epsilon" used, and I can assure you that R's
optim() version never suffered from that; we've always been
using a C translation of the fortran code, and then used DBL_EPSILON.
R's (main) source file for that is in .../src/appl/lbfgsb.c, e.g., here
https://svn.r-project.org/R/trunk/src/appl/lbfgsb.c

OTOH, their remark 1 is very relevant and promising faster /
more reliable convergence. 
I'd be "happy" if optim() could gain a new option, say,
"L-BFGS-B-2011"
which would incorporate what they call "modified L-BFGS-B".

However, I did not find published code to go together with their
remark.
Ideally, some of you interested in this, would provide a patch
against the above  lbfgsb.c  file

Martin Maechler,
ETH Zurich

I believe the code can be found here:
http://users.iems.northwestern.edu/~nocedal/lbfgsb.html. Specifically,
lbfgsb.f in version 3.0 starts:

This is a modified version of L-BFGS-B. Minor changes in the updated
c     code appear preceded by a line comment as follows
c
c     c-jlm-jn
c
c     Major changes are described in the accompanying paper:
c
c         Jorge Nocedal and Jose Luis Morales, Remark on "Algorithm 778:
c         L-BFGS-B: Fortran Subroutines for Large-Scale Bound Constrained
c         Optimization"  (2011). To appear in  ACM Transactions on
c         Mathematical Software,
c
c     The paper describes an improvement and a correction to Algorithm 778.
c     It is shown that the performance of the algorithm can be improved
c     significantly by making a relatively simple modication to the subspace
c     minimization phase. The correction concerns an error caused by the use
c     of routine dpmeps to estimate machine precision.


It is released under the New 3-clause BSD license, so porting it to C
for inclusion into R should be OK as long as the i's are dotted and
t's crossed.


Avi

On Mon, Oct 10, 2016 at 5:54 AM, Martin Maechler
<maechler at stat.math.ethz.ch> wrote:
>>>>>> Spencer Graves <spencer.graves at prodsyse.com>
>>>>>>     on Sat, 8 Oct 2016 18:03:43 -0500 writes:
>
> [.............]
>
>     >              2.  It would be interesting to know if the
>     > current algorithm behind optim and optimx with
>     > method='L-BFGS-B' incorporates Morales and Nocedal (2011)
>     > 'Remark on ?Algorithm 778: L-BFGS-B: Fortran Subroutines
>     > for Large-Scale Bound Constrained Optimization?'.  I
>     > created this vignette and started this threat hoping that
>     > someone on the R Core team might decide it's worth
>     > checking things like that.
>
> well I hope you mean "thread" rather "threat"  ;-)
>
> I've now looked at the reference above, which is indeed quite
> interesting.
>         doi 10.1145/2049662.2049669
>         --> http://dl.acm.org/citation.cfm?doid=2049662.2049669
> A "free" (pre-publication I assume) version of the manuscript is
>   http://www.eecs.northwestern.edu/~morales/PSfiles/acm-remark.pdf
>
> The authors, Morales and Nocedal, the 2nd one being one of the
> original L-BFGS-B(1997) paper, make two remarks, the 2nd one
> about the "machine epsilon" used, and I can assure you that
R's
> optim() version never suffered from that; we've always been
> using a C translation of the fortran code, and then used DBL_EPSILON.
> R's (main) source file for that is in .../src/appl/lbfgsb.c, e.g., here
> https://svn.r-project.org/R/trunk/src/appl/lbfgsb.c
>
> OTOH, their remark 1 is very relevant and promising faster /
> more reliable convergence.
> I'd be "happy" if optim() could gain a new option, say,
"L-BFGS-B-2011"
> which would incorporate what they call "modified L-BFGS-B".
>
> However, I did not find published code to go together with their
> remark.
> Ideally, some of you interested in this, would provide a patch
> against the above  lbfgsb.c  file
>
> Martin Maechler,
> ETH Zurich
>
> ______________________________________________
> R-devel at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-devel