|
10
|
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">©
|
|
|
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>
|
