Line data Source code
1 : #include "TestLBFGSBuffer.h"
2 : #include "LBFGSBuffer.h"
3 : #include <iostream>
4 : #include <cmath>
5 :
6 1 : CPPUNIT_TEST_SUITE_REGISTRATION(TestLBFGSBuffer);
7 : #define DOUBLES_EQUAL_DELTA 1e-8
8 :
9 5 : TestLBFGSBuffer::TestLBFGSBuffer() {
10 5 : }
11 :
12 10 : TestLBFGSBuffer::~TestLBFGSBuffer() {
13 10 : }
14 :
15 5 : void TestLBFGSBuffer::setUp() {
16 5 : }
17 :
18 5 : void TestLBFGSBuffer::tearDown() {
19 5 : }
20 :
21 1 : void TestLBFGSBuffer::testPush1() {
22 1 : size_t n = 10;
23 1 : size_t mem = 3;
24 1 : LBFGSBuffer * buffer = new LBFGSBuffer(n, mem);
25 :
26 1 : Matrix y(n, 1);
27 2 : Matrix s(n, 1);
28 :
29 11 : for (size_t j = 0; j < n; j++) {
30 10 : y[j] = 1.0;
31 10 : s[j] = -1.0;
32 : }
33 :
34 11 : for (size_t i = 0; i < 10; i++) {
35 : int status;
36 10 : y *= 2.0;
37 10 : s *= -1.0;
38 10 : status = buffer->push(&s, &y);
39 10 : _ASSERT(ForBESUtils::is_status_ok(status));
40 :
41 : // check whether current sk is correctly buffered
42 10 : Matrix * buffS = buffer->get_S();
43 10 : Matrix s_curr = MatrixFactory::ShallowSubVector(*buffS, buffer->get_k_minus_j(0));
44 10 : _ASSERT_EQ(s_curr, s);
45 :
46 : // check whether current yk is correctly buffered
47 10 : Matrix * buffY = buffer->get_Y();
48 20 : Matrix curry = MatrixFactory::ShallowSubVector(*buffY, buffer->get_k_minus_j(0));
49 10 : _ASSERT_EQ(curry, y);
50 :
51 20 : Matrix sy = s*y;
52 10 : _ASSERT_NUM_EQ(sy[0], buffer->get_Ys()->get(buffer->cursor(), 0), 1e-9);
53 10 : }
54 :
55 2 : delete buffer;
56 1 : }
57 :
58 1 : void TestLBFGSBuffer::testPush2() {
59 1 : size_t n = 30;
60 1 : size_t mem = 3;
61 1 : LBFGSBuffer * buffer = new LBFGSBuffer(n, mem);
62 :
63 1 : Matrix y1 = MatrixFactory::MakeRandomMatrix(n, 1, 0.0, 1.0);
64 2 : Matrix y2 = MatrixFactory::MakeRandomMatrix(n, 1, 0.0, 1.0);
65 2 : Matrix y3 = MatrixFactory::MakeRandomMatrix(n, 1, 0.0, 1.0);
66 2 : Matrix y4 = MatrixFactory::MakeRandomMatrix(n, 1, 0.0, 1.0);
67 :
68 2 : Matrix s1 = MatrixFactory::MakeRandomMatrix(n, 1, 0.0, 1.0);
69 2 : Matrix s2 = MatrixFactory::MakeRandomMatrix(n, 1, 0.0, 1.0);
70 2 : Matrix s3 = MatrixFactory::MakeRandomMatrix(n, 1, 0.0, 1.0);
71 2 : Matrix s4 = MatrixFactory::MakeRandomMatrix(n, 1, 0.0, 1.0);
72 :
73 1 : buffer->push(&s1, &y1);
74 1 : buffer->push(&s2, &y2);
75 1 : buffer->push(&s3, &y3);
76 1 : buffer->push(&s4, &y4);
77 :
78 1 : Matrix * buffS = buffer->get_S();
79 2 : Matrix s_temp = MatrixFactory::ShallowSubVector(*buffS, buffer->get_k_minus_j(0));
80 1 : _ASSERT_EQ(s4, s_temp);
81 :
82 1 : s_temp = MatrixFactory::ShallowSubVector(*buffS, buffer->get_k_minus_j(1));
83 1 : _ASSERT_EQ(s3, s_temp);
84 :
85 1 : s_temp = MatrixFactory::ShallowSubVector(*buffS, buffer->get_k_minus_j(2));
86 1 : _ASSERT_EQ(s2, s_temp);
87 :
88 2 : Matrix sy3 = s3*y3;
89 2 : Matrix sy2 = s2*y2;
90 1 : _ASSERT_NUM_EQ(sy2[0], buffer->get_Ys()->get(buffer->get_k_minus_j(2), 0), 1e-8);
91 1 : _ASSERT_NUM_EQ(sy3[0], buffer->get_Ys()->get(buffer->get_k_minus_j(1), 0), 1e-8);
92 :
93 8 : for (size_t j = 3; j < 10; j++)
94 7 : _ASSERT_EQ(LBFGSBuffer::LBFGS_BUFFER_EOB, buffer->get_k_minus_j(j));
95 :
96 2 : delete buffer;
97 1 : }
98 :
99 1 : void TestLBFGSBuffer::testUpdate() {
100 1 : std::srand(static_cast<unsigned long> (1433291l));
101 :
102 1 : size_t n = 10;
103 1 : size_t mem = 3;
104 1 : LBFGSBuffer * buffer = new LBFGSBuffer(n, mem);
105 :
106 1 : Matrix q = MatrixFactory::MakeRandomMatrix(n, 1, 0.0, 1.0);
107 2 : Matrix r;
108 :
109 1 : double H0 = 1.0;
110 1 : buffer->update(&q, &r, H0);
111 :
112 : // the value of Hk0 does not depend of the whole history stored in the
113 : // buffer - it only depends on y_{k-1} and s_{k-}
114 3 : for (size_t j = 0; j < 2; j++) {
115 6 : for (size_t i = 0; i < 2; i++) {
116 : double m = (j == 0)
117 : ? 12.34
118 4 : : ((i == 2) ? 45.33 : 0.0);
119 4 : Matrix yi = MatrixFactory::MakeRandomMatrix(n, 1, m, 1.0);
120 8 : Matrix si = MatrixFactory::MakeRandomMatrix(n, 1, m, 1.0);
121 4 : buffer->push(&si, &yi);
122 4 : buffer->update(&q, &r, H0);
123 4 : if (j == 0) {
124 2 : Matrix * alpha = buffer -> get_alphas();
125 2 : if (i == 0) {
126 1 : _ASSERT_NUM_EQ(0.0, (*alpha)[1], 1e-9);
127 1 : _ASSERT_NUM_EQ(0.0, (*alpha)[2], 1e-9);
128 1 : } else if (i == 1) {
129 1 : _ASSERT_NUM_EQ(0.0, (*alpha)[2], 1e-9);
130 : }
131 : }
132 4 : _ASSERT(r.norm_fro_sq() > 0.1);
133 4 : }
134 : }
135 :
136 2 : delete buffer;
137 1 : }
138 :
139 1 : void TestLBFGSBuffer::testTwoLoopQuadratic() {
140 1 : size_t n = 10;
141 : int status;
142 : double dirs[][10] = {
143 : {-3.476000000000000e+01, -1.367700000000000e+01, 2.961000000000000e+00, 3.756000000000000e+00, -5.618000000000001e+00,
144 : -1.571000000000000e+00, -4.121000000000000e+00, -3.709000000000000e+00, 4.010000000000000e-01, 7.639999999999999e+00},
145 : {-6.861170733797232e-01, -1.661270665201917e+00, 2.217225828759783e-01, 5.615134140894827e-01, -1.922426760799171e-01,
146 : -8.961101045874649e-02, -3.044802963260585e-01, -1.996235459345302e-01, 1.267604425710271e-01, 3.360845247013288e-01},
147 : {-1.621334774299757e-01, 2.870743130038509e-01, -5.485761164147890e-01, 9.992734938824946e-02, -1.332550298134261e-02,
148 : 5.326252573648004e-02, -6.299408068289099e-02, 1.525398352758627e-02, -7.776943954825605e-02, -2.335884953507601e-02},
149 : {-2.008976150849174e-01, 2.237224648542355e-01, 4.811889625788790e-02, -6.855884193567087e-01, -2.729265954345345e-02,
150 : 3.651730112313705e-02, 6.325330777317102e-02, 2.871281112230844e-02, -1.285590864125103e-01, -3.204963735369064e-03},
151 : {-2.317011191832649e-01, 2.980080835636925e-02, -1.267017945785352e-01, 4.328230970765579e-02, -2.437461022925741e-01,
152 : 1.349716200511426e-02, -7.155992987801446e-04, -3.513449694839539e-03, -5.603489763638486e-02, 5.612114259243500e-02}
153 1 : };
154 :
155 : double data_Q[] = {32.0000, 13.1000, -4.9000, -3.0000, 6.0000, 2.2000, 2.6000, 3.4000, -1.9000, -7.5000,
156 : 13.1000, 18.3000, -5.3000, -9.5000, 3.0000, 2.1000, 3.9000, 3.0000, -3.6000, -4.4000,
157 : -4.9000, -5.3000, 7.7000, 2.1000, -0.4000, -3.4000, -0.8000, -3.0000, 5.3000, 5.5000,
158 : -3.0000, -9.5000, 2.1000, 20.1000, 1.1000, 0.8000, -12.4000, -2.5000, 5.5000, 2.1000,
159 : 6.0000, 3.0000, -0.4000, 1.1000, 3.8000, 0.6000, 0.5000, 0.9000, -0.4000, -2.0000,
160 : 2.2000, 2.1000, -3.4000, 0.8000, 0.6000, 7.8000, 2.9000, -1.3000, -4.3000, -5.1000,
161 : 2.6000, 3.9000, -0.8000, -12.4000, 0.5000, 2.9000, 14.5000, 1.7000, -4.9000, 1.2000,
162 : 3.4000, 3.0000, -3.0000, -2.5000, 0.9000, -1.3000, 1.7000, 6.6000, -0.8000, 2.7000,
163 : -1.9000, -3.6000, 5.3000, 5.5000, -0.4000, -4.3000, -4.9000, -0.8000, 7.9000, 5.7000,
164 1 : -7.5000, -4.4000, 5.5000, 2.1000, -2.0000, -5.1000, 1.2000, 2.7000, 5.7000, 16.1000};
165 :
166 : double data_xs[][10] = {
167 : {1.0, 0.01, 0.02, 0.03, 0.04, 0.05, 0.06, 0.07, 0.08, 0.09},
168 : {0.09, 1.0, 0.01, 0.02, 0.03, 0.04, 0.05, 0.06, 0.07, 0.08},
169 : {0.08, 0.09, 1.0, 0.01, 0.02, 0.03, 0.04, 0.05, 0.06, 0.07},
170 : {0.07, 0.08, 0.09, 1.0, 0.01, 0.02, 0.03, 0.04, 0.05, 0.06},
171 : {0.06, 0.07, 0.08, 0.09, 1.0, 0.01, 0.02, 0.03, 0.04, 0.05}
172 1 : };
173 :
174 1 : double data_q[] = {2.9000, 0.8000, 1.3000, -1.1000, -0.5000, -0.3000, 1.0000, -0.3000, 0.7000, -2.1000};
175 :
176 1 : size_t mem = 3;
177 :
178 1 : LBFGSBuffer * buffer = new LBFGSBuffer(n, mem);
179 1 : Matrix * Q = new Matrix(n, n, data_Q);
180 1 : Matrix * q = new Matrix(n, 1, data_q);
181 :
182 1 : Function * f = new Quadratic(*Q, *q);
183 :
184 1 : Matrix * y = new Matrix(n, 1);
185 1 : Matrix * s = new Matrix(n, 1);
186 :
187 1 : Matrix * x_old = new Matrix(n, 1, data_xs[0]);
188 1 : Matrix * grad_old = new Matrix(n, 1);
189 :
190 1 : Matrix * d = new Matrix(n, 1);
191 1 : Matrix * grad = new Matrix(n, 1);
192 :
193 : double fx;
194 1 : double gamma0 = 1.0;
195 6 : for (int i = 0; i < 5; i++) {
196 5 : Matrix x(n, 1, data_xs[i]);
197 5 : status = f->call(x, fx, *grad);
198 5 : _ASSERT(ForBESUtils::is_status_ok(status));
199 5 : if (i > 0) {
200 4 : *s = x - *x_old;
201 4 : *y = *grad - *grad_old;
202 4 : status = buffer->push(s, y);
203 4 : _ASSERT(ForBESUtils::is_status_ok(status));
204 4 : double sy = 0.0;
205 4 : double yy = 0.0;
206 44 : for (size_t l = 0; l < n; l++) {
207 40 : sy += ((*s)[l]) * ((*y)[l]);
208 40 : yy += std::pow((*y)[l], 2);
209 : }
210 4 : gamma0 = sy / yy;
211 : }
212 5 : status = buffer->update(grad, d, gamma0);
213 5 : _ASSERT(ForBESUtils::is_status_ok(status));
214 55 : for (int j = 0; j < n; j++) {
215 : // keep the minus sign in -d.get(j, 0), since I multiplied H
216 : // times grad instead of -grad
217 50 : _ASSERT_NUM_EQ(dirs[i][j], -(*d)[j], DOUBLES_EQUAL_DELTA);
218 : }
219 5 : *x_old = x;
220 5 : *grad_old = *grad;
221 5 : }
222 :
223 1 : delete buffer;
224 1 : delete Q;
225 1 : delete q;
226 1 : delete f;
227 1 : delete y;
228 1 : delete s;
229 1 : delete x_old;
230 1 : delete grad_old;
231 1 : delete d;
232 1 : delete grad;
233 1 : }
234 :
235 1 : void TestLBFGSBuffer::testHessianEstimate() {
236 1 : std::srand(static_cast<unsigned long> (1433291l));
237 1 : size_t n = 10;
238 1 : size_t mem = 3;
239 :
240 1 : LBFGSBuffer * buffer = new LBFGSBuffer(n, mem);
241 :
242 1 : Matrix q = MatrixFactory::MakeRandomMatrix(n, 1, 0.0, 1.0);
243 2 : Matrix r;
244 :
245 1 : double H0 = 1.0;
246 :
247 11 : for (size_t i = 0; i < 10; i++) {
248 10 : Matrix yi = MatrixFactory::MakeRandomMatrix(n, 1, -0.4, 1.0);
249 20 : Matrix si = MatrixFactory::MakeRandomMatrix(n, 1, 0.5, 1.0);
250 10 : buffer->push(&si, &yi);
251 10 : }
252 :
253 1 : double hessian_est = buffer->hessian_estimate();
254 1 : _ASSERT(hessian_est > 0);
255 :
256 2 : delete buffer;
257 :
258 4 : }
|
