1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
|
.. highlight:: c++
.. default-domain:: cpp
.. _chapter-gradient_tutorial:
==================================
General Unconstrained Minimization
==================================
Ceres Solver besides being able to solve non-linear least squares
problem can also solve general unconstrained problems using just their
objective function value and gradients. In this chapter we will see
how to do this.
Rosenbrock's Function
=====================
Consider minimizing the famous `Rosenbrock's function
<http://en.wikipedia.org/wiki/Rosenbrock_function>`_ [#f1]_.
The simplest way to minimize is to define a templated functor to
evaluate the objective value of this function and then use Ceres
Solver's automatic differentiation to compute its derivatives.
We begin by defining a templated functor and then using
``AutoDiffFirstOrderFunction`` to construct an instance of the
``FirstOrderFunction`` interface. This is the object that is
responsible for computing the objective function value and the
gradient (if required). This is the analog of the
:class:`CostFunction` when defining non-linear least squares problems
in Ceres.
.. code::
// f(x,y) = (1-x)^2 + 100(y - x^2)^2;
struct Rosenbrock {
template <typename T>
bool operator()(const T* parameters, T* cost) const {
const T x = parameters[0];
const T y = parameters[1];
cost[0] = (1.0 - x) * (1.0 - x) + 100.0 * (y - x * x) * (y - x * x);
return true;
}
static ceres::FirstOrderFunction* Create() {
constexpr int kNumParameters = 2;
return new ceres::AutoDiffFirstOrderFunction<Rosenbrock, kNumParameters>(
new Rosenbrock);
}
};
Minimizing it then is a straightforward matter of constructing a
:class:`GradientProblem` object and calling :func:`Solve` on it.
.. code::
double parameters[2] = {-1.2, 1.0};
ceres::GradientProblem problem(Rosenbrock::Create());
ceres::GradientProblemSolver::Options options;
options.minimizer_progress_to_stdout = true;
ceres::GradientProblemSolver::Summary summary;
ceres::Solve(options, problem, parameters, &summary);
std::cout << summary.FullReport() << "\n";
Executing this code results, solve the problem using limited memory
`BFGS
<http://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm>`_
algorithm.
.. code-block:: bash
0: f: 2.420000e+01 d: 0.00e+00 g: 2.16e+02 h: 0.00e+00 s: 0.00e+00 e: 0 it: 2.29e-05 tt: 2.29e-05
1: f: 4.280493e+00 d: 1.99e+01 g: 1.52e+01 h: 2.01e-01 s: 8.62e-04 e: 2 it: 8.39e-05 tt: 1.62e-04
2: f: 3.571154e+00 d: 7.09e-01 g: 1.35e+01 h: 3.78e-01 s: 1.34e-01 e: 3 it: 2.22e-05 tt: 1.91e-04
3: f: 3.440869e+00 d: 1.30e-01 g: 1.73e+01 h: 1.36e-01 s: 1.00e+00 e: 1 it: 5.01e-06 tt: 2.01e-04
4: f: 3.213597e+00 d: 2.27e-01 g: 1.55e+01 h: 1.06e-01 s: 4.59e-01 e: 1 it: 3.81e-06 tt: 2.10e-04
5: f: 2.839723e+00 d: 3.74e-01 g: 1.05e+01 h: 1.34e-01 s: 5.24e-01 e: 1 it: 4.05e-06 tt: 2.19e-04
6: f: 2.448490e+00 d: 3.91e-01 g: 1.29e+01 h: 3.04e-01 s: 1.00e+00 e: 1 it: 5.01e-06 tt: 2.28e-04
7: f: 1.943019e+00 d: 5.05e-01 g: 4.00e+00 h: 8.81e-02 s: 7.43e-01 e: 1 it: 4.05e-06 tt: 2.36e-04
8: f: 1.731469e+00 d: 2.12e-01 g: 7.36e+00 h: 1.71e-01 s: 4.60e-01 e: 2 it: 1.22e-05 tt: 2.52e-04
9: f: 1.503267e+00 d: 2.28e-01 g: 6.47e+00 h: 8.66e-02 s: 1.00e+00 e: 1 it: 5.96e-06 tt: 2.66e-04
10: f: 1.228331e+00 d: 2.75e-01 g: 2.00e+00 h: 7.70e-02 s: 7.90e-01 e: 1 it: 4.05e-06 tt: 2.75e-04
11: f: 1.016523e+00 d: 2.12e-01 g: 5.15e+00 h: 1.39e-01 s: 3.76e-01 e: 2 it: 9.06e-06 tt: 2.88e-04
12: f: 9.145773e-01 d: 1.02e-01 g: 6.74e+00 h: 7.98e-02 s: 1.00e+00 e: 1 it: 5.01e-06 tt: 2.97e-04
13: f: 7.508302e-01 d: 1.64e-01 g: 3.88e+00 h: 5.76e-02 s: 4.93e-01 e: 1 it: 5.01e-06 tt: 3.05e-04
14: f: 5.832378e-01 d: 1.68e-01 g: 5.56e+00 h: 1.42e-01 s: 1.00e+00 e: 1 it: 4.77e-06 tt: 3.13e-04
15: f: 3.969581e-01 d: 1.86e-01 g: 1.64e+00 h: 1.17e-01 s: 1.00e+00 e: 1 it: 4.05e-06 tt: 3.20e-04
16: f: 3.171557e-01 d: 7.98e-02 g: 3.84e+00 h: 1.18e-01 s: 3.97e-01 e: 2 it: 8.82e-06 tt: 3.33e-04
17: f: 2.641257e-01 d: 5.30e-02 g: 3.27e+00 h: 6.14e-02 s: 1.00e+00 e: 1 it: 4.05e-06 tt: 3.42e-04
18: f: 1.909730e-01 d: 7.32e-02 g: 5.29e-01 h: 8.55e-02 s: 6.82e-01 e: 1 it: 1.00e-05 tt: 4.64e-04
19: f: 1.472012e-01 d: 4.38e-02 g: 3.11e+00 h: 1.20e-01 s: 3.47e-01 e: 2 it: 1.29e-05 tt: 4.87e-04
20: f: 1.093558e-01 d: 3.78e-02 g: 2.97e+00 h: 8.43e-02 s: 1.00e+00 e: 1 it: 5.01e-06 tt: 4.97e-04
21: f: 6.710346e-02 d: 4.23e-02 g: 1.42e+00 h: 9.64e-02 s: 8.85e-01 e: 1 it: 4.05e-06 tt: 5.06e-04
22: f: 3.993377e-02 d: 2.72e-02 g: 2.30e+00 h: 1.29e-01 s: 4.63e-01 e: 2 it: 1.00e-05 tt: 5.25e-04
23: f: 2.911794e-02 d: 1.08e-02 g: 2.55e+00 h: 6.55e-02 s: 1.00e+00 e: 1 it: 5.01e-06 tt: 5.34e-04
24: f: 1.457683e-02 d: 1.45e-02 g: 2.77e-01 h: 6.37e-02 s: 6.14e-01 e: 1 it: 4.05e-06 tt: 5.42e-04
25: f: 8.577515e-03 d: 6.00e-03 g: 2.86e+00 h: 1.40e-01 s: 1.00e+00 e: 1 it: 3.81e-06 tt: 5.49e-04
26: f: 3.486574e-03 d: 5.09e-03 g: 1.76e-01 h: 1.23e-02 s: 1.00e+00 e: 1 it: 4.05e-06 tt: 5.57e-04
27: f: 1.257570e-03 d: 2.23e-03 g: 1.39e-01 h: 5.08e-02 s: 1.00e+00 e: 1 it: 3.81e-06 tt: 5.65e-04
28: f: 2.783568e-04 d: 9.79e-04 g: 6.20e-01 h: 6.47e-02 s: 1.00e+00 e: 1 it: 4.05e-06 tt: 5.73e-04
29: f: 2.533399e-05 d: 2.53e-04 g: 1.68e-02 h: 1.98e-03 s: 1.00e+00 e: 1 it: 4.05e-06 tt: 5.81e-04
30: f: 7.591572e-07 d: 2.46e-05 g: 5.40e-03 h: 9.27e-03 s: 1.00e+00 e: 1 it: 5.96e-06 tt: 6.30e-04
31: f: 1.902460e-09 d: 7.57e-07 g: 1.62e-03 h: 1.89e-03 s: 1.00e+00 e: 1 it: 4.05e-06 tt: 6.39e-04
32: f: 1.003030e-12 d: 1.90e-09 g: 3.50e-05 h: 3.52e-05 s: 1.00e+00 e: 1 it: 3.81e-06 tt: 6.47e-04
33: f: 4.835994e-17 d: 1.00e-12 g: 1.05e-07 h: 1.13e-06 s: 1.00e+00 e: 1 it: 4.05e-06 tt: 6.59e-04
34: f: 1.885250e-22 d: 4.84e-17 g: 2.69e-10 h: 1.45e-08 s: 1.00e+00 e: 1 it: 4.05e-06 tt: 6.67e-04
Solver Summary (v 2.1.0-eigen-(3.4.0)-lapack-suitesparse-(5.10.1)-cxsparse-(3.2.0)-acceleratesparse-eigensparse-no_openmp)
Parameters 2
Line search direction LBFGS (20)
Line search type CUBIC WOLFE
Cost:
Initial 2.420000e+01
Final 1.955192e-27
Change 2.420000e+01
Minimizer iterations 36
Time (in seconds):
Cost evaluation 0.000000 (0)
Gradient & cost evaluation 0.000005 (44)
Polynomial minimization 0.000041
Total 0.000368
Termination: CONVERGENCE (Parameter tolerance reached. Relative step_norm: 1.890726e-11 <= 1.000000e-08.)
Initial x: -1.2 y: 1
Final x: 1 y: 1
If you are unable to use automatic differentiation for some reason
(say beacause you need to call an external library), then you can
use numeric differentiation. In that case the functor is defined as
follows [#f2]_.
.. code::
// f(x,y) = (1-x)^2 + 100(y - x^2)^2;
struct Rosenbrock {
bool operator()(const double* parameters, double* cost) const {
const double x = parameters[0];
const double y = parameters[1];
cost[0] = (1.0 - x) * (1.0 - x) + 100.0 * (y - x * x) * (y - x * x);
return true;
}
static ceres::FirstOrderFunction* Create() {
constexpr int kNumParameters = 2;
return new ceres::NumericDiffFirstOrderFunction<Rosenbrock,
ceres::CENTRAL,
kNumParameters>(
new Rosenbrock);
}
};
And finally, if you would rather compute the derivatives by hand (say
because the size of the parameter vector is too large to be
automatically differentiated). Then you should define an instance of
`FirstOrderFunction`, which is the analog of :class:`CostFunction` for
non-linear least squares problems [#f3]_.
.. code::
// f(x,y) = (1-x)^2 + 100(y - x^2)^2;
class Rosenbrock final : public ceres::FirstOrderFunction {
public:
~Rosenbrock() override {}
bool Evaluate(const double* parameters,
double* cost,
double* gradient) const override {
const double x = parameters[0];
const double y = parameters[1];
cost[0] = (1.0 - x) * (1.0 - x) + 100.0 * (y - x * x) * (y - x * x);
if (gradient) {
gradient[0] = -2.0 * (1.0 - x) - 200.0 * (y - x * x) * 2.0 * x;
gradient[1] = 200.0 * (y - x * x);
}
return true;
}
int NumParameters() const override { return 2; }
};
.. rubric:: Footnotes
.. [#f1] `examples/rosenbrock.cc
<https://ceres-solver.googlesource.com/ceres-solver/+/master/examples/rosenbrock.cc>`_
.. [#f2] `examples/rosenbrock_numeric_diff.cc
<https://ceres-solver.googlesource.com/ceres-solver/+/master/examples/rosenbrock_numeric_diff.cc>`_
.. [#f3] `examples/rosenbrock_analytic_diff.cc
<https://ceres-solver.googlesource.com/ceres-solver/+/master/examples/rosenbrock_analytic_diff.cc>`_
|
