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
|
<!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: Multimin Overview</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Multimin Overview">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Multimin Overview">
<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="Multidimensional-Minimization.html#Multidimensional-Minimization" rel="up" title="Multidimensional Minimization">
<link href="Multimin-Caveats.html#Multimin-Caveats" rel="next" title="Multimin Caveats">
<link href="Multidimensional-Minimization.html#Multidimensional-Minimization" rel="previous" title="Multidimensional Minimization">
<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="Multimin-Overview"></a>
<div class="header">
<p>
Next: <a href="Multimin-Caveats.html#Multimin-Caveats" accesskey="n" rel="next">Multimin Caveats</a>, Up: <a href="Multidimensional-Minimization.html#Multidimensional-Minimization" accesskey="u" rel="up">Multidimensional Minimization</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Overview-3"></a>
<h3 class="section">37.1 Overview</h3>
<p>The problem of multidimensional minimization requires finding a point
<em>x</em> such that the scalar function,
</p>
<div class="example">
<pre class="example">f(x_1, …, x_n)
</pre></div>
<p>takes a value which is lower than at any neighboring point. For smooth
functions the gradient <em>g = \nabla f</em> vanishes at the minimum. In
general there are no bracketing methods available for the
minimization of <em>n</em>-dimensional functions. The algorithms
proceed from an initial guess using a search algorithm which attempts
to move in a downhill direction.
</p>
<p>Algorithms making use of the gradient of the function perform a
one-dimensional line minimisation along this direction until the lowest
point is found to a suitable tolerance. The search direction is then
updated with local information from the function and its derivatives,
and the whole process repeated until the true <em>n</em>-dimensional
minimum is found.
</p>
<p>Algorithms which do not require the gradient of the function use
different strategies. For example, the Nelder-Mead Simplex algorithm
maintains <em>n+1</em> trial parameter vectors as the vertices of a
<em>n</em>-dimensional simplex. On each iteration it tries to improve
the worst vertex of the simplex by geometrical transformations. The
iterations are continued until the overall size of the simplex has
decreased sufficiently.
</p>
<p>Both types of algorithms use a standard framework. The user provides a
high-level driver for the algorithms, and the library provides the
individual functions necessary for each of the steps. There are three
main phases of the iteration. The steps are,
</p>
<ul>
<li> initialize minimizer state, <var>s</var>, for algorithm <var>T</var>
</li><li> update <var>s</var> using the iteration <var>T</var>
</li><li> test <var>s</var> for convergence, and repeat iteration if necessary
</li></ul>
<p>Each iteration step consists either of an improvement to the
line-minimisation in the current direction or an update to the search
direction itself. The state for the minimizers is held in a
<code>gsl_multimin_fdfminimizer</code> struct or a
<code>gsl_multimin_fminimizer</code> struct.
</p>
<hr>
<div class="header">
<p>
Next: <a href="Multimin-Caveats.html#Multimin-Caveats" accesskey="n" rel="next">Multimin Caveats</a>, Up: <a href="Multidimensional-Minimization.html#Multidimensional-Minimization" accesskey="u" rel="up">Multidimensional Minimization</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
