optimization.cpp 31.2 KB
Newer Older
1
// Copyright (C) 2008  Davis E. King (davis@dlib.net)
2
3
4
5
6
7
8
9
10
11
12
// License: Boost Software License   See LICENSE.txt for the full license.


#include <dlib/optimization.h>
#include <sstream>
#include <string>
#include <cstdlib>
#include <ctime>
#include <vector>
#include "../stl_checked.h"
#include "../array.h"
13
#include "../rand.h"
14
15
16
17
18
19
20
21
22
23
24
25
26

#include "tester.h"


namespace  
{

    using namespace test;
    using namespace dlib;
    using namespace std;

    logger dlog("test.optimization");

27
28
29
30
31
32
33
34
35
36
// ----------------------------------------------------------------------------------------

    bool approx_equal (
        double a,
        double b
    )
    {
        return std::abs(a - b) < 100*std::numeric_limits<double>::epsilon();
    }

Davis King's avatar
Davis King committed
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// ----------------------------------------------------------------------------------------

    long total_count = 0;


    template <typename T>
    double apq ( const T& x)
    {
        DLIB_ASSERT(x.nr() > 1 && x.nc() == 1,"");
        COMPILE_TIME_ASSERT(is_matrix<T>::value);
        double temp = 0;
        for (long r = 0; r < x.nr(); ++r)
        {
            temp += (r+1)*x(r)*x(r);
        }

        ++total_count;

        return temp + 1/100.0*(x(0) + x(x.nr()-1))*(x(0) + x(x.nr()-1));
    }

    template <typename T>
    T der_apq ( const T& x)
    {
        DLIB_ASSERT(x.nr() > 1 && x.nc() == 1,"");
        COMPILE_TIME_ASSERT(is_matrix<T>::value);
        T temp(x.nr());
        for (long r = 0; r < x.nr(); ++r)
        {
            temp(r) = 2*(r+1)*x(r) ;
        }

        temp(0) += 1/50.0*(x(0) + x(x.nr()-1));
        temp(x.nr()-1) += 1/50.0*(x(0) + x(x.nr()-1));

        ++total_count;

        return temp;
    }

// ----------------------------------------------------------------------------------------

    // Rosenbrock's function.  minimum at (1,1)
    double rosen ( const matrix<double,2,1>& x)
    {
        ++total_count;
        return 100*pow(x(1) - x(0)*x(0),2) + pow(1 - x(0),2);
    }

    matrix<double,2,1> der_rosen ( const matrix<double,2,1>& x)
    {
        ++total_count;
        matrix<double,2,1> res;
        res(0) = -400*x(0)*(x(1)-x(0)*x(0)) - 2*(1-x(0));
        res(1) = 200*(x(1)-x(0)*x(0));
        return res;
    }

95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// ----------------------------------------------------------------------------------------

    // negative of Rosenbrock's function.  minimum at (1,1)
    double neg_rosen ( const matrix<double,2,1>& x)
    {
        ++total_count;
        return -(100*pow(x(1) - x(0)*x(0),2) + pow(1 - x(0),2));
    }

    matrix<double,2,1> der_neg_rosen ( const matrix<double,2,1>& x)
    {
        ++total_count;
        matrix<double,2,1> res;
        res(0) = -400*x(0)*(x(1)-x(0)*x(0)) - 2*(1-x(0));
        res(1) = 200*(x(1)-x(0)*x(0));
        return -res;
    }

Davis King's avatar
Davis King committed
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
// ----------------------------------------------------------------------------------------

    double simple ( const matrix<double,2,1>& x)
    {
        ++total_count;
        return 10*x(0)*x(0) + x(1)*x(1);
    }

    matrix<double,2,1> der_simple ( const matrix<double,2,1>& x)
    {
        ++total_count;
        matrix<double,2,1> res;
        res(0) = 20*x(0);
        res(1) = 2*x(1);
        return res;
    }

// ----------------------------------------------------------------------------------------

    double powell ( const matrix<double,4,1>& x)
    {
        ++total_count;
        return pow(x(0) + 10*x(1),2) +
Davis King's avatar
Davis King committed
136
            pow(std::sqrt(5.0)*(x(2) - x(3)),2) + 
Davis King's avatar
Davis King committed
137
            pow((x(1) - 2*x(2))*(x(1) - 2*x(2)),2) +
Davis King's avatar
Davis King committed
138
            pow(std::sqrt(10.0)*(x(0) - x(3))*(x(0) - x(3)),2);
Davis King's avatar
Davis King committed
139
140
    }

141
142
143
144
145
146
147
148
// ----------------------------------------------------------------------------------------

// a simple function with a minimum at zero
    double single_variable_function ( double x)
    {
        ++total_count;
        return 3*x*x + 5;
    }
Davis King's avatar
Davis King committed
149
150
151
152
153
154
155
156
157
158

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

