Sandia National Laboratories

Ticket #19 (closed defect: fixed)

Opened 2 years ago

Last modified 2 years ago

LBFGS two-loop recursion bug

Reported by: dmdunla Owned by: dmdunla
Priority: blocker Milestone: Poblano 1.0
Component: Poblano Version: 1.0
Keywords: lbfgs Cc:

Description

This was reported by Jennifer Erway:

It looks to me like the matlab code lbfgs.m in the Poblano toolbox v1.0 isn't quite correct. In it, there's the following to update the stored vectors:

S = [sk S(:,1:end-1)];
Y = [yk Y(:,1:end-1)];
rho = [rhok rho(1:end-1)];

Your newest sk, yk, and rho are stored in the first entry of each array; the oldest vectors are at the end.

In the first part of the two-loop recursion, I think you want to process the newest vectors first, which in this case appear at the beginning of the vector and not at the end of the vector; however, it looks to me like you are actually processing the oldest vectors first. Similarly, the second half of the two-loop recursion should process the oldest vectors first and the newest last; however, it looks like the code is doing the opposite. (I believe the Sandia Report (pdf) is correct, but it looks to me that the code isn't doing this.) I think the fix is to change the two-loop counters to count in the opposite directions than they current do or change the way that S, Y and rho are updated.

Change History

comment:1 Changed 2 years ago by dmdunla

  • Status changed from new to closed
  • Resolution set to fixed

Tammy and Danny verified that the code was incorrect and made the change to reflect Nocedal and Wright's.

Improved perfomance on the test problems:

Here are the results for the MINPACK-2 text set using the corrected LMBFGS and original. There are definite improvements in terms of convergence.

More to follow once I complete all of the analysis.

--Danny

poblano_uncprobs_test('lbfgs')

Problem Exit Flag Iters FuncEvals? F_comp F_star Error


1 0 19 71 2.6803e-21 0.0000e+00 2.6803e-21
2 0 8 25 4.8984e+01 4.8984e+01 7.2528e-16
3 3 95 355 5.5692e-22 0.0000e+00 5.5692e-22
4 0 10 23 0.0000e+00 0.0000e+00 0.0000e+00
5 0 11 32 3.8901e-29 0.0000e+00 3.8901e-29
6 0 1 8 2.0200e+03 1.2436e+02 1.5243e+01 *
7 0 21 60 1.3486e-21 0.0000e+00 1.3486e-21
8 0 11 33 8.2149e-03 8.2149e-03 3.2960e-17
9 0 3 8 1.1279e-08 1.1279e-08 2.7696e-14

10 3 311 1099 8.7946e+01 8.7946e+01 6.5879e-13
11 0 1 2 3.8500e-02 0.0000e+00 3.8500e-02 *
12 0 14 50 2.2918e-19 0.0000e+00 2.2918e-19
13 0 29 87 3.4277e-15 0.0000e+00 3.4277e-15
14 0 39 115 8.9029e-23 0.0000e+00 8.9029e-23
15 0 17 50 3.0751e-04 3.0751e-04 3.9615e-10
16 0 15 63 8.5822e+04 8.5822e+04 4.3537e-09
17 0 62 203 5.4649e-05 5.4649e-05 9.7483e-13
18 0 30 77 5.6556e-03 0.0000e+00 5.6556e-03 *
19 3 264 784 4.0138e-02 4.0138e-02 2.9355e-10
20 3 1270 3297 1.3998e-06 1.4017e-06 1.9787e-09
21 0 19 71 1.3402e-20 0.0000e+00 1.3402e-20
22 0 29 87 3.4277e-15 0.0000e+00 3.4277e-15
23 0 89 334 2.2500e-05 2.2500e-05 2.4991e-11
24 0 224 738 9.3763e-06 9.3763e-06 7.3557e-15
25 0 4 22 1.4035e-23 0.0000e+00 1.4035e-23
26 0 32 78 2.7951e-05 2.7951e-05 2.1883e-13
27 0 8 26 1.9956e-27 0.0000e+00 1.9956e-27
28 3 63 137 1.2771e-16 0.0000e+00 1.2771e-16
29 0 7 15 4.0462e-21 0.0000e+00 4.0462e-21
30 3 25 54 2.5304e-18 0.0000e+00 2.5304e-18
31 3 24 76 3.0573e+00 0.0000e+00 3.0573e+00 *
32 0 2 4 1.0000e+01 1.0000e+01 7.1054e-16
33 0 2 4 4.6341e+00 4.6341e+00 0.0000e+00
34 0 2 4 6.1351e+00 6.1351e+00 0.0000e+00

poblano_uncprobs_test('lbfgs_orig')

Problem Exit Flag Iters FuncEvals? F_comp F_star Error


1 3 43 145 1.5549e-20 0.0000e+00 1.5549e-20
2 3 14 73 4.8984e+01 4.8984e+01 4.3517e-16
3 3 206 730 5.8432e-20 0.0000e+00 5.8432e-20
4 0 14 29 7.8886e-31 0.0000e+00 7.8886e-31
5 0 20 55 1.2898e-24 0.0000e+00 1.2898e-24
6 0 1 8 2.0200e+03 1.2436e+02 1.5243e+01 *
7 0 40 103 8.6454e-28 0.0000e+00 8.6454e-28
8 0 25 59 8.2149e-03 8.2149e-03 2.4286e-17
9 0 3 8 1.1279e-08 1.1279e-08 2.7696e-14

10 3 705 2406 8.7946e+01 8.7946e+01 4.2594e-13
11 0 1 2 3.8500e-02 0.0000e+00 3.8500e-02 *
12 0 24 76 3.2973e-20 0.0000e+00 3.2973e-20
13 0 65 135 4.0056e-16 0.0000e+00 4.0056e-16
14 3 66 187 1.2955e-19 0.0000e+00 1.2955e-19
15 0 28 71 3.0751e-04 3.0751e-04 3.9615e-10
16 3 22 96 8.5822e+04 8.5822e+04 4.3537e-09
17 3 221 602 5.4649e-05 5.4649e-05 9.7483e-13
18 0 53 139 5.6556e-03 0.0000e+00 5.6556e-03 *
19 3 267 713 4.0138e-02 4.0138e-02 2.9355e-10
20 3 5118 10752 1.3998e-06 1.4017e-06 1.9194e-09
21 0 43 145 7.7745e-20 0.0000e+00 7.7745e-20
22 0 65 135 4.0056e-16 0.0000e+00 4.0056e-16
23 0 217 785 2.2500e-05 2.2500e-05 2.4991e-11
24 0 454 1449 9.3763e-06 9.3763e-06 7.3563e-15
25 0 4 31 1.4730e-29 0.0000e+00 1.4730e-29
26 0 39 95 2.7951e-05 2.7951e-05 2.1880e-13
27 0 15 37 9.7350e-24 0.0000e+00 9.7350e-24
28 3 67 140 1.2313e-16 0.0000e+00 1.2313e-16
29 0 6 14 1.6306e-17 0.0000e+00 1.6306e-17
30 3 25 54 1.5036e-17 0.0000e+00 1.5036e-17
31 3 27 100 3.0573e+00 0.0000e+00 3.0573e+00 *
32 0 2 4 1.0000e+01 1.0000e+01 7.1054e-16
33 0 2 4 4.6341e+00 4.6341e+00 0.0000e+00
34 0 2 4 6.1351e+00 6.1351e+00 0.0000e+00

Note: See TracTickets for help on using tickets.