Mercurial > hg > de.mpg.mpiwg.itgroup.digilib.core

comparison libs/commons-math-2.1/docs/userguide/optimization.html @ 10:5f2c5fb36e93

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commons-math-2.1 added
author dwinter
date Tue, 04 Jan 2011 10:00:53 +0100
parents
children
comparison
equal deleted inserted replaced
9:e63a64652f4d 10:5f2c5fb36e93
1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
2
3
4
5
6
7
8
9
10
11
12
13 <html xmlns="http://www.w3.org/1999/xhtml">
14 <head>
15 <title>Math - The Commons Math User Guide - Optimization</title>
16 <style type="text/css" media="all">
17 @import url("../css/maven-base.css");
18 @import url("../css/maven-theme.css");
19 @import url("../css/site.css");
20 </style>
21 <link rel="stylesheet" href="../css/print.css" type="text/css" media="print" />
22 <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />
23 </head>
24 <body class="composite">
25 <div id="banner">
26 <span id="bannerLeft">
27
28 Commons Math User Guide
29
30 </span>
31 <div class="clear">
32 <hr/>
33 </div>
34 </div>
35 <div id="breadcrumbs">
36
37
38
39
40
41
42
43
44 <div class="xright">
45
46
47
48
49
50
51
52 </div>
53 <div class="clear">
54 <hr/>
55 </div>
56 </div>
57 <div id="leftColumn">
58 <div id="navcolumn">
59
60
61
62
63
64
65
66
67 <h5>User Guide</h5>
68 <ul>
69
70 <li class="none">
71 <a href="../userguide/index.html">Contents</a>
72 </li>
73
74 <li class="none">
75 <a href="../userguide/overview.html">Overview</a>
76 </li>
77
78 <li class="none">
79 <a href="../userguide/stat.html">Statistics</a>
80 </li>
81
82 <li class="none">
83 <a href="../userguide/random.html">Data Generation</a>
84 </li>
85
86 <li class="none">
87 <a href="../userguide/linear.html">Linear Algebra</a>
88 </li>
89
90 <li class="none">
91 <a href="../userguide/analysis.html">Numerical Analysis</a>
92 </li>
93
94 <li class="none">
95 <a href="../userguide/special.html">Special Functions</a>
96 </li>
97
98 <li class="none">
99 <a href="../userguide/utilities.html">Utilities</a>
100 </li>
101
102 <li class="none">
103 <a href="../userguide/complex.html">Complex Numbers</a>
104 </li>
105
106 <li class="none">
107 <a href="../userguide/distribution.html">Distributions</a>
108 </li>
109
110 <li class="none">
111 <a href="../userguide/fraction.html">Fractions</a>
112 </li>
113
114 <li class="none">
115 <a href="../userguide/transform.html">Transform Methods</a>
116 </li>
117
118 <li class="none">
119 <a href="../userguide/geometry.html">3D Geometry</a>
120 </li>
121
122 <li class="none">
123 <strong>Optimization</strong>
124 </li>
125
126 <li class="none">
127 <a href="../userguide/ode.html">Ordinary Differential Equations</a>
128 </li>
129
130 <li class="none">
131 <a href="../userguide/genetics.html">Genetic Algorithms</a>
132 </li>
133 </ul>
134 <a href="http://maven.apache.org/" title="Built by Maven" class="poweredBy">
135 <img alt="Built by Maven" src="../images/logos/maven-feather.png"></img>
136 </a>
137
138
139
140
141
142
143
144
145 </div>
146 </div>
147 <div id="bodyColumn">
148 <div id="contentBox">
149 <div class="section"><h2><a name="a12_Optimization"></a>12 Optimization</h2>
150 <div class="section"><h3><a name="a12.1_Overview"></a>12.1 Overview</h3>
151 <p>
152 The optimization package provides algorithms to optimize (i.e. either minimize
153 or maximize) some objective or cost function. The package is split in several
154 sub-packages dedicated to different kind of functions or algorithms.
155 <ul><li>the univariate package handles univariate scalar functions,</li>
156 <li>the linear package handles multivariate vector linear functions
157 with linear constraints,</li>
158 <li>the direct package handles multivariate scalar functions
159 using direct search methods (i.e. not using derivatives),</li>
160 <li>the general package handles multivariate scalar or vector functions
161 using derivatives.</li>
162 <li>the fitting package handles curve fitting by univariate real functions</li>
163 </ul>
164 </p>
165 <p>
166 The top level optimization package provides common interfaces for the optimization
167 algorithms provided in sub-packages. The main interfaces defines defines optimizers
168 and convergence checkers. The functions that are optimized by the algorithms provided
169 by this package and its sub-packages are a subset of the one defined in the
170 <code>analysis</code> package, namely the real and vector valued functions. These
171 functions are called objective function here. When the goal is to minimize, the
172 functions are often called cost function, this name is not used in this package.
173 </p>
174 <p>
175 The type of goal, i.e. minimization or maximization, is defined by the enumerated
176 <a href="../apidocs/org/apache/commons/math/optimization/GoalType.html">
177 GoalType</a> which has only two values: <code>MAXIMIZE</code> and <code>MINIMIZE</code>.
178 </p>
179 <p>
180 Optimizers are the algorithms that will either minimize or maximize, the objective
181 function by changing its input variables set until an optimal set is found. There
182 are only four interfaces defining the common behavior of optimizers, one for each
183 supported type of objective function:
184 <ul><li><a href="../apidocs/org/apache/commons/math/optimization/UnivariateRealOptimizer.html">
185 UnivariateRealOptimizer</a> for <a href="../apidocs/org/apache/commons/math/analysis/UnivariateRealFunction.html">
186 univariate real functions</a></li>
187 <li><a href="../apidocs/org/apache/commons/math/optimization/MultivariateRealOptimizer.html">
188 MultivariateRealOptimizer</a> for <a href="../apidocs/org/apache/commons/math/analysis/MultivariateRealFunction.html">
189 multivariate real functions</a></li>
190 <li><a href="../apidocs/org/apache/commons/math/optimization/DifferentiableMultivariateRealOptimizer.html">
191 DifferentiableMultivariateRealOptimizer</a> for <a href="../apidocs/org/apache/commons/math/analysis/DifferentiableMultivariateRealFunction.html">
192 differentiable multivariate real functions</a></li>
193 <li><a href="../apidocs/org/apache/commons/math/optimization/DifferentiableMultivariateVectorialOptimizer.html">
194 DifferentiableMultivariateVectorialOptimizer</a> for <a href="../apidocs/org/apache/commons/math/analysis/DifferentiableMultivariateVectorialFunction.html">
195 differentiable multivariate vectorial functions</a></li>
196 </ul>
197 </p>
198 <p>
199 Despite there are only four types of supported optimizers, it is possible to optimize
200 a transform a <a href="../apidocs/org/apache/commons/math/analysis/MultivariateVectorialFunction.html">
201 non-differentiable multivariate vectorial function</a> by converting it to a <a href="../apidocs/org/apache/commons/math/analysis/MultivariateRealFunction.html">
202 non-differentiable multivariate real function</a> thanks to the <a href="../apidocs/org/apache/commons/math/optimization/LeastSquaresConverter.html">
203 LeastSquaresConverter</a> helper class. The transformed function can be optimized using
204 any implementation of the <a href="../apidocs/org/apache/commons/math/optimization/MultivariateRealOptimizer.html">
205 MultivariateRealOptimizer</a> interface.
206 </p>
207 <p>
208 For each of the four types of supported optimizers, there is a special implementation
209 which wraps a classical optimizer in order to add it a multi-start feature. This feature
210 call the underlying optimizer several times in sequence with different starting points
211 and returns the best optimum found or all optima if desired. This is a classical way to
212 prevent being trapped into a local extremum when looking for a global one.
213 </p>
214 </div>
215 <div class="section"><h3><a name="a12.2_Univariate_Functions"></a>12.2 Univariate Functions</h3>
216 <p>
217 A <a href="../apidocs/org/apache/commons/math/optimization/UnivariateRealOptimizer.html">
218 UnivariateRealOptimizer</a> is used to find the minimal values of a univariate real-valued
219 function <code>f</code>.
220 </p>
221 <p>
222 These algorithms usage is very similar to root-finding algorithms usage explained
223 in the analysis package. The main difference is that the <code>solve</code> methods in root
224 finding algorithms is replaced by <code>optimize</code> methods.
225 </p>
226 </div>
227 <div class="section"><h3><a name="a12.3_Linear_Programming"></a>12.3 Linear Programming</h3>
228 <p>
229 This package provides an implementation of George Dantzig's simplex algorithm
230 for solving linear optimization problems with linear equality and inequality
231 constraints.
232 </p>
233 </div>
234 <div class="section"><h3><a name="a12.4_Direct_Methods"></a>12.4 Direct Methods</h3>
235 <p>
236 Direct search methods only use cost function values, they don't
237 need derivatives and don't either try to compute approximation of
238 the derivatives. According to a 1996 paper by Margaret H. Wright
239 (<a href="http://cm.bell-labs.com/cm/cs/doc/96/4-02.ps.gz" class="externalLink">Direct
240 Search Methods: Once Scorned, Now Respectable</a>), they are used
241 when either the computation of the derivative is impossible (noisy
242 functions, unpredictable discontinuities) or difficult (complexity,
243 computation cost). In the first cases, rather than an optimum, a
244 <em>not too bad</em> point is desired. In the latter cases, an
245 optimum is desired but cannot be reasonably found. In all cases
246 direct search methods can be useful.
247 </p>
248 <p>
249 Simplex-based direct search methods are based on comparison of
250 the cost function values at the vertices of a simplex (which is a
251 set of n+1 points in dimension n) that is updated by the algorithms
252 steps.
253 </p>
254 <p>
255 The instances can be built either in single-start or in
256 multi-start mode. Multi-start is a traditional way to try to avoid
257 being trapped in a local minimum and miss the global minimum of a
258 function. It can also be used to verify the convergence of an
259 algorithm. In multi-start mode, the <code>minimizes</code>method
260 returns the best minimum found after all starts, and the <code>etMinima</code>
261 method can be used to retrieve all minima from all starts (including the one
262 already provided by the <code>minimizes</code> method).
263 </p>
264 <p>
265 The <code>direct</code> package provides two solvers. The first one is the classical
266 <a href="../apidocs/org/apache/commons/math/optimization/direct/NelderMead.html">
267 Nelder-Mead</a> method. The second one is Virginia Torczon's
268 <a href="../apidocs/org/apache/commons/math/optimization/direct/MultiDirectional.html">
269 multi-directional</a> method.
270 </p>
271 </div>
272 <div class="section"><h3><a name="a12.5_General_Case"></a>12.5 General Case</h3>
273 <p>
274 The general package deals with non-linear vectorial optimization problems when
275 the partial derivatives of the objective function are available.
276 </p>
277 <p>
278 One important class of estimation problems is weighted least
279 squares problems. They basically consist in finding the values
280 for some parameters p<sub>k</sub> such that a cost function
281 J = sum(w<sub>i</sub>(mes<sub>i</sub> - mod<sub>i</sub>)<sup>2</sup>) is
282 minimized. The various (target<sub>i</sub> - model<sub>i</sub>(p<sub>k</sub>))
283 terms are called residuals. They represent the deviation between a set of
284 target values target<sub>i</sub> and theoretical values computed from
285 models model<sub>i</sub> depending on free parameters p<sub>k</sub>.
286 The w<sub>i</sub> factors are weights. One classical use case is when the
287 target values are experimental observations or measurements.
288 </p>
289 <p>
290 Solving a least-squares problem is finding the free parameters p<sub>k</sub>
291 of the theoretical models such that they are close to the target values, i.e.
292 when the residual are small.
293 </p>
294 <p>
295 Two optimizers are available in the general package, both devoted to least-squares
296 problems. The first one is based on the <a href="../apidocs/org/apache/commons/math/optimization/general/GaussNewtonOptimizer.html">
297 Gauss-Newton</a> method. The second one is the <a href="../apidocs/org/apache/commons/math/optimization/general/LevenbergMarquardtOptimizer.html">
298 Levenberg-Marquardt</a> method.
299 </p>
300 <p>
301 In order to solve a vectorial optimization problem, the user must provide it as
302 an object implementing the <a href="../apidocs/org/apache/commons/math/analysis/DifferentiableMultivariateVectorialFunction.html">
303 DifferentiableMultivariateVectorialFunction</a> interface. The object will be provided to
304 the <code>estimate</code> method of the optimizer, along with the target and weight arrays,
305 thus allowing the optimizer to compute the residuals at will. The last parameter to the
306 <code>estimate</code> method is the point from which the optimizer will start its
307 search for the optimal point.
308 </p>
309 <p>
310 In addition to least squares solving, the <a href="../apidocs/org/apache/commons/math/optimization/general/NonLinearConjugateGradientOptimizer.html">
311 NonLinearConjugateGradientOptimizer</a> class provides a non-linear conjugate gradient algorithm
312 to optimize <a href="../apidocs/org/apache/commons/math/optimization/DifferentiableMultivariateRealFunction.html">
313 DifferentiableMultivariateRealFunction</a>. Both the Fletcher-Reeves and the Polak-Ribière
314 search direction update methods are supported. It is also possible to set up a preconditioner
315 or to change the line-search algorithm of the inner loop if desired (the default one is a Brent
316 solver).
317 </p>
318 </div>
319 <div class="section"><h3><a name="a12.6_Curve_Fitting"></a>12.6 Curve Fitting</h3>
320 <p>
321 The fitting package deals with curve fitting for univariate real functions.
322 When a univariate real function y = f(x) does depend on some unknown parameters
323 p<sub>0</sub>, p<sub>1</sub> ... p<sub>n-1</sub>, curve fitting can be used to
324 find these parameters. It does this by <em>fitting</em> the curve so it remains
325 very close to a set of observed points (x<sub>0</sub>, y<sub>0</sub>),
326 (x<sub>1</sub>, y<sub>1</sub>) ... (x<sub>k-1</sub>, y<sub>k-1</sub>). This
327 fitting is done by finding the parameters values that minimizes the objective
328 function sum(y<sub>i</sub>-f(x<sub>i</sub>))<sup>2</sup>. This is really a least
329 squares problem.
330 </p>
331 <p>
332 For all provided curve fitters, the operating principle is the same. Users must first
333 create an instance of the fitter, then add the observed points and once the complete
334 sample of observed points has been added they must call the <code>fit</code> method
335 which will compute the parameters that best fit the sample. A weight is associated
336 with each observed point, this allows to take into account uncertainty on some points
337 when they come from loosy measurements for example. If no such information exist and
338 all points should be treated the same, it is safe to put 1.0 as the weight for all points.
339 </p>
340 <p>
341 The <a href="../apidocs/org/apache/commons/math/optimization/fitting/CurveFitter.html">
342 CurveFitter</a> class provides curve fitting for general curves. Users must
343 provide their own implementation of the curve template as a class implementing
344 the <a href="../apidocs/org/apache/commons/math/optimization/fitting/ParametricRealFunction.html">
345 ParametricRealFunction</a> interface and they must provide the initial guess of the
346 parameters. The more specialized <a href="../apidocs/org/apache/commons/math/optimization/fitting/PolynomialFitter.html">
347 PolynomialFitter</a> and <a href="../apidocs/org/apache/commons/math/optimization/fitting/HarmonicFitter.html">
348 HarmonicFitter</a> classes require neither an implementation of the parametric real function
349 not an initial guess as they are able to compute them by themselves.
350 </p>
351 <p>
352 An example of fitting a polynomial is given here:
353 </p>
354 <div class="source"><pre>PolynomialFitter fitter = new PolynomialFitter(degree, new LevenbergMarquardtOptimizer());
355 fitter.addObservedPoint(-1.00, 2.021170021833143);
356 fitter.addObservedPoint(-0.99 2.221135431136975);
357 fitter.addObservedPoint(-0.98 2.09985277659314);
358 fitter.addObservedPoint(-0.97 2.0211192647627025);
359 // lots of lines ommitted
360 fitter.addObservedPoint( 0.99, -2.4345814727089854);
361 PolynomialFunction fitted = fitter.fit();
362 </pre>
363 </div>
364 </div>
365 </div>
366
367 </div>
368 </div>
369 <div class="clear">
370 <hr/>
371 </div>
372 <div id="footer">
373 <div class="xright">&#169;
374 2003-2010
375
376
377
378
379
380
381
382
383
384 </div>
385 <div class="clear">
386 <hr/>
387 </div>
388 </div>
389 </body>
390 </html>