|
6778
|
1 @c Copyright (C) 1996, 1997, 2007 John W. Eaton |
|
3294
|
2 @c This is part of the Octave manual. |
|
|
3 @c For copying conditions, see the file gpl.texi. |
|
|
4 |
|
4167
|
5 @node Optimization |
|
3294
|
6 @chapter Optimization |
|
|
7 |
|
6741
|
8 Octave comes with support for solving various kinds of optimization |
|
|
9 problems. Specifically Octave can solve problems in Linear Programming, |
|
|
10 Quadratic Programming, Nonlinear Programming, and Linear Least Squares |
|
|
11 Minimization. |
|
|
12 |
|
3294
|
13 @menu |
|
4246
|
14 * Linear Programming:: |
|
3294
|
15 * Quadratic Programming:: |
|
|
16 * Nonlinear Programming:: |
|
|
17 * Linear Least Squares:: |
|
|
18 @end menu |
|
|
19 |
|
|
20 @c @cindex linear programming |
|
|
21 @cindex quadratic programming |
|
|
22 @cindex nonlinear programming |
|
|
23 @cindex optimization |
|
|
24 @cindex LP |
|
|
25 @cindex QP |
|
|
26 @cindex NLP |
|
|
27 |
|
4246
|
28 @node Linear Programming |
|
|
29 @section Linear Programming |
|
|
30 |
|
6741
|
31 Octave can solve Linear Programming problems using the @code{glpk} |
|
|
32 function. That is, Octave can solve |
|
|
33 |
|
|
34 @iftex |
|
|
35 @tex |
|
|
36 $$ |
|
|
37 \min_x c^T x |
|
|
38 $$ |
|
|
39 @end tex |
|
|
40 @end iftex |
|
|
41 @ifnottex |
|
|
42 @example |
|
|
43 min C'*x |
|
|
44 @end example |
|
|
45 @end ifnottex |
|
|
46 subject to the linear constraints |
|
|
47 @iftex |
|
|
48 @tex |
|
|
49 $Ax = b$ where $x \geq 0$. |
|
|
50 @end tex |
|
|
51 @end iftex |
|
|
52 @ifnottex |
|
|
53 @math{A*x = b} where @math{x >= 0}. |
|
|
54 @end ifnottex |
|
|
55 |
|
|
56 @noindent |
|
|
57 The @code{glpk} function also supports variations of this problem. |
|
|
58 |
|
6502
|
59 @DOCSTRING(glpk) |
|
|
60 |
|
4167
|
61 @node Quadratic Programming |
|
3294
|
62 @section Quadratic Programming |
|
|
63 |
|
6741
|
64 Octave can also solve Quadratic Programming problems, this is |
|
|
65 @iftex |
|
|
66 @tex |
|
|
67 $$ |
|
|
68 \min_x {1 \over 2} x^T H x + x^T q |
|
|
69 $$ |
|
|
70 @end tex |
|
|
71 @end iftex |
|
|
72 @ifnottex |
|
|
73 @example |
|
|
74 min 0.5 x'*H*x + x'*q |
|
|
75 @end example |
|
|
76 @end ifnottex |
|
|
77 subject to |
|
|
78 @iftex |
|
|
79 @tex |
|
|
80 $$ |
|
|
81 Ax = b \qquad lb \leq x \leq ub \qquad A_{lb} \leq A_{in} \leq A_{ub} |
|
|
82 $$ |
|
|
83 @end tex |
|
|
84 @end iftex |
|
|
85 @ifnottex |
|
|
86 @example |
|
|
87 A*x = b |
|
|
88 lb <= x <= ub |
|
|
89 A_lb <= A_in*x <= A_ub |
|
|
90 @end example |
|
|
91 @end ifnottex |
|
|
92 |
|
6502
|
93 @DOCSTRING(qp) |
|
|
94 |
|
4167
|
95 @node Nonlinear Programming |
|
3294
|
96 @section Nonlinear Programming |
|
|
97 |
|
6741
|
98 Octave can also perform general nonlinear minimization using a |
|
|
99 successive quadratic programming solver. |
|
|
100 |
|
6502
|
101 @DOCSTRING(sqp) |
|
|
102 |
|
4167
|
103 @node Linear Least Squares |
|
3294
|
104 @section Linear Least Squares |
|
|
105 |
|
6741
|
106 Octave also supports linear least squares minimization. That is, |
|
|
107 Octave can find the parameter @math{b} such the the model |
|
|
108 @iftex |
|
|
109 @tex |
|
|
110 $y = xb$ |
|
|
111 @end tex |
|
|
112 @end iftex |
|
|
113 @ifnottex |
|
|
114 @math{y = x*b} |
|
|
115 @end ifnottex |
|
|
116 fits data @math{(x,y)} as good as possible, assuming zero-mean |
|
|
117 Gaussian noise. If the noise is assumed to be isotropic the problem |
|
|
118 can be solved using the @samp{\} or @samp{/} operators, or the @code{ols} |
|
|
119 function. In the general case where the noise is assumed to be anisotropic |
|
|
120 the @code{gls} is needed. |
|
|
121 |
|
|
122 @DOCSTRING(ols) |
|
|
123 |
|
3368
|
124 @DOCSTRING(gls) |
|
3294
|
125 |