    void test_apq (
        const matrix<double,0,1> p
    )
    {
        typedef matrix<double,0,1> T;
Davis King's avatar
Davis King committed
159
        const double eps = 1e-12;
Davis King's avatar
Davis King committed
160
161
162
        const double minf = -10;
        matrix<double,0,1> x(p.nr()), opt(p.nr());
        set_all_elements(opt, 0);
163
        double val = 0;
Davis King's avatar
Davis King committed
164

165
166
167
168
        if (p.size() < 20)
            dlog << LINFO << "testing with apq and the start point: " << trans(p);
        else
            dlog << LINFO << "testing with apq and a big vector with " << p.size() << " components.";
Davis King's avatar
Davis King committed
169

170
171
172
173
174
        // don't use bfgs on really large vectors
        if (p.size() < 20)
        {
            total_count = 0;
            x = p;
175
            val = find_min(bfgs_search_strategy(), 
176
177
178
                     objective_delta_stop_strategy(eps),
                     wrap_function(apq<T>), wrap_function(der_apq<T>), x, minf);
            DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
179
            DLIB_TEST(approx_equal(val , apq(x)));
180
            dlog << LINFO << "find_min() bgfs: got apq in " << total_count;
181
182
183
184
185
186
187
188

            total_count = 0;
            x = p;
            find_min(bfgs_search_strategy(), 
                     gradient_norm_stop_strategy(),
                     wrap_function(apq<T>), wrap_function(der_apq<T>), x, minf);
            DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
            dlog << LINFO << "find_min() bgfs(gn): got apq in " << total_count;
189
        }
Davis King's avatar
Davis King committed
190
191


192
193
194
195
        if (p.size() < 100)
        {
            total_count = 0;
            x = p;
196
            val=find_min_bobyqa(wrap_function(apq<T>), x, 2*x.size()+1,
197
198
199
200
201
202
                            uniform_matrix<double>(x.size(),1,-1e100),
                            uniform_matrix<double>(x.size(),1,1e100),
                            (max(abs(x))+1)/10,
                            1e-6,
                            10000);
            DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
203
            DLIB_TEST(approx_equal(val , apq(x)));
204
205
206
            dlog << LINFO << "find_min_bobyqa(): got apq in " << total_count;
        }

Davis King's avatar
Davis King committed
207
208
        total_count = 0;
        x = p;
209
        val=find_min(lbfgs_search_strategy(10), 
210
211
                 objective_delta_stop_strategy(eps),
                 wrap_function(apq<T>), wrap_function(der_apq<T>), x, minf);
212
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
213
        DLIB_TEST(approx_equal(val , apq(x)));
214
        dlog << LINFO << "find_min() lbgfs-10: got apq in " << total_count;
Davis King's avatar
Davis King committed
215

216
217
218

        total_count = 0;
        x = p;
219
        val=find_min(lbfgs_search_strategy(1), 
220
221
                 objective_delta_stop_strategy(eps),
                 wrap_function(apq<T>), wrap_function(der_apq<T>), x, minf);
222
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
223
        DLIB_TEST(approx_equal(val , apq(x)));
224
225
        dlog << LINFO << "find_min() lbgfs-1: got apq in " << total_count;

226
227
228

        total_count = 0;
        x = p;
229
        val=find_min(cg_search_strategy(),
230
231
                 objective_delta_stop_strategy(eps),
                 wrap_function(apq<T>), wrap_function(der_apq<T>), x, minf);
232
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
233
        DLIB_TEST(approx_equal(val , apq(x)));
234
235
236
237
238
239
240
241
        dlog << LINFO << "find_min() cg: got apq in " << total_count;


        // don't do approximate derivative tests if the input point is really long
        if (p.size() < 20)
        {
            total_count = 0;
            x = p;
242
            val=find_min(bfgs_search_strategy(),
243
244
245
                     objective_delta_stop_strategy(eps),
                     wrap_function(apq<T>), derivative(wrap_function(apq<T>)), x, minf);
            DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
246
            DLIB_TEST(approx_equal(val , apq(x)));
247
248
249
250
251
            dlog << LINFO << "find_min() bfgs: got apq/noder in " << total_count;


            total_count = 0;
            x = p;
252
            val=find_min(cg_search_strategy(),
253
254
255
                     objective_delta_stop_strategy(eps),
                     wrap_function(apq<T>), derivative(wrap_function(apq<T>)), x, minf);
            DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
256
            DLIB_TEST(approx_equal(val , apq(x)));
257
258
259
260
261
            dlog << LINFO << "find_min() cg: got apq/noder in " << total_count;


            total_count = 0;
            x = p;
262
            val=find_min_using_approximate_derivatives(bfgs_search_strategy(),
263
264
265
                                                   objective_delta_stop_strategy(eps), 
                                                   wrap_function(apq<T>), x, minf);
            DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
266
            DLIB_TEST(approx_equal(val , apq(x)));
267
268
269
270
271
            dlog << LINFO << "find_min() bfgs: got apq/noder2 in " << total_count;


            total_count = 0;
            x = p;
272
            val=find_min_using_approximate_derivatives(lbfgs_search_strategy(10),
273
274
275
276
277
278
279
280
                                                   objective_delta_stop_strategy(eps), 
                                                   wrap_function(apq<T>), x, minf);
            DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
            dlog << LINFO << "find_min() lbfgs-10: got apq/noder2 in " << total_count;


            total_count = 0;
            x = p;
281
            val=find_min_using_approximate_derivatives(cg_search_strategy(),
282
283
284
                                                   objective_delta_stop_strategy(eps),
                                                   wrap_function(apq<T>), x, minf);
            DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
285
            DLIB_TEST(approx_equal(val , apq(x)));
286
287
            dlog << LINFO << "find_min() cg: got apq/noder2 in " << total_count;
        }
Davis King's avatar
Davis King committed
288
289
290
291
292
293
294
295
296
297
298
    }

