3
<title>Multimin Overview - GNU Scientific Library -- Reference Manual</title>
4
<meta http-equiv="Content-Type" content="text/html">
5
<meta name="description" content="GNU Scientific Library -- Reference Manual">
6
<meta name="generator" content="makeinfo 4.8">
7
<link title="Top" rel="start" href="index.html#Top">
8
<link rel="up" href="Multidimensional-Minimization.html#Multidimensional-Minimization" title="Multidimensional Minimization">
9
<link rel="next" href="Multimin-Caveats.html#Multimin-Caveats" title="Multimin Caveats">
10
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
12
Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 The GSL Team.
14
Permission is granted to copy, distribute and/or modify this document
15
under the terms of the GNU Free Documentation License, Version 1.2 or
16
any later version published by the Free Software Foundation; with the
17
Invariant Sections being ``GNU General Public License'' and ``Free Software
18
Needs Free Documentation'', the Front-Cover text being ``A GNU Manual'',
19
and with the Back-Cover Text being (a) (see below). A copy of the
20
license is included in the section entitled ``GNU Free Documentation
23
(a) The Back-Cover Text is: ``You have freedom to copy and modify this
24
GNU Manual, like GNU software.''-->
25
<meta http-equiv="Content-Style-Type" content="text/css">
26
<style type="text/css"><!--
27
pre.display { font-family:inherit }
28
pre.format { font-family:inherit }
29
pre.smalldisplay { font-family:inherit; font-size:smaller }
30
pre.smallformat { font-family:inherit; font-size:smaller }
31
pre.smallexample { font-size:smaller }
32
pre.smalllisp { font-size:smaller }
33
span.sc { font-variant:small-caps }
34
span.roman { font-family:serif; font-weight:normal; }
35
span.sansserif { font-family:sans-serif; font-weight:normal; }
41
<a name="Multimin-Overview"></a>
42
Next: <a rel="next" accesskey="n" href="Multimin-Caveats.html#Multimin-Caveats">Multimin Caveats</a>,
43
Up: <a rel="up" accesskey="u" href="Multidimensional-Minimization.html#Multidimensional-Minimization">Multidimensional Minimization</a>
47
<h3 class="section">35.1 Overview</h3>
49
<p>The problem of multidimensional minimization requires finding a point
50
x such that the scalar function,
51
takes a value which is lower than at any neighboring point. For smooth
52
functions the gradient g = \nabla f vanishes at the minimum. In
53
general there are no bracketing methods available for the
54
minimization of n-dimensional functions. The algorithms
55
proceed from an initial guess using a search algorithm which attempts
56
to move in a downhill direction.
58
<p>Algorithms making use of the gradient of the function perform a
59
one-dimensional line minimisation along this direction until the lowest
60
point is found to a suitable tolerance. The search direction is then
61
updated with local information from the function and its derivatives,
62
and the whole process repeated until the true n-dimensional
65
<p>The Nelder-Mead Simplex algorithm applies a different strategy. It
66
maintains n+1 trial parameter vectors as the vertices of a
67
n-dimensional simplex. In each iteration step it tries to
68
improve the worst vertex by a simple geometrical transformation until
69
the size of the simplex falls below a given tolerance.
71
<p>Both types of algorithms use a standard framework. The user provides a
72
high-level driver for the algorithms, and the library provides the
73
individual functions necessary for each of the steps. There are three
74
main phases of the iteration. The steps are,
77
<li>initialize minimizer state, <var>s</var>, for algorithm <var>T</var>
79
<li>update <var>s</var> using the iteration <var>T</var>
81
<li>test <var>s</var> for convergence, and repeat iteration if necessary
84
<p class="noindent">Each iteration step consists either of an improvement to the
85
line-minimisation in the current direction or an update to the search
86
direction itself. The state for the minimizers is held in a
87
<code>gsl_multimin_fdfminimizer</code> struct or a
88
<code>gsl_multimin_fminimizer</code> struct.