Debian Codegraph @

include/deal.II/optimization/solver_bfgs.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2018 - 2025 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_solver_bfgs_h
16 #define dealii_solver_bfgs_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/lac/solver.h>
21
22 #include <deal.II/numerics/history.h>
23
24 #include <deal.II/optimization/line_minimization.h>
25
26 #include <boost/signals2.hpp>
27
28 #include <limits>
29
30 DEAL_II_NAMESPACE_OPEN
31
32 /**
33 * Implement the limited memory BFGS minimization method.
34 *
35 * This class implements a method to minimize a given function for which only
36 * the values of the function and its derivatives, but not its second
37 * derivatives are available. The BFGS method is a variation of the Newton
38 * method for function minimization in which the Hessian matrix is only
39 * approximated. In particular, the Hessian is updated using the formula of
40 * Broyden, Fletcher, Goldfarb, and Shanno (BFGS):
41 * @f{align*}{
42 * H^{(k+1)} &= \left[
43 * I-\rho_{(k)} s^{(k)} \otimes y^{(k)}
44 * \right]
45 * H^{(k)}
46 * \left[
47 * I -\rho^{(k)} y^{(k)} \otimes s^{(k)}
48 * \right]
49 * +
50 * \rho^{(k)} s^{(k)} \otimes s^{(k)} \\
51 * y^{(k)} &\dealcoloneq g^{(k+1)} - g^{(k)} \\
52 * s^{(k)} &\dealcoloneq x^{(k+1)} - x^{(k)} \\
53 * \rho^{(k)} &\dealcoloneq \frac{1}{y^{(k)} \cdot s^{(k)}}
54 * @f}
55 * for a symmetric positive definite $H$. Limited memory variant is
56 * implemented via the two-loop recursion.
57 */
58 template <typename VectorType>
59 class SolverBFGS : public SolverBase<VectorType>
60 {
61 public:
62 /**
63 * Number type.
64 */
65 using Number = typename VectorType::value_type;
66
67
68 /**
69 * Standardized data struct to pipe additional data to the solver.
70 */
71 struct AdditionalData
72 {
73 /**
74 * Constructor.
75 */
76 explicit AdditionalData(const unsigned int max_history_size = 5,
77 const bool debug_output = false);
78
79 /**
80 * Maximum history size.
81 */
82 unsigned int max_history_size;
83
84 /**
85 * Print extra debug output to deallog.
86 */
87 bool debug_output;
88 };
89
90
91 /**
92 * Constructor.
93 */
94 explicit SolverBFGS(SolverControl &residual_control,
95 const AdditionalData &data = AdditionalData());
96
97 /**
98 * Solve the unconstrained minimization problem
99 * \f[
100 * \min_{\mathbf x} f(\mathbf x)
101 * \f]
102 * starting from initial state @p x.
103 *
104 * The function @p compute takes two arguments indicating the values of $x$
105 * and of the gradient $g=\nabla f(\mathbf x)=\frac{\partial f}{\partial
106 * \mathbf x}$. When called, it needs to update the gradient $g$ at the given
107 * location $x$ and return the value of the function being minimized, i.e.,
108 * $f(\mathbf x)$.
109 */
110 void
111 solve(
112 const std::function<Number(const VectorType &x, VectorType &g)> &compute,
113 VectorType &x);
114
115 /**
116 * Connect a slot to perform a custom line-search.
117 *
118 * Given the value of function @p f, the current value of unknown @p x,
119 * the gradient @p g and the search direction @p p,
120 * return the size $\alpha$ of the step $x \leftarrow x + \alpha p$,
121 * and update @p x, @p g and @p f accordingly.
122 */
123 boost::signals2::connection
124 connect_line_search_slot(
125 const std::function<
126 Number(Number &f, VectorType &x, VectorType &g, const VectorType &p)>
127 &slot);
128
129 /**
130 * Connect a slot to perform a custom preconditioning.
131 *
132 * The preconditioner is applied inside the two loop recursion to
133 * vector `g` using the history of position increments `s` and
134 * gradient increments `y`.
135 *
136 * One possibility is to use the oldest `s,y` pair:
137 * @code
138 * const auto preconditioner = [](VectorType & g,
139 * const FiniteSizeHistory<VectorType> &s,
140 * const FiniteSizeHistory<VectorType> &y) {
141 * if (s.size() > 0)
142 * {
143 * const unsigned int i = s.size() - 1;
144 * const auto yy = y[i] * y[i];
145 * const auto sy = s[i] * y[i];
146 * Assert(yy > 0 && sy > 0, ExcInternalError());
147 * g *= sy / yy;
148 * }
149 * };
150 * @endcode
151 *
152 * No preconditioning is performed if the code using this class has not
153 * attached anything to the signal.
154 */
155 boost::signals2::connection
156 connect_preconditioner_slot(
157 const std::function<void(VectorType &g,
158 const FiniteSizeHistory<VectorType> &s,
159 const FiniteSizeHistory<VectorType> &y)> &slot);
160
161
162 protected:
163 /**
164 * Additional data to the solver.
165 */
166 const AdditionalData additional_data;
167
168 /**
169 * Signal used to perform line search.
170 */
171 boost::signals2::signal<
172 Number(Number &f, VectorType &x, VectorType &g, const VectorType &p)>
173 line_search_signal;
174
175 /**
176 * Signal used to perform preconditioning.
177 */
178 boost::signals2::signal<void(VectorType &g,
179 const FiniteSizeHistory<VectorType> &s,
180 const FiniteSizeHistory<VectorType> &y)>
181 preconditioner_signal;
182 };
183
184
185 // ------------------- inline and template functions ----------------
186 #ifndef DOXYGEN
187
188 template <typename VectorType>
189 SolverBFGS<VectorType>::AdditionalData::AdditionalData(
190 const unsigned int max_history_size_,
191 const bool debug_output_)
192 : max_history_size(max_history_size_)
193 , debug_output(debug_output_)
194 {}
195
196
197
198 template <typename VectorType>
199 SolverBFGS<VectorType>::SolverBFGS(SolverControl &solver_control,
200 const AdditionalData &data)
201 : SolverBase<VectorType>(solver_control)
202 , additional_data(data)
203 {}
204
205
206
207 template <typename VectorType>
208 boost::signals2::connection
209 SolverBFGS<VectorType>::connect_line_search_slot(
210 const std::function<
211 Number(Number &f, VectorType &x, VectorType &g, const VectorType &p)> &slot)
212 {
213 Assert(line_search_signal.empty(),
214 ExcMessage("One should not attach more than one line search signal."));
215 return line_search_signal.connect(slot);
216 }
217
218
219
220 template <typename VectorType>
221 boost::signals2::connection
222 SolverBFGS<VectorType>::connect_preconditioner_slot(
223 const std::function<void(VectorType &g,
224 const FiniteSizeHistory<VectorType> &s,
225 const FiniteSizeHistory<VectorType> &y)> &slot)
226 {
227 Assert(preconditioner_signal.empty(),
228 ExcMessage(
229 "One should not attach more than one preconditioner signal."));
230 return preconditioner_signal.connect(slot);
231 }
232
233
234
235 template <typename VectorType>
236 void
237 SolverBFGS<VectorType>::solve(
238 const std::function<typename VectorType::value_type(const VectorType &x,
239 VectorType &f)> &compute,
240 VectorType &x)
241 {
242 // Also see scipy Fortran implementation
243 // https://github.com/scipy/scipy/blob/master/scipy/optimize/lbfgsb_src/lbfgsb.f
244 // and Octave-optim implementation:
245 // https://sourceforge.net/p/octave/optim/ci/default/tree/src/__bfgsmin.cc
246 LogStream::Prefix prefix("BFGS");
247
248 // default line search:
249 bool first_step = true;
250 Number f_prev = 0.;
251 // provide default line search if no signal was attached
252 VectorType x0;
253 if (line_search_signal.empty())
254 {
255 x0.reinit(x);
256 const auto default_line_min =
257 [&](Number &f, VectorType &x, VectorType &g, const VectorType &p) {
258 const Number f0 = f;
259 const Number g0 = g * p;
260 Assert(g0 < 0,
261 ExcMessage(
262 "Function does not decrease along the current direction"));
263
264 // save current solution value (to be used in line_search):
265 x0 = x;
266
267 // see scipy implementation
268 // https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.line_search.html#scipy.optimize.line_search
269 // and Eq. 2.6.8 in Fletcher 2013, Practical methods of optimization
270 Number df = f_prev - f;
271 Assert(first_step || df >= 0.,
272 ExcMessage("Function value is not decreasing"));
273 df = std::max(df, 100. * std::numeric_limits<Number>::epsilon());
274 // guess a reasonable first step:
275 const Number a1 =
276 (first_step ? 1. : std::min(1., -1.01 * 2. * df / g0));
277 Assert(a1 > 0., ExcInternalError());
278 f_prev = f;
279
280 // 1d line-search function
281 const auto line_func =
282 [&](const Number &x_line) -> std::pair<Number, Number> {
283 x = x0;
284 x.add(x_line, p);
285 f = compute(x, g);
286 const Number g_line = g * p;
287 return std::make_pair(f, g_line);
288 };
289
290 // loose line search:
291 const auto res = LineMinimization::line_search<Number>(
292 line_func,
293 f0,
294 g0,
295 LineMinimization::poly_fit<Number>,
296 a1,
297 0.9,
298 0.001);
299
300 if (first_step)
301 first_step = false;
302
303 return res.first;
304 };
305 this->connect_line_search_slot(default_line_min);
306 }
307
308 // FIXME: Octave has convergence in terms of:
309 // function change tolerance, default 1e-12
310 // parameter change tolerance, default 1e-6
311 // gradient tolerance, default 1e-5
312 // SolverBase and/or SolverControl need extension
313
314 VectorType g(x), p(x), y_k(x), s_k(x);
315
316 std::vector<Number> c1;
317 c1.reserve(additional_data.max_history_size);
318
319 // limited history
320 FiniteSizeHistory<VectorType> y(additional_data.max_history_size);
321 FiniteSizeHistory<VectorType> s(additional_data.max_history_size);
322 FiniteSizeHistory<Number> rho(additional_data.max_history_size);
323
324 unsigned int m = 0;
325 Number f;
326
327 SolverControl::State conv = SolverControl::iterate;
328 unsigned int k = 0;
329
330 f = compute(x, g);
331
332 conv = this->iteration_status(k, g.l2_norm(), x);
333 if (conv != SolverControl::iterate)
334 return;
335
336 while (conv == SolverControl::iterate)
337 {
338 if (additional_data.debug_output)
339 deallog << "Iteration " << k << " history " << m << std::endl
340 << "f=" << f << std::endl;
341
342 // 1. Two loop recursion to calculate p = - H*g
343 c1.resize(m);
344 p = g;
345 // first loop:
346 for (unsigned int i = 0; i < m; ++i)
347 {
348 c1[i] = rho[i] * (s[i] * p);
349 p.add(-c1[i], y[i]);
350 }
351 // H0
352 if (!preconditioner_signal.empty())
353 preconditioner_signal(p, s, y);
354
355 // second loop:
356 for (int i = m - 1; i >= 0; --i)
357 {
358 Assert(i >= 0, ExcInternalError());
359 const Number c2 = rho[i] * (y[i] * p);
360 p.add(c1[i] - c2, s[i]);
361 }
362 p *= -1.;
363
364 // 2. Line search
365 s_k = x;
366 y_k = g;
367 const Number alpha = line_search_signal(f, x, g, p)
368 .get(); // <-- signals return boost::optional
369 s_k.sadd(-1, 1, x);
370 y_k.sadd(-1, 1, g);
371
372 if (additional_data.debug_output)
373 deallog << "Line search a=" << alpha << " f=" << f << std::endl;
374
375 // 3. Check convergence
376 ++k;
377 const Number g_l2 = g.l2_norm();
378 conv = this->iteration_status(k, g_l2, x);
379 if (conv != SolverControl::iterate)
380 break;
381
382 // 4. Store s, y, rho
383 const Number curvature = s_k * y_k;
384 if (additional_data.debug_output)
385 deallog << "Curvature " << curvature << std::endl;
386
387 if (curvature > 0. && additional_data.max_history_size > 0)
388 {
389 s.add(s_k);
390 y.add(y_k);
391 rho.add(1. / curvature);
392 m = s.size();
393
394 Assert(y.size() == m, ExcInternalError());
395 Assert(rho.size() == m, ExcInternalError());
396 }
397
398 Assert(m <= additional_data.max_history_size, ExcInternalError());
399 }
400
401 // In the case of failure: throw exception.
402 AssertThrow(conv == SolverControl::success,
403 SolverControl::NoConvergence(k, g.l2_norm()));
404 }
405
406 #endif
407
408 DEAL_II_NAMESPACE_CLOSE
409
410 #endif