    void test_powell (
        const matrix<double,4,1> p
    )
    {
        const double eps = 1e-15;
        const double minf = -1;
        matrix<double,4,1> x, opt;
        opt(0) = 0;
        opt(1) = 0;
299
300
        opt(2) = 0;
        opt(3) = 0;
Davis King's avatar
Davis King committed
301

302
303
        double val = 0;

Davis King's avatar
Davis King committed
304
305
        dlog << LINFO << "testing with powell and the start point: " << trans(p);

Davis King's avatar
Davis King committed
306
        /*
Davis King's avatar
Davis King committed
307
308
        total_count = 0;
        x = p;
309
        val=find_min(bfgs_search_strategy(),
310
311
                 objective_delta_stop_strategy(eps),
                 &powell, derivative(&powell,1e-8), x, minf);
312
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-2),opt-x);
313
        DLIB_TEST(approx_equal(val , powell(x)));
314
315
        dlog << LINFO << "find_min() bfgs: got powell/noder in " << total_count;

Davis King's avatar
Davis King committed
316
317
318

        total_count = 0;
        x = p;
319
        val=find_min(cg_search_strategy(),
320
321
                 objective_delta_stop_strategy(eps),
                 &powell, derivative(&powell,1e-9), x, minf);
322
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-2),opt-x);
323
        DLIB_TEST(approx_equal(val , powell(x)));
324
        dlog << LINFO << "find_min() cg: got powell/noder in " << total_count;
Davis King's avatar
Davis King committed
325
        */
326
327
328

        total_count = 0;
        x = p;
329
        val=find_min_using_approximate_derivatives(bfgs_search_strategy(),
330
331
                                               objective_delta_stop_strategy(eps),
                                               &powell, x, minf, 1e-10);
332
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-1),opt-x);
333
        DLIB_TEST(approx_equal(val , powell(x)));
334
335
336
337
338
        dlog << LINFO << "find_min() bfgs: got powell/noder2 in " << total_count;


        total_count = 0;
        x = p;
339
        val=find_min_using_approximate_derivatives(lbfgs_search_strategy(4),
340
341
342
                                               objective_delta_stop_strategy(eps),
                                               &powell, x, minf, 1e-10);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-1),opt-x);
343
        DLIB_TEST(approx_equal(val , powell(x)));
344
345
        dlog << LINFO << "find_min() lbfgs-4: got powell/noder2 in " << total_count;

346

347
348
        total_count = 0;
        x = p;
349
        val=find_min_using_approximate_derivatives(lbfgs_search_strategy(4),
350
351
352
                                               gradient_norm_stop_strategy(),
                                               &powell, x, minf, 1e-10);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-1),opt-x);
353
        DLIB_TEST(approx_equal(val , powell(x)));
