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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
<!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 Algorithms with Derivatives</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Multimin Algorithms with Derivatives">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Multimin Algorithms with 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-Algorithms-without-Derivatives.html#Multimin-Algorithms-without-Derivatives" rel="next" title="Multimin Algorithms without Derivatives">
<link href="Multimin-Stopping-Criteria.html#Multimin-Stopping-Criteria" rel="previous" title="Multimin Stopping Criteria">
<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-with-Derivatives"></a>
<div class="header">
<p>
Next: <a href="Multimin-Algorithms-without-Derivatives.html#Multimin-Algorithms-without-Derivatives" accesskey="n" rel="next">Multimin Algorithms without Derivatives</a>, Previous: <a href="Multimin-Stopping-Criteria.html#Multimin-Stopping-Criteria" accesskey="p" rel="previous">Multimin Stopping Criteria</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="Algorithms-with-Derivatives"></a>
<h3 class="section">37.7 Algorithms with Derivatives</h3>
<p>There are several minimization methods available. The best choice of
algorithm depends on the problem. The algorithms described in this
section use the value of the function and its gradient at each
evaluation point.
</p>
<dl>
<dt><a name="index-gsl_005fmultimin_005ffdfminimizer_005fconjugate_005ffr"></a>Minimizer: <strong>gsl_multimin_fdfminimizer_conjugate_fr</strong></dt>
<dd><a name="index-Fletcher_002dReeves-conjugate-gradient-algorithm_002c-minimization"></a>
<a name="index-Conjugate-gradient-algorithm_002c-minimization"></a>
<a name="index-minimization_002c-conjugate-gradient-algorithm"></a>
<p>This is the Fletcher-Reeves conjugate gradient algorithm. The conjugate
gradient algorithm proceeds as a succession of line minimizations. The
sequence of search directions is used to build up an approximation to the
curvature of the function in the neighborhood of the minimum.
</p>
<p>An initial search direction <var>p</var> is chosen using the gradient, and line
minimization is carried out in that direction. The accuracy of the line
minimization is specified by the parameter <var>tol</var>. The minimum
along this line occurs when the function gradient <var>g</var> and the search direction
<var>p</var> are orthogonal. The line minimization terminates when
<em>dot(p,g) < tol |p| |g|</em>. The
search direction is updated using the Fletcher-Reeves formula
<em>p' = g' - \beta g</em> where <em>\beta=-|g'|^2/|g|^2</em>, and
the line minimization is then repeated for the new search
direction.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005fmultimin_005ffdfminimizer_005fconjugate_005fpr"></a>Minimizer: <strong>gsl_multimin_fdfminimizer_conjugate_pr</strong></dt>
<dd><a name="index-Polak_002dRibiere-algorithm_002c-minimization"></a>
<a name="index-minimization_002c-Polak_002dRibiere-algorithm"></a>
<p>This is the Polak-Ribiere conjugate gradient algorithm. It is similar
to the Fletcher-Reeves method, differing only in the choice of the
coefficient <em>\beta</em>. Both methods work well when the evaluation
point is close enough to the minimum of the objective function that it
is well approximated by a quadratic hypersurface.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005fmultimin_005ffdfminimizer_005fvector_005fbfgs2"></a>Minimizer: <strong>gsl_multimin_fdfminimizer_vector_bfgs2</strong></dt>
<dt><a name="index-gsl_005fmultimin_005ffdfminimizer_005fvector_005fbfgs"></a>Minimizer: <strong>gsl_multimin_fdfminimizer_vector_bfgs</strong></dt>
<dd><a name="index-BFGS-algorithm_002c-minimization"></a>
<a name="index-minimization_002c-BFGS-algorithm"></a>
<p>These methods use the vector Broyden-Fletcher-Goldfarb-Shanno (BFGS)
algorithm. This is a quasi-Newton method which builds up an approximation
to the second derivatives of the function <em>f</em> using the difference
between successive gradient vectors. By combining the first and second
derivatives the algorithm is able to take Newton-type steps towards the
function minimum, assuming quadratic behavior in that region.
</p>
<p>The <code>bfgs2</code> version of this minimizer is the most efficient
version available, and is a faithful implementation of the line
minimization scheme described in Fletcher’s <cite>Practical Methods of
Optimization</cite>, Algorithms 2.6.2 and 2.6.4. It supersedes the original
<code>bfgs</code> routine and requires substantially fewer function and
gradient evaluations. The user-supplied tolerance <var>tol</var>
corresponds to the parameter <em>\sigma</em> used by Fletcher. A value
of 0.1 is recommended for typical use (larger values correspond to
less accurate line searches).
</p>
</dd></dl>
<dl>
<dt><a name="index-gsl_005fmultimin_005ffdfminimizer_005fsteepest_005fdescent"></a>Minimizer: <strong>gsl_multimin_fdfminimizer_steepest_descent</strong></dt>
<dd><a name="index-steepest-descent-algorithm_002c-minimization"></a>
<a name="index-minimization_002c-steepest-descent-algorithm"></a>
<p>The steepest descent algorithm follows the downhill gradient of the
function at each step. When a downhill step is successful the step-size
is increased by a factor of two. If the downhill step leads to a higher
function value then the algorithm backtracks and the step size is
decreased using the parameter <var>tol</var>. A suitable value of <var>tol</var>
for most applications is 0.1. The steepest descent method is
inefficient and is included only for demonstration purposes.
</p></dd></dl>
<hr>
<div class="header">
<p>
Next: <a href="Multimin-Algorithms-without-Derivatives.html#Multimin-Algorithms-without-Derivatives" accesskey="n" rel="next">Multimin Algorithms without Derivatives</a>, Previous: <a href="Multimin-Stopping-Criteria.html#Multimin-Stopping-Criteria" accesskey="p" rel="previous">Multimin Stopping Criteria</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>
|
