File: Nonlinear-Least_002dSquares-TRS-Levenberg_002dMarquardt.html

package info (click to toggle)
gsl-ref-html 2.3-1
  • links: PTS
  • area: non-free
  • in suites: bullseye, buster, sid
  • size: 6,876 kB
  • ctags: 4,574
  • sloc: makefile: 35
file content (114 lines) | stat: -rw-r--r-- 5,883 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
<!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: Nonlinear Least-Squares TRS Levenberg-Marquardt</title>

<meta name="description" content="GNU Scientific Library &ndash; Reference Manual: Nonlinear Least-Squares TRS Levenberg-Marquardt">
<meta name="keywords" content="GNU Scientific Library &ndash; Reference Manual: Nonlinear Least-Squares TRS Levenberg-Marquardt">
<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="Nonlinear-Least_002dSquares-TRS-Overview.html#Nonlinear-Least_002dSquares-TRS-Overview" rel="up" title="Nonlinear Least-Squares TRS Overview">
<link href="Nonlinear-Least_002dSquares-TRS-Levenberg_002dMarquardt-with-Geodesic-Acceleration.html#Nonlinear-Least_002dSquares-TRS-Levenberg_002dMarquardt-with-Geodesic-Acceleration" rel="next" title="Nonlinear Least-Squares TRS Levenberg-Marquardt with Geodesic Acceleration">
<link href="Nonlinear-Least_002dSquares-TRS-Overview.html#Nonlinear-Least_002dSquares-TRS-Overview" rel="previous" title="Nonlinear Least-Squares TRS Overview">
<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="Nonlinear-Least_002dSquares-TRS-Levenberg_002dMarquardt"></a>
<div class="header">
<p>
Next: <a href="Nonlinear-Least_002dSquares-TRS-Levenberg_002dMarquardt-with-Geodesic-Acceleration.html#Nonlinear-Least_002dSquares-TRS-Levenberg_002dMarquardt-with-Geodesic-Acceleration" accesskey="n" rel="next">Nonlinear Least-Squares TRS Levenberg-Marquardt with Geodesic Acceleration</a>, Up: <a href="Nonlinear-Least_002dSquares-TRS-Overview.html#Nonlinear-Least_002dSquares-TRS-Overview" accesskey="u" rel="up">Nonlinear Least-Squares TRS Overview</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Levenberg_002dMarquardt"></a>
<h4 class="subsection">39.2.1 Levenberg-Marquardt</h4>
<a name="index-Levenberg_002dMarquardt-algorithm"></a>
<a name="index-nonlinear-least-squares_002c-levenberg_002dmarquardt"></a>

<p>There is a theorem which states that if <em>\delta_k</em> is a solution
to the trust region subproblem given above, then there exists
<em>\mu_k \ge 0</em> such that
</p>
<div class="example">
<pre class="example">( B_k + \mu_k D_k^T D_k ) \delta_k = -g_k
</pre></div>

<p>with <em>\mu_k (\Delta_k - ||D_k \delta_k||) = 0</em>. This
forms the basis of the Levenberg-Marquardt algorithm, which controls
the trust region size by adjusting the parameter <em>\mu_k</em>
rather than the radius <em>\Delta_k</em> directly. For each radius
<em>\Delta_k</em>, there is a unique parameter <em>\mu_k</em> which
solves the TRS, and they have an inverse relationship, so that large values of
<em>\mu_k</em> correspond to smaller trust regions, while small
values of <em>\mu_k</em> correspond to larger trust regions.
</p>
<p>With the approximation <em>B_k \approx J_k^T J_k</em>, on each iteration,
in order to calculate the step <em>\delta_k</em>,
the following linear least squares problem is solved:
</p>
<div class="example">
<pre class="example">[J_k; sqrt(mu_k) D_k] \delta_k = - [f_k; 0]
</pre></div>

<p>If the step <em>\delta_k</em> is accepted, then
<em>\mu_k</em> is decreased on the next iteration in order
to take a larger step, otherwise it is increased to take
a smaller step. The Levenberg-Marquardt algorithm provides
an exact solution of the trust region subproblem, but
typically has a higher computational cost per iteration
than the approximate methods discussed below, since it
may need to solve the least squares system above several
times for different values of <em>\mu_k</em>.
</p>



</body>
</html>