354
355
356
        dlog << LINFO << "find_min() lbfgs-4(gn): got powell/noder2 in " << total_count;


357
358
        total_count = 0;
        x = p;
359
        val=find_min_using_approximate_derivatives(cg_search_strategy(),
360
361
                                               objective_delta_stop_strategy(eps),
                                               &powell, x, minf, 1e-10);
362
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-1),opt-x);
363
        DLIB_TEST(approx_equal(val , powell(x)));
364
        dlog << LINFO << "find_min() cg: got powell/noder2 in " << total_count;
365
366
367
368


        total_count = 0;
        x = p;
369
        val=find_min_bobyqa(&powell, x, 2*x.size()+1,
370
371
372
373
374
375
                        uniform_matrix<double>(x.size(),1,-1e100),
                        uniform_matrix<double>(x.size(),1,1e100),
                        (max(abs(x))+1)/10,
                        1e-7,
                        10000);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-3),opt-x);
376
        DLIB_TEST(approx_equal(val , powell(x)));
377
378
        dlog << LINFO << "find_min_bobyqa(): got powell in " << total_count;

Davis King's avatar
Davis King committed
379
380
381
382
383
384
385
386
    }



    void test_simple (
        const matrix<double,2,1> p
    )
    {
Davis King's avatar
Davis King committed
387
        const double eps = 1e-12;
Davis King's avatar
Davis King committed
388
389
390
391
        const double minf = -10000;
        matrix<double,2,1> x, opt;
        opt(0) = 0;
        opt(1) = 0;
392
        double val = 0;
Davis King's avatar
Davis King committed
393
394
395
396
397

        dlog << LINFO << "testing with simple and the start point: " << trans(p);

        total_count = 0;
        x = p;
398
        val=find_min(bfgs_search_strategy(),
399
400
                 objective_delta_stop_strategy(eps),
                 &simple, &der_simple, x, minf);
401
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
402
        DLIB_TEST(approx_equal(val , simple(x)));
403
404
        dlog << LINFO << "find_min() bfgs: got simple in " << total_count;

Davis King's avatar
Davis King committed
405

406
407
        total_count = 0;
        x = p;
408
        val=find_min(bfgs_search_strategy(),
409
410
411
                 gradient_norm_stop_strategy(),
                 &simple, &der_simple, x, minf);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
412
        DLIB_TEST(approx_equal(val , simple(x)));
413
414
415
        dlog << LINFO << "find_min() bfgs(gn): got simple in " << total_count;


Davis King's avatar
Davis King committed
416
417
        total_count = 0;
        x = p;
418
        val=find_min(lbfgs_search_strategy(3),
419
420
                 objective_delta_stop_strategy(eps),
                 &simple, &der_simple, x, minf);
421
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
422
        DLIB_TEST(approx_equal(val , simple(x)));
423
424
        dlog << LINFO << "find_min() lbfgs-3: got simple in " << total_count;

Davis King's avatar
Davis King committed
425
426
427

        total_count = 0;
        x = p;
428
        val=find_min(cg_search_strategy(),
429
430
                 objective_delta_stop_strategy(eps),
                 &simple, &der_simple, x, minf);
431
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
432
        DLIB_TEST(approx_equal(val , simple(x)));
433
434
435
        dlog << LINFO << "find_min() cg: got simple in " << total_count;


Davis King's avatar
Davis King committed
436
437
438

        total_count = 0;
        x = p;
439
        val=find_min(bfgs_search_strategy(),
440
441
                 objective_delta_stop_strategy(eps),
                 &simple, derivative(&simple), x, minf);
442
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
443
        DLIB_TEST(approx_equal(val , simple(x)));
444
445
        dlog << LINFO << "find_min() bfgs: got simple/noder in " << total_count;

446
447
448

        total_count = 0;
        x = p;
449
        val=find_min(lbfgs_search_strategy(8),
450
451
                 objective_delta_stop_strategy(eps),
                 &simple, derivative(&simple), x, minf);
452
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
453
        DLIB_TEST(approx_equal(val , simple(x)));
454
455
        dlog << LINFO << "find_min() lbfgs-8: got simple/noder in " << total_count;

456
457
458

        total_count = 0;
        x = p;
459
        val=find_min(cg_search_strategy(),
460
461
                 objective_delta_stop_strategy(eps),
                 &simple, derivative(&simple), x, minf);
462
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
463
        DLIB_TEST(approx_equal(val , simple(x)));
464
465
466
467
468
469
        dlog << LINFO << "find_min() cg: got simple/noder in " << total_count;



        total_count = 0;
        x = p;
470
        val=find_min_using_approximate_derivatives(bfgs_search_strategy(),
471
472
473
                                               objective_delta_stop_strategy(eps),
                                               &simple, x, minf);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
474
        DLIB_TEST(approx_equal(val , simple(x)));
475
476
477
478
479
        dlog << LINFO << "find_min() bfgs: got simple/noder2 in " << total_count;


        total_count = 0;
        x = p;
480
        val=find_min_using_approximate_derivatives(lbfgs_search_strategy(6),
481
482
483
                                               objective_delta_stop_strategy(eps),
                                               &simple, x, minf);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
484
        DLIB_TEST(approx_equal(val , simple(x)));
485
486
487
488
489
        dlog << LINFO << "find_min() lbfgs-6: got simple/noder2 in " << total_count;


        total_count = 0;
        x = p;
490
        val=find_min_using_approximate_derivatives(cg_search_strategy(),
491
492
493
                                               objective_delta_stop_strategy(eps),
                                               &simple, x, minf);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
494
        DLIB_TEST(approx_equal(val , simple(x)));
495
496
        dlog << LINFO << "find_min() cg: got simple/noder2 in " << total_count;

497
498
499

        total_count = 0;
        x = p;
500
        val=find_min_bobyqa(&simple, x, 2*x.size()+1,
501
502
503
504
505
506
                        uniform_matrix<double>(x.size(),1,-1e100),
                        uniform_matrix<double>(x.size(),1,1e100),
                        (max(abs(x))+1)/10,
                        1e-6,
                        10000);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
507
        DLIB_TEST(approx_equal(val , simple(x)));
508
509
        dlog << LINFO << "find_min_bobyqa(): got simple in " << total_count;

Davis King's avatar
Davis King committed
510
511
512
513
514
515
516
    }


    void test_rosen (
        const matrix<double,2,1> p
    )
    {
517
        const double eps = 1e-15;
Davis King's avatar
Davis King committed
518
519
520
521
522
        const double minf = -10;
        matrix<double,2,1> x, opt;
        opt(0) = 1;
        opt(1) = 1;

523
524
        double val = 0;

Davis King's avatar
Davis King committed
525
526
527
528
        dlog << LINFO << "testing with rosen and the start point: " << trans(p);

        total_count = 0;
        x = p;
529
        val=find_min(bfgs_search_strategy(),
530
531
                 objective_delta_stop_strategy(eps),
                 &rosen, &der_rosen, x, minf);
532
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-7),opt-x);
533
        DLIB_TEST(approx_equal(val , rosen(x)));
