File: Multimin-Algorithms-without-Derivatives.html

package info (click to toggle)
gsl-ref-html 2.3-1
  • links: PTS
  • area: non-free
  • in suites: buster, sid
  • size: 6,876 kB
  • ctags: 4,574
  • sloc: makefile: 35
file content (143 lines) | stat: -rw-r--r-- 7,729 bytes parent folder | download
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
<!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 &ndash; Reference Manual: Multimin Algorithms without Derivatives</title>

<meta name="description" content="GNU Scientific Library &ndash; Reference Manual: Multimin Algorithms without Derivatives">
<meta name="keywords" content="GNU Scientific Library &ndash; Reference Manual: Multimin Algorithms without Derivatives">
<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-Examples.html#Multimin-Examples" rel="next" title="Multimin Examples">
<link href="Multimin-Algorithms-with-Derivatives.html#Multimin-Algorithms-with-Derivatives" rel="previous" title="Multimin Algorithms with Derivatives">
<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-Algorithms-without-Derivatives"></a>
<div class="header">
<p>
Next: <a href="Multimin-Examples.html#Multimin-Examples" accesskey="n" rel="next">Multimin Examples</a>, Previous: <a href="Multimin-Algorithms-with-Derivatives.html#Multimin-Algorithms-with-Derivatives" accesskey="p" rel="previous">Multimin Algorithms with Derivatives</a>, Up: <a href="Multidimensional-Minimization.html#Multidimensional-Minimization" accesskey="u" rel="up">Multidimensional Minimization</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Algorithms-without-Derivatives-2"></a>
<h3 class="section">37.8 Algorithms without Derivatives</h3>

<p>The algorithms described in this section use only the value of the function
at each evaluation point.
</p>
<dl>
<dt><a name="index-gsl_005fmultimin_005ffminimizer_005fnmsimplex2"></a>Minimizer: <strong>gsl_multimin_fminimizer_nmsimplex2</strong></dt>
<dt><a name="index-gsl_005fmultimin_005ffminimizer_005fnmsimplex"></a>Minimizer: <strong>gsl_multimin_fminimizer_nmsimplex</strong></dt>
<dd><a name="index-Nelder_002dMead-simplex-algorithm-for-minimization"></a>
<a name="index-simplex-algorithm_002c-minimization"></a>
<a name="index-minimization_002c-simplex-algorithm"></a>
<p>These methods use the Simplex algorithm of Nelder and Mead. 
Starting from the initial vector <em><var>x</var> = p_0</em>, the algorithm
constructs an additional <em>n</em> vectors <em>p_i</em>
using the step size vector <em>s = <var>step_size</var></em> as follows:
</p>
<div class="example">
<pre class="example">p_0 = (x_0, x_1, ... , x_n) 
p_1 = (x_0 + s_0, x_1, ... , x_n) 
p_2 = (x_0, x_1 + s_1, ... , x_n) 
... = ...
p_n = (x_0, x_1, ... , x_n + s_n)
</pre></div>

<p>These vectors form the <em>n+1</em> vertices of a simplex in <em>n</em>
dimensions.  On each iteration the algorithm uses simple geometrical
transformations to update the vector corresponding to the highest
function value.  The geometric transformations are reflection,
reflection followed by expansion, contraction and multiple
contraction.  Using these transformations the simplex moves through
the space towards the minimum, where it contracts itself.
</p>
<p>After each iteration, the best vertex is returned.  Note, that due to
the nature of the algorithm not every step improves the current
best parameter vector.  Usually several iterations are required.
</p>
<p>The minimizer-specific characteristic size is calculated as the
average distance from the geometrical center of the simplex to all its
vertices.  This size can be used as a stopping criteria, as the
simplex contracts itself near the minimum. The size is returned by the
function <code>gsl_multimin_fminimizer_size</code>.
</p>
<p>The <code>nmsimplex2</code> version of this minimiser is a new <em>O(N)</em> operations
implementation of the earlier <em>O(N^2)</em> operations <code>nmsimplex</code>
minimiser.  It uses the same underlying algorithm, but the simplex
updates are computed more efficiently for high-dimensional problems.
In addition, the size of simplex is calculated as the <small>RMS</small>
distance of each vertex from the center rather than the mean distance,
allowing a linear update of this quantity on each step.  The memory usage is
<em>O(N^2)</em> for both algorithms.
</p></dd></dl>

<dl>
<dt><a name="index-gsl_005fmultimin_005ffminimizer_005fnmsimplex2rand"></a>Minimizer: <strong>gsl_multimin_fminimizer_nmsimplex2rand</strong></dt>
<dd><p>This method is a variant of <code>nmsimplex2</code> which initialises the
simplex around the starting point <var>x</var> using a randomly-oriented
set of basis vectors instead of the fixed coordinate axes. The
final dimensions of the simplex are scaled along the coordinate axes by the
vector <var>step_size</var>.  The randomisation uses a simple deterministic
generator so that repeated calls to <code>gsl_multimin_fminimizer_set</code> for
a given solver object will vary the orientation in a well-defined way.
</p></dd></dl>

<hr>
<div class="header">
<p>
Next: <a href="Multimin-Examples.html#Multimin-Examples" accesskey="n" rel="next">Multimin Examples</a>, Previous: <a href="Multimin-Algorithms-with-Derivatives.html#Multimin-Algorithms-with-Derivatives" accesskey="p" rel="previous">Multimin Algorithms with Derivatives</a>, Up: <a href="Multidimensional-Minimization.html#Multidimensional-Minimization" accesskey="u" rel="up">Multidimensional Minimization</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>