From aimcleod at uwo.ca  Fri Oct 28 19:02:24 2005
From: aimcleod at uwo.ca (aimcleod@uwo.ca)
Date: Fri, 28 Oct 2005 19:02:24 +0200 (CEST)
Subject: [Rd] optim possible bug "L-BFGS-B" (PR#8261)
Message-ID: <20051028170224.0612522151@slim.kubism.ku.dk>

Full_Name: Ian McLeod
Version: 2.10
OS: windows
Submission from: (NULL) (129.100.76.136)



Subject:  Apparent bug in optim with "L-BFGS-B".


I found that optim works most of the time but sometimes produced an incorrect
answer.   In order to document what is happening, I tried to simplify by
re-writing the objective function in the optimization.  The new objective
function when evaluated gives numerically identical results except that optim
now works!!

Below is the output from optim for the two cases.  There should not be a
difference.  This output is followed by a comparison of function values for the
two methods for phis<-seq(-0.99,0.99,length=200).  In all these cases, the
function values do not appear to differ significantly.
 

Perhaps someone familar with how this algorithm works exactly, can see what is
happening.

If you would like more details (R code etc), please contact me:
aimcleod at uwo.ca


###################################################################
##Case 1.
##original objective function
## optim produces incorrect answer
###################################################################
> optim(0, fn=function(b) -LLarma(z,b,0), method="L-BFGS-B", lower=-0.99,
upper=0.99, control=list(trace=6))
N = 1, M = 5 machine precision = 2.22045e-016
L = -0.99 
X0 = 0 
U = 0.99 
At X0, 0 variables are exactly at the bounds
At iterate     0  f=       619.18  |proj g|=         0.99
Iteration     0

---------------- CAUCHY entered-------------------

There are 1  breakpoints

Piece      1 f1, f2 at start point -4.5485e+003 4.5485e+003
Distance to the next break point =  1.4679e-002
Distance to the stationary point =  1.0000e+000
Variable  1  is fixed.
Cauchy X =  0.99 

---------------- exit CAUCHY----------------------

0  variables are free at GCP on iteration 1
LINE SEARCH 1 times; norm of step = 0.417877
X = 0.417877 
G = -47.1062 
Iteration     1

---------------- CAUCHY entered-------------------

There are 1  breakpoints

Piece      1 f1, f2 at start point -2.2190e+003 1.0799e+005
Distance to the next break point =  1.2145e-002
Distance to the stationary point =  2.0548e-002
Variable  1  is fixed.
Cauchy X =  0.99 

---------------- exit CAUCHY----------------------

0 variables leave; 0 variables enter
0  variables are free at GCP on iteration 2
LINE SEARCH 1 times; norm of step = 0.299499
X = 0.717376 
G = 1.91222 
Iteration     2

---------------- CAUCHY entered-------------------

There are 1  breakpoints

Piece      1 f1, f2 at start point -3.6566e+000 5.9847e+002
Distance to the next break point =  8.9288e-001
Distance to the stationary point =  6.1099e-003

GCP found in this segment
Piece      1 f1, f2 at start point -3.6566e+000 5.9847e+002
Distance to the stationary point =  6.1099e-003
Cauchy X =  0.705692 

---------------- exit CAUCHY----------------------

Variable 1 enters the set of free variables
0 variables leave; 1 variables enter
1  variables are free at GCP on iteration 3
Nonpositive definiteness in Cholesky factorization in formk;
   refresh the lbfgs memory and restart the iteration.
Iteration     2

---------------- CAUCHY entered-------------------

There are 1  breakpoints

Piece      1 f1, f2 at start point -3.6566e+000 3.6566e+000
Distance to the next break point =  8.9288e-001
Distance to the stationary point =  1.0000e+000
Variable  1  is fixed.
Cauchy X =  -0.99 

---------------- exit CAUCHY----------------------

Variable 1 leaves the set of free variables
0  variables are free at GCP on iteration 3
LINE SEARCH 0 times; norm of step = 1.70738
X = -0.99 
G = -95.712 

iterations 3
function evaluations 6
segments explored during Cauchy searches 4
BFGS updates skipped 0
active bounds at final generalized Cauchy point 1
norm of the final projected gradient 1.98
final function value 679.48

X = -0.99 
F = 679.48
final  value 679.479918 
converged
$par
[1] -0.99

$value
[1] 679.4799

$counts
function gradient 
       6        6 

$convergence
[1] 0

$message
[1] "CONVERGENCE: REL_REDUCTION_OF_F <= FACTR*EPSMCH"


##############################################################
## Case 2
## I simplified the objective function for this special case.
## It seems to give numerically identical results with the previous
## one but the answers are different.
##############################################################
> optim(0.0, fn=Entropy, method="L-BFGS-B", lower=-0.99, upper=0.99,
control=list(trace=6))
N = 1, M = 5 machine precision = 2.22045e-016
L = -0.99 
X0 = 0 
U = 0.99 
At X0, 0 variables are exactly at the bounds
At iterate     0  f=       619.18  |proj g|=         0.99
Iteration     0

---------------- CAUCHY entered-------------------

There are 1  breakpoints

Piece      1 f1, f2 at start point -4.5485e+003 4.5485e+003
Distance to the next break point =  1.4679e-002
Distance to the stationary point =  1.0000e+000
Variable  1  is fixed.
Cauchy X =  0.99 

---------------- exit CAUCHY----------------------

0  variables are free at GCP on iteration 1
LINE SEARCH 1 times; norm of step = 0.417877
X = 0.417877 
G = -47.1062 
Iteration     1

---------------- CAUCHY entered-------------------

There are 1  breakpoints

Piece      1 f1, f2 at start point -2.2190e+003 1.0799e+005
Distance to the next break point =  1.2145e-002
Distance to the stationary point =  2.0548e-002
Variable  1  is fixed.
Cauchy X =  0.99 

---------------- exit CAUCHY----------------------

0 variables leave; 0 variables enter
0  variables are free at GCP on iteration 2
LINE SEARCH 1 times; norm of step = 0.299499
X = 0.717376 
G = 1.91222 
Iteration     2

---------------- CAUCHY entered-------------------

There are 1  breakpoints

Piece      1 f1, f2 at start point -3.6566e+000 5.9847e+002
Distance to the next break point =  8.9288e-001
Distance to the stationary point =  6.1099e-003

GCP found in this segment
Piece      1 f1, f2 at start point -3.6566e+000 5.9847e+002
Distance to the stationary point =  6.1099e-003
Cauchy X =  0.705692 

---------------- exit CAUCHY----------------------

Variable 1 enters the set of free variables
0 variables leave; 1 variables enter
1  variables are free at GCP on iteration 3
Nonpositive definiteness in Cholesky factorization in formk;
   refresh the lbfgs memory and restart the iteration.
Iteration     2

---------------- CAUCHY entered-------------------

There are 1  breakpoints

Piece      1 f1, f2 at start point -3.6566e+000 3.6566e+000
Distance to the next break point =  8.9288e-001
Distance to the stationary point =  1.0000e+000
Variable  1  is fixed.
Cauchy X =  -0.99 

---------------- exit CAUCHY----------------------

Variable 1 leaves the set of free variables
0  variables are free at GCP on iteration 3
LINE SEARCH 2 times; norm of step = 0.00986778
X = 0.707508 
G = 7.19684e-005 
Iteration     3

---------------- CAUCHY entered-------------------

There are 1  breakpoints

Piece      1 f1, f2 at start point -5.1795e-009 1.0037e-006
Distance to the next break point =  2.3587e+004
Distance to the stationary point =  5.1606e-003

GCP found in this segment
Piece      1 f1, f2 at start point -5.1795e-009 1.0037e-006
Distance to the stationary point =  5.1606e-003
Cauchy X =  0.707508 

---------------- exit CAUCHY----------------------

Variable 1 enters the set of free variables
0 variables leave; 1 variables enter
1  variables are free at GCP on iteration 4
LINE SEARCH 0 times; norm of step = 3.71399e-007
X = 0.707508 
G = 9.24842e-008 

iterations 4
function evaluations 9
segments explored during Cauchy searches 5
BFGS updates skipped 0
active bounds at final generalized Cauchy point 0
norm of the final projected gradient 9.24842e-008
final function value 586.19

X = 0.707508 
F = 586.19
final  value 586.190487 
converged
$par
[1] 0.7075076

$value
[1] 586.1905

$counts
function gradient 
       9        9 

$convergence
[1] 0

$message
[1] "CONVERGENCE: REL_REDUCTION_OF_F <= FACTR*EPSMCH"

> 

###################################################################
##  Comparison of function values
###################################################################
> ansCompare
                phi 1stMethod 2ndMethod    difference
  [1,] -0.990000000  679.4799  679.4799  9.094947e-13
  [2,] -0.980050251  678.6556  678.6556  0.000000e+00
  [3,] -0.970100503  677.9723  677.9723 -3.410605e-13
  [4,] -0.960150754  677.3457  677.3457  1.136868e-13
  [5,] -0.950201005  676.7493  676.7493  1.136868e-13
  [6,] -0.940251256  676.1713  676.1713  3.410605e-13
  [7,] -0.930301508  675.6054  675.6054 -1.136868e-13
  [8,] -0.920351759  675.0477  675.0477  2.273737e-13
  [9,] -0.910402010  674.4959  674.4959  2.273737e-13
 [10,] -0.900452261  673.9483  673.9483  1.136868e-13
 [11,] -0.890502513  673.4037  673.4037 -2.273737e-13
 [12,] -0.880552764  672.8611  672.8611  1.136868e-13
 [13,] -0.870603015  672.3200  672.3200  1.136868e-13
 [14,] -0.860653266  671.7797  671.7797 -1.136868e-13
 [15,] -0.850703518  671.2399  671.2399  2.273737e-13
 [16,] -0.840753769  670.7003  670.7003 -2.273737e-13
 [17,] -0.830804020  670.1605  670.1605  0.000000e+00
 [18,] -0.820854271  669.6203  669.6203  0.000000e+00
 [19,] -0.810904523  669.0796  669.0796  0.000000e+00
 [20,] -0.800954774  668.5381  668.5381 -1.136868e-13
 [21,] -0.791005025  667.9957  667.9957 -1.136868e-13
 [22,] -0.781055276  667.4523  667.4523  0.000000e+00
 [23,] -0.771105528  666.9078  666.9078  0.000000e+00
 [24,] -0.761155779  666.3620  666.3620 -1.136868e-13
 [25,] -0.751206030  665.8149  665.8149  1.136868e-13
 [26,] -0.741256281  665.2665  665.2665  0.000000e+00
 [27,] -0.731306533  664.7166  664.7166  0.000000e+00
 [28,] -0.721356784  664.1651  664.1651 -1.136868e-13
 [29,] -0.711407035  663.6121  663.6121  0.000000e+00
 [30,] -0.701457286  663.0575  663.0575  1.136868e-13
 [31,] -0.691507538  662.5012  662.5012 -1.136868e-13
 [32,] -0.681557789  661.9432  661.9432  0.000000e+00
 [33,] -0.671608040  661.3834  661.3834 -1.136868e-13
 [34,] -0.661658291  660.8218  660.8218 -2.273737e-13
 [35,] -0.651708543  660.2584  660.2584 -2.273737e-13
 [36,] -0.641758794  659.6932  659.6932  1.136868e-13
 [37,] -0.631809045  659.1261  659.1261 -1.136868e-13
 [38,] -0.621859296  658.5570  658.5570  0.000000e+00
 [39,] -0.611909548  657.9861  657.9861  0.000000e+00
 [40,] -0.601959799  657.4132  657.4132  1.136868e-13
 [41,] -0.592010050  656.8383  656.8383  0.000000e+00
 [42,] -0.582060302  656.2614  656.2614  1.136868e-13
 [43,] -0.572110553  655.6825  655.6825 -1.136868e-13
 [44,] -0.562160804  655.1016  655.1016  0.000000e+00
 [45,] -0.552211055  654.5186  654.5186 -1.136868e-13
 [46,] -0.542261307  653.9336  653.9336 -1.136868e-13
 [47,] -0.532311558  653.3465  653.3465  0.000000e+00
 [48,] -0.522361809  652.7574  652.7574  0.000000e+00
 [49,] -0.512412060  652.1661  652.1661 -1.136868e-13
 [50,] -0.502462312  651.5728  651.5728  0.000000e+00
 [51,] -0.492512563  650.9774  650.9774  0.000000e+00
 [52,] -0.482562814  650.3799  650.3799 -1.136868e-13
 [53,] -0.472613065  649.7802  649.7802  0.000000e+00
 [54,] -0.462663317  649.1785  649.1785  0.000000e+00
 [55,] -0.452713568  648.5747  648.5747 -1.136868e-13
 [56,] -0.442763819  647.9687  647.9687  0.000000e+00
 [57,] -0.432814070  647.3607  647.3607 -1.136868e-13
 [58,] -0.422864322  646.7505  646.7505  0.000000e+00
 [59,] -0.412914573  646.1382  646.1382  0.000000e+00
 [60,] -0.402964824  645.5239  645.5239  0.000000e+00
 [61,] -0.393015075  644.9074  644.9074  0.000000e+00
 [62,] -0.383065327  644.2889  644.2889  0.000000e+00
 [63,] -0.373115578  643.6683  643.6683  1.136868e-13
 [64,] -0.363165829  643.0456  643.0456  0.000000e+00
 [65,] -0.353216080  642.4209  642.4209  0.000000e+00
 [66,] -0.343266332  641.7942  641.7942 -1.136868e-13
 [67,] -0.333316583  641.1654  641.1654  0.000000e+00
 [68,] -0.323366834  640.5346  640.5346  0.000000e+00
 [69,] -0.313417085  639.9019  639.9019  0.000000e+00
 [70,] -0.303467337  639.2672  639.2672  1.136868e-13
 [71,] -0.293517588  638.6305  638.6305  0.000000e+00
 [72,] -0.283567839  637.9920  637.9920  1.136868e-13
 [73,] -0.273618090  637.3515  637.3515  1.136868e-13
 [74,] -0.263668342  636.7093  636.7093  1.136868e-13
 [75,] -0.253718593  636.0651  636.0651  0.000000e+00
 [76,] -0.243768844  635.4192  635.4192  0.000000e+00
 [77,] -0.233819095  634.7716  634.7716 -1.136868e-13
 [78,] -0.223869347  634.1222  634.1222  1.136868e-13
 [79,] -0.213919598  633.4712  633.4712  0.000000e+00
 [80,] -0.203969849  632.8185  632.8185  0.000000e+00
 [81,] -0.194020101  632.1642  632.1642  1.136868e-13
 [82,] -0.184070352  631.5084  631.5084 -1.136868e-13
 [83,] -0.174120603  630.8512  630.8512  0.000000e+00
 [84,] -0.164170854  630.1925  630.1925  0.000000e+00
 [85,] -0.154221106  629.5324  629.5324  1.136868e-13
 [86,] -0.144271357  628.8710  628.8710  0.000000e+00
 [87,] -0.134321608  628.2084  628.2084  0.000000e+00
 [88,] -0.124371859  627.5446  627.5446  1.136868e-13
 [89,] -0.114422111  626.8797  626.8797  1.136868e-13
 [90,] -0.104472362  626.2138  626.2138 -1.136868e-13
 [91,] -0.094522613  625.5469  625.5469  0.000000e+00
 [92,] -0.084572864  624.8792  624.8792  0.000000e+00
 [93,] -0.074623116  624.2107  624.2107  0.000000e+00
 [94,] -0.064673367  623.5415  623.5415  0.000000e+00
 [95,] -0.054723618  622.8717  622.8717 -1.136868e-13
 [96,] -0.044773869  622.2014  622.2014  0.000000e+00
 [97,] -0.034824121  621.5308  621.5308  0.000000e+00
 [98,] -0.024874372  620.8599  620.8599  0.000000e+00
 [99,] -0.014924623  620.1888  620.1888 -1.136868e-13
[100,] -0.004974874  619.5177  619.5177  1.136868e-13
[101,]  0.004974874  618.8466  618.8466  0.000000e+00
[102,]  0.014924623  618.1758  618.1758 -1.136868e-13
[103,]  0.024874372  617.5054  617.5054  0.000000e+00
[104,]  0.034824121  616.8354  616.8354  0.000000e+00
[105,]  0.044773869  616.1661  616.1661  0.000000e+00
[106,]  0.054723618  615.4975  615.4975 -1.136868e-13
[107,]  0.064673367  614.8300  614.8300  1.136868e-13
[108,]  0.074623116  614.1635  614.1635  0.000000e+00
[109,]  0.084572864  613.4984  613.4984  0.000000e+00
[110,]  0.094522613  612.8347  612.8347  0.000000e+00
[111,]  0.104472362  612.1727  612.1727 -1.136868e-13
[112,]  0.114422111  611.5125  611.5125  1.136868e-13
[113,]  0.124371859  610.8544  610.8544  1.136868e-13
[114,]  0.134321608  610.1986  610.1986  0.000000e+00
[115,]  0.144271357  609.5452  609.5452  1.136868e-13
[116,]  0.154221106  608.8945  608.8945  1.136868e-13
[117,]  0.164170854  608.2468  608.2468  0.000000e+00
[118,]  0.174120603  607.6022  607.6022  1.136868e-13
[119,]  0.184070352  606.9609  606.9609 -1.136868e-13
[120,]  0.194020101  606.3234  606.3234  1.136868e-13
[121,]  0.203969849  605.6897  605.6897  0.000000e+00
[122,]  0.213919598  605.0602  605.0602  0.000000e+00
[123,]  0.223869347  604.4352  604.4352  1.136868e-13
[124,]  0.233819095  603.8148  603.8148 -1.136868e-13
[125,]  0.243768844  603.1995  603.1995  0.000000e+00
[126,]  0.253718593  602.5895  602.5895  0.000000e+00
[127,]  0.263668342  601.9851  601.9851  0.000000e+00
[128,]  0.273618090  601.3866  601.3866  0.000000e+00
[129,]  0.283567839  600.7943  600.7943  1.136868e-13
[130,]  0.293517588  600.2086  600.2086  0.000000e+00
[131,]  0.303467337  599.6297  599.6297  0.000000e+00
[132,]  0.313417085  599.0581  599.0581  0.000000e+00
[133,]  0.323366834  598.4941  598.4941  0.000000e+00
[134,]  0.333316583  597.9379  597.9379  0.000000e+00
[135,]  0.343266332  597.3900  597.3900  0.000000e+00
[136,]  0.353216080  596.8507  596.8507  0.000000e+00
[137,]  0.363165829  596.3204  596.3204 -1.136868e-13
[138,]  0.373115578  595.7994  595.7994  0.000000e+00
[139,]  0.383065327  595.2882  595.2882  0.000000e+00
[140,]  0.393015075  594.7870  594.7870  0.000000e+00
[141,]  0.402964824  594.2963  594.2963  0.000000e+00
[142,]  0.412914573  593.8164  593.8164 -1.136868e-13
[143,]  0.422864322  593.3477  593.3477  0.000000e+00
[144,]  0.432814070  592.8906  592.8906 -1.136868e-13
[145,]  0.442763819  592.4455  592.4455 -1.136868e-13
[146,]  0.452713568  592.0128  592.0128 -1.136868e-13
[147,]  0.462663317  591.5928  591.5928  0.000000e+00
[148,]  0.472613065  591.1859  591.1859 -1.136868e-13
[149,]  0.482562814  590.7924  590.7924 -1.136868e-13
[150,]  0.492512563  590.4128  590.4128 -1.136868e-13
[151,]  0.502462312  590.0474  590.0474  0.000000e+00
[152,]  0.512412060  589.6965  589.6965  0.000000e+00
[153,]  0.522361809  589.3606  589.3606  0.000000e+00
[154,]  0.532311558  589.0398  589.0398 -1.136868e-13
[155,]  0.542261307  588.7347  588.7347  0.000000e+00
[156,]  0.552211055  588.4454  588.4454 -2.273737e-13
[157,]  0.562160804  588.1724  588.1724 -1.136868e-13
[158,]  0.572110553  587.9159  587.9159 -1.136868e-13
[159,]  0.582060302  587.6761  587.6761  0.000000e+00
[160,]  0.592010050  587.4534  587.4534  0.000000e+00
[161,]  0.601959799  587.2481  587.2481  1.136868e-13
[162,]  0.611909548  587.0603  587.0603  0.000000e+00
[163,]  0.621859296  586.8904  586.8904 -1.136868e-13
[164,]  0.631809045  586.7384  586.7384 -1.136868e-13
[165,]  0.641758794  586.6047  586.6047  1.136868e-13
[166,]  0.651708543  586.4894  586.4894  0.000000e+00
[167,]  0.661658291  586.3927  586.3927 -1.136868e-13
[168,]  0.671608040  586.3146  586.3146  0.000000e+00
[169,]  0.681557789  586.2555  586.2555 -1.136868e-13
[170,]  0.691507538  586.2152  586.2152  0.000000e+00
[171,]  0.701457286  586.1940  586.1940  1.136868e-13
[172,]  0.711407035  586.1920  586.1920  0.000000e+00
[173,]  0.721356784  586.2091  586.2091  0.000000e+00
[174,]  0.731306533  586.2454  586.2454  0.000000e+00
[175,]  0.741256281  586.3010  586.3010  0.000000e+00
[176,]  0.751206030  586.3758  586.3758  1.136868e-13
[177,]  0.761155779  586.4698  586.4698 -1.136868e-13
[178,]  0.771105528  586.5831  586.5831  1.136868e-13
[179,]  0.781055276  586.7156  586.7156  1.136868e-13
[180,]  0.791005025  586.8673  586.8673 -1.136868e-13
[181,]  0.800954774  587.0380  587.0380 -1.136868e-13
[182,]  0.810904523  587.2278  587.2278  1.136868e-13
[183,]  0.820854271  587.4366  587.4366  1.136868e-13
[184,]  0.830804020  587.6644  587.6644  1.136868e-13
[185,]  0.840753769  587.9111  587.9111  0.000000e+00
[186,]  0.850703518  588.1767  588.1767  1.136868e-13
[187,]  0.860653266  588.4613  588.4613  0.000000e+00
[188,]  0.870603015  588.7649  588.7649 -1.136868e-13
[189,]  0.880552764  589.0876  589.0876 -3.410605e-13
[190,]  0.890502513  589.4296  589.4296 -1.136868e-13
[191,]  0.900452261  589.7914  589.7914  0.000000e+00
[192,]  0.910402010  590.1734  590.1734  1.136868e-13
[193,]  0.920351759  590.5766  590.5766  2.273737e-13
[194,]  0.930301508  591.0022  591.0022  1.136868e-13
[195,]  0.940251256  591.4524  591.4524 -2.273737e-13
[196,]  0.950201005  591.9306  591.9306  0.000000e+00
[197,]  0.960150754  592.4426  592.4426  2.273737e-13
[198,]  0.970100503  593.0001  593.0001  1.136868e-13
[199,]  0.980050251  593.6290  593.6290 -1.136868e-13
[200,]  0.990000000  594.4134  594.4134 -3.410605e-13



[Rd] optim possible bug "L-BFGS-B" (PR#8261)
aimcleod@uwo.ca