534
535
        dlog << LINFO << "find_min() bfgs: got rosen in " << total_count;

Davis King's avatar
Davis King committed
536

537
538
        total_count = 0;
        x = p;
539
        val=find_min(bfgs_search_strategy(),
540
541
542
                 gradient_norm_stop_strategy(),
                 &rosen, &der_rosen, x, minf);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-7),opt-x);
543
        DLIB_TEST(approx_equal(val , rosen(x)));
544
545
546
        dlog << LINFO << "find_min() bfgs(gn): got rosen in " << total_count;


Davis King's avatar
Davis King committed
547
548
        total_count = 0;
        x = p;
549
        val=find_min(lbfgs_search_strategy(20),
550
551
552
                 objective_delta_stop_strategy(eps),
                 &rosen, &der_rosen, x, minf);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-7),opt-x);
553
        DLIB_TEST(approx_equal(val , rosen(x)));
554
555
        dlog << LINFO << "find_min() lbfgs-20: got rosen in " << total_count;

Davis King's avatar
Davis King committed
556
557
558

        total_count = 0;
        x = p;
559
        val=find_min(cg_search_strategy(),
560
561
562
                 objective_delta_stop_strategy(eps),
                 &rosen, &der_rosen, x, minf);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-7),opt-x);
563
        DLIB_TEST(approx_equal(val , rosen(x)));
564
565
566
567
568
569
        dlog << LINFO << "find_min() cg: got rosen in " << total_count;



        total_count = 0;
        x = p;
570
        val=find_min(bfgs_search_strategy(),
571
572
                 objective_delta_stop_strategy(eps),
                 &rosen, derivative(&rosen,1e-5), x, minf);
573
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-4),opt-x);
574
        DLIB_TEST(approx_equal(val , rosen(x)));
575
576
        dlog << LINFO << "find_min() bfgs: got rosen/noder in " << total_count;

Davis King's avatar
Davis King committed
577
578
579

        total_count = 0;
        x = p;
