Debian Codegraph @

third-party/boost-math/include/boost/math/tools/minima.hpp

raw
1 // (C) Copyright John Maddock 2006.
2 // Use, modification and distribution are subject to the
3 // Boost Software License, Version 1.0. (See accompanying file
4 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5
6
7 #ifndef BOOST_MATH_TOOLS_MINIMA_HPP
8 #define BOOST_MATH_TOOLS_MINIMA_HPP
9
10 #ifdef _MSC_VER
11 #pragma once
12 #endif
13
14 #include <boost/math/tools/config.hpp>
15 #include <boost/math/tools/cstdint.hpp>
16 #include <boost/math/tools/tuple.hpp>
17 #include <boost/math/tools/numeric_limits.hpp>
18 #include <boost/math/tools/precision.hpp>
19 #include <boost/math/tools/utility.hpp>
20 #include <boost/math/policies/policy.hpp>
21
22 namespace boost{ namespace math{ namespace tools{
23
24 template <class F, class T>
25 BOOST_MATH_GPU_ENABLED boost::math::pair<T, T> brent_find_minima(F f, T min, T max, int bits, boost::math::uintmax_t& max_iter)
26 noexcept(BOOST_MATH_IS_FLOAT(T)
27 #ifndef BOOST_MATH_HAS_GPU_SUPPORT
28 && noexcept(std::declval<F>()(std::declval<T>()))
29 #endif
30 )
31 {
32 BOOST_MATH_STD_USING
33 bits = (boost::math::min)(policies::digits<T, policies::policy<> >() / 2, bits);
34 T tolerance = static_cast<T>(ldexp(1.0, 1-bits));
35 T x; // minima so far
36 T w; // second best point
37 T v; // previous value of w
38 T u; // most recent evaluation point
39 T delta; // The distance moved in the last step
40 T delta2; // The distance moved in the step before last
41 T fu, fv, fw, fx; // function evaluations at u, v, w, x
42 T mid; // midpoint of min and max
43 T fract1, fract2; // minimal relative movement in x
44
45 static const T golden = 0.3819660f; // golden ratio, don't need too much precision here!
46
47 x = w = v = max;
48 fw = fv = fx = f(x);
49 delta2 = delta = 0;
50
51 boost::math::uintmax_t count = max_iter;
52
53 do{
54 // get midpoint
55 mid = (min + max) / 2;
56 // work out if we're done already:
57 fract1 = tolerance * fabs(x) + tolerance / 4;
58 fract2 = 2 * fract1;
59 if(fabs(x - mid) <= (fract2 - (max - min) / 2))
60 break;
61
62 if(fabs(delta2) > fract1)
63 {
64 // try and construct a parabolic fit:
65 T r = (x - w) * (fx - fv);
66 T q = (x - v) * (fx - fw);
67 T p = (x - v) * q - (x - w) * r;
68 q = 2 * (q - r);
69 if(q > 0)
70 p = -p;
71 q = fabs(q);
72 T td = delta2;
73 delta2 = delta;
74 // determine whether a parabolic step is acceptable or not:
75 if((fabs(p) >= fabs(q * td / 2)) || (p <= q * (min - x)) || (p >= q * (max - x)))
76 {
77 // nope, try golden section instead
78 delta2 = (x >= mid) ? min - x : max - x;
79 delta = golden * delta2;
80 }
81 else
82 {
83 // whew, parabolic fit:
84 delta = p / q;
85 u = x + delta;
86 if(((u - min) < fract2) || ((max- u) < fract2))
87 delta = (mid - x) < 0 ? (T)-fabs(fract1) : (T)fabs(fract1);
88 }
89 }
90 else
91 {
92 // golden section:
93 delta2 = (x >= mid) ? min - x : max - x;
94 delta = golden * delta2;
95 }
96 // update current position:
97 u = (fabs(delta) >= fract1) ? T(x + delta) : (delta > 0 ? T(x + fabs(fract1)) : T(x - fabs(fract1)));
98 fu = f(u);
99 if(fu <= fx)
100 {
101 // good new point is an improvement!
102 // update brackets:
103 if(u >= x)
104 min = x;
105 else
106 max = x;
107 // update control points:
108 v = w;
109 w = x;
110 x = u;
111 fv = fw;
112 fw = fx;
113 fx = fu;
114 }
115 else
116 {
117 // Oh dear, point u is worse than what we have already,
118 // even so it *must* be better than one of our endpoints:
119 if(u < x)
120 min = u;
121 else
122 max = u;
123 if((fu <= fw) || (w == x))
124 {
125 // however it is at least second best:
126 v = w;
127 w = u;
128 fv = fw;
129 fw = fu;
130 }
131 else if((fu <= fv) || (v == x) || (v == w))
132 {
133 // third best:
134 v = u;
135 fv = fu;
136 }
137 }
138
139 }while(--count);
140
141 max_iter -= count;
142
143 return boost::math::make_pair(x, fx);
144 }
145
146 template <class F, class T>
147 BOOST_MATH_GPU_ENABLED inline boost::math::pair<T, T> brent_find_minima(F f, T min, T max, int digits)
148 noexcept(BOOST_MATH_IS_FLOAT(T)
149 #ifndef BOOST_MATH_HAS_GPU_SUPPORT
150 && noexcept(std::declval<F>()(std::declval<T>()))
151 #endif
152 )
153 {
154 boost::math::uintmax_t m = (boost::math::numeric_limits<boost::math::uintmax_t>::max)();
155 return brent_find_minima(f, min, max, digits, m);
156 }
157
158 }}} // namespaces
159
160 #endif
161
162
163
164