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
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 The GSL Team.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "GNU General Public License" and "Free Software
Needs Free Documentation", the Front-Cover text being "A GNU Manual",
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled "GNU Free Documentation
License".
(a) The Back-Cover Text is: "You have the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library – Reference Manual: Minimization Algorithms</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Minimization Algorithms">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Minimization Algorithms">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="One-dimensional-Minimization.html#One-dimensional-Minimization" rel="up" title="One dimensional Minimization">
<link href="Minimization-Examples.html#Minimization-Examples" rel="next" title="Minimization Examples">
<link href="Minimization-Stopping-Parameters.html#Minimization-Stopping-Parameters" rel="previous" title="Minimization Stopping Parameters">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>
</head>
<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Minimization-Algorithms"></a>
<div class="header">
<p>
Next: <a href="Minimization-Examples.html#Minimization-Examples" accesskey="n" rel="next">Minimization Examples</a>, Previous: <a href="Minimization-Stopping-Parameters.html#Minimization-Stopping-Parameters" accesskey="p" rel="previous">Minimization Stopping Parameters</a>, Up: <a href="One-dimensional-Minimization.html#One-dimensional-Minimization" accesskey="u" rel="up">One dimensional Minimization</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Minimization-Algorithms-1"></a>
<h3 class="section">35.7 Minimization Algorithms</h3>
<p>The minimization algorithms described in this section require an initial
interval which is guaranteed to contain a minimum—if <em>a</em> and
<em>b</em> are the endpoints of the interval and <em>x</em> is an estimate
of the minimum then <em>f(a) > f(x) < f(b)</em>. This ensures that the
function has at least one minimum somewhere in the interval. If a valid
initial interval is used then these algorithm cannot fail, provided the
function is well-behaved.
</p>
<dl>
<dt><a name="index-gsl_005fmin_005ffminimizer_005fgoldensection"></a>Minimizer: <strong>gsl_min_fminimizer_goldensection</strong></dt>
<dd>
<a name="index-golden-section-algorithm-for-finding-minima"></a>
<a name="index-minimum-finding_002c-golden-section-algorithm"></a>
<p>The <em>golden section algorithm</em> is the simplest method of bracketing
the minimum of a function. It is the slowest algorithm provided by the
library, with linear convergence.
</p>
<p>On each iteration, the algorithm first compares the subintervals from
the endpoints to the current minimum. The larger subinterval is divided
in a golden section (using the famous ratio <em>(3-\sqrt 5)/2 =
0.3819660</em>…) and the value of the function at this new point is
calculated. The new value is used with the constraint <em>f(a') >
f(x') < f(b')</em> to a select new interval containing the minimum, by
discarding the least useful point. This procedure can be continued
indefinitely until the interval is sufficiently small. Choosing the
golden section as the bisection ratio can be shown to provide the
fastest convergence for this type of algorithm.
</p>
</dd></dl>
<dl>
<dt><a name="index-gsl_005fmin_005ffminimizer_005fbrent"></a>Minimizer: <strong>gsl_min_fminimizer_brent</strong></dt>
<dd><a name="index-Brent_0027s-method-for-finding-minima"></a>
<a name="index-minimum-finding_002c-Brent_0027s-method"></a>
<p>The <em>Brent minimization algorithm</em> combines a parabolic
interpolation with the golden section algorithm. This produces a fast
algorithm which is still robust.
</p>
<p>The outline of the algorithm can be summarized as follows: on each
iteration Brent’s method approximates the function using an
interpolating parabola through three existing points. The minimum of the
parabola is taken as a guess for the minimum. If it lies within the
bounds of the current interval then the interpolating point is accepted,
and used to generate a smaller interval. If the interpolating point is
not accepted then the algorithm falls back to an ordinary golden section
step. The full details of Brent’s method include some additional checks
to improve convergence.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005fmin_005ffminimizer_005fquad_005fgolden"></a>Minimizer: <strong>gsl_min_fminimizer_quad_golden</strong></dt>
<dd><a name="index-safeguarded-step_002dlength-algorithm"></a>
<p>This is a variant of Brent’s algorithm which uses the safeguarded
step-length algorithm of Gill and Murray.
</p></dd></dl>
<hr>
<div class="header">
<p>
Next: <a href="Minimization-Examples.html#Minimization-Examples" accesskey="n" rel="next">Minimization Examples</a>, Previous: <a href="Minimization-Stopping-Parameters.html#Minimization-Stopping-Parameters" accesskey="p" rel="previous">Minimization Stopping Parameters</a>, Up: <a href="One-dimensional-Minimization.html#One-dimensional-Minimization" accesskey="u" rel="up">One dimensional Minimization</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