580
        val=find_min(lbfgs_search_strategy(5),
581
582
                 objective_delta_stop_strategy(eps),
                 &rosen, derivative(&rosen,1e-5), x, minf);
583
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-4),opt-x);
584
        DLIB_TEST(approx_equal(val , rosen(x)));
585
586
        dlog << LINFO << "find_min() lbfgs-5: got rosen/noder in " << total_count;

587
588
589

        total_count = 0;
        x = p;
590
        val=find_min(cg_search_strategy(),
591
592
593
                 objective_delta_stop_strategy(eps),
                 &rosen, derivative(&rosen,1e-5), x, minf);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-4),opt-x);
594
        DLIB_TEST(approx_equal(val , rosen(x)));
595
596
597
        dlog << LINFO << "find_min() cg: got rosen/noder in " << total_count;


598
599
        total_count = 0;
        x = p;
600
        val=find_min_using_approximate_derivatives(cg_search_strategy(),
601
602
                                               objective_delta_stop_strategy(eps),
                                               &rosen, x, minf);
603
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-4),opt-x);
604
        DLIB_TEST(approx_equal(val , rosen(x)));
605
        dlog << LINFO << "find_min() cg: got rosen/noder2 in " << total_count;
606
607
608
609
610
611


        if (max(abs(p)) < 1000)
        {
            total_count = 0;
            x = p;
612
            val=find_min_bobyqa(&rosen, x, 2*x.size()+1,
613
614
615
616
617
618
                            uniform_matrix<double>(x.size(),1,-1e100),
                            uniform_matrix<double>(x.size(),1,1e100),
                            (max(abs(x))+1)/10,
                            1e-6,
                            10000);
            DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
619
            DLIB_TEST(approx_equal(val , rosen(x)));
620
621
            dlog << LINFO << "find_min_bobyqa(): got rosen in " << total_count;
        }
622
623
624
625
626
627
628
629
630
631
632
633
634
    }


    void test_neg_rosen (
        const matrix<double,2,1> p
    )
    {
        const double eps = 1e-15;
        const double maxf = 10;
        matrix<double,2,1> x, opt;
        opt(0) = 1;
        opt(1) = 1;

635
636
        double val = 0;

637
638
639
640
        dlog << LINFO << "testing with neg_rosen and the start point: " << trans(p);

        total_count = 0;
        x = p;
641
        val=find_max(
642
643
644
            bfgs_search_strategy(), 
            objective_delta_stop_strategy(eps), &neg_rosen, &der_neg_rosen, x, maxf);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-7),opt-x);
645
        DLIB_TEST(approx_equal(val , neg_rosen(x)));
646
647
648
649
        dlog << LINFO << "find_max() bfgs: got neg_rosen in " << total_count;

        total_count = 0;
        x = p;
650
        val=find_max(
651
652
653
            lbfgs_search_strategy(5), 
            objective_delta_stop_strategy(eps), &neg_rosen, &der_neg_rosen, x, maxf);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-7),opt-x);
654
        DLIB_TEST(approx_equal(val , neg_rosen(x)));
655
656
657
658
        dlog << LINFO << "find_max() lbfgs-5: got neg_rosen in " << total_count;

        total_count = 0;
        x = p;
659
        val=find_max(
660
661
662
            lbfgs_search_strategy(5), 
            objective_delta_stop_strategy(eps), &neg_rosen, derivative(&neg_rosen), x, maxf);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-7),opt-x);
663
        DLIB_TEST(approx_equal(val , neg_rosen(x)));
664
665
666
667
668
        dlog << LINFO << "find_max() lbfgs-5: got neg_rosen/noder in " << total_count;


        total_count = 0;
        x = p;
669
        val=find_max_using_approximate_derivatives(
670
671
672
            cg_search_strategy(), 
            objective_delta_stop_strategy(eps), &neg_rosen, x, maxf);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-7),opt-x);
673
        DLIB_TEST(approx_equal(val , neg_rosen(x)));
674
        dlog << LINFO << "find_max() cg: got neg_rosen/noder2 in " << total_count;
675
676
677
678


        total_count = 0;
        x = p;
679
        val=find_max_bobyqa(&neg_rosen, x, 2*x.size()+1,
680
681
682
683
684
685
                        uniform_matrix<double>(x.size(),1,-1e100),
                        uniform_matrix<double>(x.size(),1,1e100),
                        (max(abs(x))+1)/10,
                        1e-6,
                        10000);
        DLIB_TEST_MSG(dlib::equal(x,opt, 1e-5),opt-x);
686
        DLIB_TEST(approx_equal(val , neg_rosen(x)));
687
        dlog << LINFO << "find_max_bobyqa(): got neg_rosen in " << total_count;
Davis King's avatar
Davis King committed
688
689
    }

690
691
692
693
694
695
// ----------------------------------------------------------------------------------------

    void test_single_variable_function (
        const double p
    )
    {
696
        const double eps = 1e-7;
697
698
699


        dlog << LINFO << "testing with single_variable_function and the start point: " << p;
700
        double out, x;
701
702

        total_count = 0;
703
704
705
706
        x = p;
        out = find_min_single_variable(&single_variable_function, x, -1e100, 1e100, eps, 1000);
        DLIB_TEST_MSG(std::abs(out-5) < 1e-6, out-5);
        DLIB_TEST_MSG(std::abs(x) < 1e-6, x);
707
708
709
710
        dlog << LINFO << "find_min_single_variable(): got single_variable_function in " << total_count;


        total_count = 0;
711
712
713
714
        x = p;
        out = -find_max_single_variable(negate_function(&single_variable_function), x, -1e100, 1e100, eps, 1000);
        DLIB_TEST_MSG(std::abs(out-5) < 1e-6, out-5);
        DLIB_TEST_MSG(std::abs(x) < 1e-6, x);
715
716
        dlog << LINFO << "find_max_single_variable(): got single_variable_function in " << total_count;

717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758

        if (p > 0)
        {
            total_count = 0;
            x = p;
            out = find_min_single_variable(&single_variable_function, x, -1e-4, 1e100, eps, 1000);
            DLIB_TEST_MSG(std::abs(out-5) < 1e-6, out-5);
            DLIB_TEST_MSG(std::abs(x) < 1e-6, x);
            dlog << LINFO << "find_min_single_variable(): got single_variable_function in " << total_count;


            if (p > 3)
            {
                total_count = 0;
                x = p;
                out = -find_max_single_variable(negate_function(&single_variable_function), x, 3, 1e100, eps, 1000);
                DLIB_TEST_MSG(std::abs(out - (3*3*3+5)) < 1e-6, out-(3*3*3+5));
                DLIB_TEST_MSG(std::abs(x-3) < 1e-6, x);
                dlog << LINFO << "find_max_single_variable(): got single_variable_function in " << total_count;
            }
        }

        if (p < 0)
        {
            total_count = 0;
            x = p;
            out = find_min_single_variable(&single_variable_function, x, -1e100, 1e-4, eps, 1000);
            DLIB_TEST_MSG(std::abs(out-5) < 1e-6, out-5);
            DLIB_TEST_MSG(std::abs(x) < 1e-6, x);
            dlog << LINFO << "find_min_single_variable(): got single_variable_function in " << total_count;

            if (p < -3)
            {
                total_count = 0;
                x = p;
                out = find_min_single_variable(&single_variable_function, x, -1e100, -3, eps, 1000);
                DLIB_TEST_MSG(std::abs(out - (3*3*3+5)) < 1e-6, out-(3*3*3+5));
                DLIB_TEST_MSG(std::abs(x+3) < 1e-6, x);
                dlog << LINFO << "find_min_single_variable(): got single_variable_function in " << total_count;
            }
        }

759
760
    }

Davis King's avatar
Davis King committed
761
762
// ----------------------------------------------------------------------------------------

763
764
765
766
767
768
769
    void optimization_test (
    )
    /*!
        ensures
            - runs tests on the optimization stuff compliance with the specs
    !*/
    {        
Davis King's avatar
Davis King committed
770
771
        matrix<double,0,1> p;

772
773
        print_spinner();

Davis King's avatar
Davis King committed
774
775
        p.set_size(2);

776
777
778
779
        // test with single_variable_function
        test_single_variable_function(0);
        test_single_variable_function(1);
        test_single_variable_function(-10);
780
        test_single_variable_function(-100);
781
        test_single_variable_function(900.53);
Davis King's avatar
Davis King committed
782
783
784
785
786

        // test with the rosen function
        p(0) = 9;
        p(1) = -4.9;
        test_rosen(p);
787
        test_neg_rosen(p);
Davis King's avatar
Davis King committed
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809

        p(0) = 0;
        p(1) = 0;
        test_rosen(p);

        p(0) = 5323;
        p(1) = 98248;
        test_rosen(p);

        // test with the simple function
        p(0) = 1;
        p(1) = 1;
        test_simple(p);

        p(0) = 0.5;
        p(1) = -9;
        test_simple(p);

        p(0) = 645;
        p(1) = 839485;
        test_simple(p);

810
811
        print_spinner();

Davis King's avatar
Davis King committed
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
        // test with the apq function
        p.set_size(5);

        p(0) = 1;
        p(1) = 1;
        p(2) = 1;
        p(3) = 1;
        p(4) = 1;
        test_apq(p);

        p(0) = 1;
        p(1) = 2;
        p(2) = 3;
        p(3) = 4;
        p(4) = 5;
        test_apq(p);

        p(0) = 1;
        p(1) = 2;
        p(2) = -3;
        p(3) = 4;
        p(4) = 5;
        test_apq(p);

836
837
        print_spinner();

Davis King's avatar
Davis King committed
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
        p(0) = 1;
        p(1) = 2324;
        p(2) = -3;
        p(3) = 4;
        p(4) = 534534;
        test_apq(p);

        p.set_size(10);
        p(0) = 1;
        p(1) = 2;
        p(2) = -3;
        p(3) = 4;
        p(4) = 5;
        p(5) = 1;
        p(6) = 2;
        p(7) = -3;
        p(8) = 4;
        p(9) = 5;
        test_apq(p);

858
859
860
861
862
863
864
865
866
867
868
        // test apq with a big vector
        p.set_size(500);
        dlib::rand::float_1a rnd;
        for (long i = 0; i < p.size(); ++i)
        {
            p(i) = rnd.get_random_double()*20 - 10; 
        }
        test_apq(p);

        print_spinner();

Davis King's avatar
Davis King committed
869
870
871
872
873
874
875
876
        // test with the powell function
        p.set_size(4);

        p(0) = 3;
        p(1) = -1;
        p(2) = 0;
        p(3) = 1;
        test_powell(p);
877

878
879
880
881
        {
            matrix<double,2,1> m;
            m(0) = -0.43;
            m(1) = 0.919;
882
            DLIB_TEST(dlib::equal(der_rosen(m) , derivative(&rosen)(m),1e-5));
883

884
            DLIB_TEST_MSG(std::abs(derivative(make_line_search_function(&rosen,m,m))(0) - 
885
                                  make_line_search_function(derivative(&rosen),m,m)(0)) < 1e-5,"");
886
            DLIB_TEST_MSG(std::abs(derivative(make_line_search_function(&rosen,m,m))(1) - 
887
888
                                  make_line_search_function(derivative(&rosen),m,m)(1)) < 1e-5,"");

889
            DLIB_TEST_MSG(std::abs(derivative(make_line_search_function(&rosen,m,m))(0) - 
890
                                  make_line_search_function(&der_rosen,m,m)(0)) < 1e-5,"");
891
            DLIB_TEST_MSG(std::abs(derivative(make_line_search_function(&rosen,m,m))(1) - 
892
893
894
895
896
897
                                  make_line_search_function(&der_rosen,m,m)(1)) < 1e-5,"");
        }
        {
            matrix<double,2,1> m;
            m(0) = 1;
            m(1) = 2;
898
            DLIB_TEST(dlib::equal(der_rosen(m) , derivative(&rosen)(m),1e-5));
899

900
            DLIB_TEST_MSG(std::abs(derivative(make_line_search_function(&rosen,m,m))(0) - 
901
                                  make_line_search_function(derivative(&rosen),m,m)(0)) < 1e-5,"");
902
            DLIB_TEST_MSG(std::abs(derivative(make_line_search_function(&rosen,m,m))(1) - 
903
904
                                  make_line_search_function(derivative(&rosen),m,m)(1)) < 1e-5,"");

905
            DLIB_TEST_MSG(std::abs(derivative(make_line_search_function(&rosen,m,m))(0) - 
906
                                  make_line_search_function(&der_rosen,m,m)(0)) < 1e-5,"");
907
            DLIB_TEST_MSG(std::abs(derivative(make_line_search_function(&rosen,m,m))(1) - 
908
909
910
                                  make_line_search_function(&der_rosen,m,m)(1)) < 1e-5,"");
        }

911
912
913
914
915
916
        {
            matrix<double,2,1> m;
            m = 1,2;
            DLIB_TEST(std::abs(neg_rosen(m) - negate_function(&rosen)(m) ) < 1e-16);
        }

917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
    }



    class optimization_tester : public tester
    {
    public:
        optimization_tester (
        ) :
            tester ("test_optimization",
                    "Runs tests on the optimization component.")
        {}

        void perform_test (
        )
        {
            optimization_test();
        }
    } a;

}