Mercurial > octave-nkf
annotate scripts/optimization/qp.m @ 13027:b9a89ca0fb75
prevent optimization functions from setting ans in workspace at startup
* fminbnd.m, fminunc.m, fsolve.m, fzero.m, lsqnonneg.m, pqpnonneg.m,
qp.m: Discard result from call to __all_opt__ in PKG_ADD command.
| author | John W. Eaton <jwe@octave.org> |
|---|---|
| date | Mon, 29 Aug 2011 13:07:22 -0400 |
| parents | b0084095098e |
| children | 72c96de7a403 |
| rev | line source |
|---|---|
| 11523 | 1 ## Copyright (C) 2000-2011 Gabriele Pannocchia. |
| 5289 | 2 ## |
| 3 ## This file is part of Octave. | |
| 4 ## | |
| 5 ## Octave is free software; you can redistribute it and/or modify it | |
| 6 ## under the terms of the GNU General Public License as published by | |
| 7016 | 7 ## the Free Software Foundation; either version 3 of the License, or (at |
| 8 ## your option) any later version. | |
| 5289 | 9 ## |
| 10 ## Octave is distributed in the hope that it will be useful, but | |
| 11 ## WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 12 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| 13 ## General Public License for more details. | |
| 14 ## | |
| 15 ## You should have received a copy of the GNU General Public License | |
| 7016 | 16 ## along with Octave; see the file COPYING. If not, see |
| 17 ## <http://www.gnu.org/licenses/>. | |
| 5289 | 18 |
| 19 ## -*- texinfo -*- | |
|
10793
be55736a0783
Grammarcheck the documentation from m-files.
Rik <octave@nomad.inbox5.com>
parents:
10549
diff
changeset
|
20 ## @deftypefn {Function File} {[@var{x}, @var{obj}, @var{info}, @var{lambda}] =} qp (@var{x0}, @var{H}) |
|
10059
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
21 ## @deftypefnx {Function File} {[@var{x}, @var{obj}, @var{info}, @var{lambda}] =} qp (@var{x0}, @var{H}, @var{q}) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
22 ## @deftypefnx {Function File} {[@var{x}, @var{obj}, @var{info}, @var{lambda}] =} qp (@var{x0}, @var{H}, @var{q}, @var{A}, @var{b}) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
23 ## @deftypefnx {Function File} {[@var{x}, @var{obj}, @var{info}, @var{lambda}] =} qp (@var{x0}, @var{H}, @var{q}, @var{A}, @var{b}, @var{lb}, @var{ub}) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
24 ## @deftypefnx {Function File} {[@var{x}, @var{obj}, @var{info}, @var{lambda}] =} qp (@var{x0}, @var{H}, @var{q}, @var{A}, @var{b}, @var{lb}, @var{ub}, @var{A_lb}, @var{A_in}, @var{A_ub}) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
25 ## @deftypefnx {Function File} {[@var{x}, @var{obj}, @var{info}, @var{lambda}] =} qp (@dots{}, @var{options}) |
| 5289 | 26 ## Solve the quadratic program |
| 6741 | 27 ## @tex |
| 28 ## $$ | |
| 29 ## \min_x {1 \over 2} x^T H x + x^T q | |
| 30 ## $$ | |
| 31 ## @end tex | |
| 32 ## @ifnottex | |
| 5289 | 33 ## |
| 34 ## @example | |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
35 ## @group |
| 5289 | 36 ## min 0.5 x'*H*x + x'*q |
| 37 ## x | |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
38 ## @end group |
| 5289 | 39 ## @end example |
| 40 ## | |
| 6741 | 41 ## @end ifnottex |
| 42 ## subject to | |
| 5289 | 43 ## @tex |
| 6741 | 44 ## $$ |
| 45 ## Ax = b \qquad lb \leq x \leq ub \qquad A_{lb} \leq A_{in} \leq A_{ub} | |
| 46 ## $$ | |
| 5289 | 47 ## @end tex |
| 6741 | 48 ## @ifnottex |
| 5289 | 49 ## |
| 50 ## @example | |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
51 ## @group |
| 5289 | 52 ## A*x = b |
| 53 ## lb <= x <= ub | |
| 6741 | 54 ## A_lb <= A_in*x <= A_ub |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
55 ## @end group |
| 5289 | 56 ## @end example |
|
10821
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
57 ## |
| 6741 | 58 ## @end ifnottex |
| 5289 | 59 ## @noindent |
| 60 ## using a null-space active-set method. | |
| 61 ## | |
| 62 ## Any bound (@var{A}, @var{b}, @var{lb}, @var{ub}, @var{A_lb}, | |
| 63 ## @var{A_ub}) may be set to the empty matrix (@code{[]}) if not | |
| 64 ## present. If the initial guess is feasible the algorithm is faster. | |
| 65 ## | |
|
10059
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
66 ## @table @var |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
67 ## @item options |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
68 ## An optional structure containing the following |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
69 ## parameter(s) used to define the behavior of the solver. Missing elements |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
70 ## in the structure take on default values, so you only need to set the |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
71 ## elements that you wish to change from the default. |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
72 ## |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
73 ## @table @code |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
74 ## @item MaxIter (default: 200) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
75 ## Maximum number of iterations. |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
76 ## @end table |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
77 ## @end table |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
78 ## |
|
10821
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
79 ## @table @var |
|
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
80 ## @item info |
|
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
81 ## Structure containing run-time information about the algorithm. The |
|
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
82 ## following fields are defined: |
|
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
83 ## |
| 5289 | 84 ## @table @code |
| 85 ## @item solveiter | |
| 86 ## The number of iterations required to find the solution. | |
|
10821
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
87 ## |
| 5289 | 88 ## @item info |
|
10821
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
89 ## An integer indicating the status of the solution. |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
90 ## |
| 5289 | 91 ## @table @asis |
| 92 ## @item 0 | |
| 93 ## The problem is feasible and convex. Global solution found. | |
|
10821
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
94 ## |
| 5289 | 95 ## @item 1 |
| 96 ## The problem is not convex. Local solution found. | |
|
10821
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
97 ## |
| 5289 | 98 ## @item 2 |
| 99 ## The problem is not convex and unbounded. | |
|
10821
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
100 ## |
| 5289 | 101 ## @item 3 |
| 102 ## Maximum number of iterations reached. | |
|
10821
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
103 ## |
| 5289 | 104 ## @item 6 |
| 105 ## The problem is infeasible. | |
| 106 ## @end table | |
| 107 ## @end table | |
|
10821
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
108 ## @end table |
| 5289 | 109 ## @end deftypefn |
| 110 | |
|
13027
b9a89ca0fb75
prevent optimization functions from setting ans in workspace at startup
John W. Eaton <jwe@octave.org>
parents:
11589
diff
changeset
|
111 ## PKG_ADD: ## Discard result to avoid polluting workspace with ans at startup. |
|
b9a89ca0fb75
prevent optimization functions from setting ans in workspace at startup
John W. Eaton <jwe@octave.org>
parents:
11589
diff
changeset
|
112 ## PKG_ADD: [~] = __all_opts__ ("qp"); |
|
10060
8f51a90eb8d1
implement default opts query and register opts for qp
Jaroslav Hajek <highegg@gmail.com>
parents:
10059
diff
changeset
|
113 |
|
10059
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
114 function [x, obj, INFO, lambda] = qp (x0, H, varargin) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
115 |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
116 nargs = nargin; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
117 |
|
10060
8f51a90eb8d1
implement default opts query and register opts for qp
Jaroslav Hajek <highegg@gmail.com>
parents:
10059
diff
changeset
|
118 if (nargin == 1 && ischar (x0) && strcmp (x0, 'defaults')) |
|
8f51a90eb8d1
implement default opts query and register opts for qp
Jaroslav Hajek <highegg@gmail.com>
parents:
10059
diff
changeset
|
119 x = optimset ("MaxIter", 200); |
|
8f51a90eb8d1
implement default opts query and register opts for qp
Jaroslav Hajek <highegg@gmail.com>
parents:
10059
diff
changeset
|
120 return; |
|
8f51a90eb8d1
implement default opts query and register opts for qp
Jaroslav Hajek <highegg@gmail.com>
parents:
10059
diff
changeset
|
121 endif |
|
8f51a90eb8d1
implement default opts query and register opts for qp
Jaroslav Hajek <highegg@gmail.com>
parents:
10059
diff
changeset
|
122 |
|
10059
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
123 if (nargs > 2 && isstruct (varargin{end})) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
124 options = varargin{end}; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
125 nargs--; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
126 else |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
127 options = struct (); |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
128 endif |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
129 |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
130 if (nargs >= 3) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
131 q = varargin{1}; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
132 else |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
133 q = []; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
134 endif |
| 5289 | 135 |
|
10059
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
136 if (nargs >= 5) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
137 A = varargin{2}; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
138 b = varargin{3}; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
139 else |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
140 A = []; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
141 b = []; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
142 endif |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
143 |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
144 if (nargs >= 7) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
145 lb = varargin{4}; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
146 ub = varargin{5}; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
147 else |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
148 lb = []; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
149 ub = []; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
150 endif |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
151 |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
152 if (nargs == 10) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
153 A_lb = varargin{6}; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
154 A_in = varargin{7}; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
155 A_ub = varargin{8}; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
156 else |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
157 A_lb = []; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
158 A_in = []; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
159 A_ub = []; |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
160 endif |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
161 |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
162 if (nargs == 2 || nargs == 3 || nargs == 5 || nargs == 7 || nargs == 10) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
163 |
|
10064
17ce2a700a97
qp.m: Add missing semicolon.
Ben Abbott <bpabbott@mac.com>
parents:
10060
diff
changeset
|
164 maxit = optimget (options, "MaxIter", 200); |
| 5289 | 165 |
| 166 ## Checking the quadratic penalty | |
|
9872
72d6e0de76c7
fix qp, condest and krylov
Jaroslav Hajek <highegg@gmail.com>
parents:
9211
diff
changeset
|
167 if (! issquare (H)) |
| 5289 | 168 error ("qp: quadratic penalty matrix not square"); |
|
9872
72d6e0de76c7
fix qp, condest and krylov
Jaroslav Hajek <highegg@gmail.com>
parents:
9211
diff
changeset
|
169 elseif (! ishermitian (H)) |
|
72d6e0de76c7
fix qp, condest and krylov
Jaroslav Hajek <highegg@gmail.com>
parents:
9211
diff
changeset
|
170 ## warning ("qp: quadratic penalty matrix not hermitian"); |
| 5289 | 171 H = (H + H')/2; |
| 172 endif | |
|
9872
72d6e0de76c7
fix qp, condest and krylov
Jaroslav Hajek <highegg@gmail.com>
parents:
9211
diff
changeset
|
173 n = rows (H); |
| 5289 | 174 |
| 175 ## Checking the initial guess (if empty it is resized to the | |
| 176 ## right dimension and filled with 0) | |
| 177 if (isempty (x0)) | |
| 178 x0 = zeros (n, 1); | |
|
10059
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
179 elseif (numel (x0) != n) |
| 5289 | 180 error ("qp: the initial guess has incorrect length"); |
| 181 endif | |
| 182 | |
| 183 ## Linear penalty. | |
|
10059
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
184 if (isempty (q)) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
185 q = zeros (n, 1); |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
186 elseif (numel (q) != n) |
| 5289 | 187 error ("qp: the linear term has incorrect length"); |
| 188 endif | |
| 189 | |
| 190 ## Equality constraint matrices | |
|
10059
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
191 if (isempty (A) || isempty (b)) |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
192 A = zeros (0, n); |
|
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
193 b = zeros (0, 1); |
| 5289 | 194 n_eq = 0; |
| 195 else | |
| 196 [n_eq, n1] = size (A); | |
| 197 if (n1 != n) | |
| 10549 | 198 error ("qp: equality constraint matrix has incorrect column dimension"); |
| 5289 | 199 endif |
|
10059
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
200 if (numel (b) != n_eq) |
| 10549 | 201 error ("qp: equality constraint matrix and vector have inconsistent dimension"); |
| 5289 | 202 endif |
| 203 endif | |
| 204 | |
| 205 ## Bound constraints | |
| 206 Ain = zeros (0, n); | |
| 207 bin = zeros (0, 1); | |
| 208 n_in = 0; | |
|
10059
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
209 if (nargs > 5) |
| 5289 | 210 if (! isempty (lb)) |
| 10549 | 211 if (numel (lb) != n) |
| 212 error ("qp: lower bound has incorrect length"); | |
| 213 elseif (isempty (ub)) | |
| 214 Ain = [Ain; eye(n)]; | |
| 215 bin = [bin; lb]; | |
| 216 endif | |
| 5289 | 217 endif |
| 218 | |
| 219 if (! isempty (ub)) | |
| 10549 | 220 if (numel (ub) != n) |
| 221 error ("qp: upper bound has incorrect length"); | |
| 222 elseif (isempty (lb)) | |
| 223 Ain = [Ain; -eye(n)]; | |
| 224 bin = [bin; -ub]; | |
| 225 endif | |
| 5289 | 226 endif |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
227 |
|
8280
5ee11a81688e
qp.m: convert b <= x <= b and b <= A*x <= b to equality constraints
Gabriele Pannocchia <g.pannocchia@ing.unipi.it>
parents:
7795
diff
changeset
|
228 if (! isempty (lb) && ! isempty (ub)) |
| 10549 | 229 rtol = sqrt (eps); |
| 230 for i = 1:n | |
| 231 if (abs(lb (i) - ub(i)) < rtol*(1 + max (abs (lb(i) + ub(i))))) | |
|
8280
5ee11a81688e
qp.m: convert b <= x <= b and b <= A*x <= b to equality constraints
Gabriele Pannocchia <g.pannocchia@ing.unipi.it>
parents:
7795
diff
changeset
|
232 ## These are actually an equality constraint |
| 10549 | 233 tmprow = zeros(1,n); |
| 234 tmprow(i) = 1; | |
|
8280
5ee11a81688e
qp.m: convert b <= x <= b and b <= A*x <= b to equality constraints
Gabriele Pannocchia <g.pannocchia@ing.unipi.it>
parents:
7795
diff
changeset
|
235 A = [A;tmprow]; |
|
5ee11a81688e
qp.m: convert b <= x <= b and b <= A*x <= b to equality constraints
Gabriele Pannocchia <g.pannocchia@ing.unipi.it>
parents:
7795
diff
changeset
|
236 b = [b; 0.5*(lb(i) + ub(i))]; |
| 10549 | 237 n_eq = n_eq + 1; |
| 238 else | |
| 239 tmprow = zeros(1,n); | |
| 240 tmprow(i) = 1; | |
| 241 Ain = [Ain; tmprow; -tmprow]; | |
| 242 bin = [bin; lb(i); -ub(i)]; | |
| 243 n_in = n_in + 2; | |
| 244 endif | |
| 245 endfor | |
|
8280
5ee11a81688e
qp.m: convert b <= x <= b and b <= A*x <= b to equality constraints
Gabriele Pannocchia <g.pannocchia@ing.unipi.it>
parents:
7795
diff
changeset
|
246 endif |
| 5289 | 247 endif |
| 248 | |
| 249 ## Inequality constraints | |
|
10059
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
250 if (nargs > 7) |
| 5289 | 251 [dimA_in, n1] = size (A_in); |
| 252 if (n1 != n) | |
| 10549 | 253 error ("qp: inequality constraint matrix has incorrect column dimension"); |
| 5289 | 254 else |
| 10549 | 255 if (! isempty (A_lb)) |
| 256 if (numel (A_lb) != dimA_in) | |
| 257 error ("qp: inequality constraint matrix and lower bound vector inconsistent"); | |
| 258 elseif (isempty (A_ub)) | |
| 259 Ain = [Ain; A_in]; | |
| 260 bin = [bin; A_lb]; | |
| 261 endif | |
| 262 endif | |
| 263 if (! isempty (A_ub)) | |
| 264 if (numel (A_ub) != dimA_in) | |
| 265 error ("qp: inequality constraint matrix and upper bound vector inconsistent"); | |
| 266 elseif (isempty (A_lb)) | |
| 267 Ain = [Ain; -A_in]; | |
| 268 bin = [bin; -A_ub]; | |
| 269 endif | |
| 270 endif | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
271 |
| 10549 | 272 if (! isempty (A_lb) && ! isempty (A_ub)) |
| 273 rtol = sqrt (eps); | |
| 274 for i = 1:dimA_in | |
| 275 if (abs (A_lb(i) - A_ub(i)) < rtol*(1 + max (abs (A_lb(i) + A_ub(i))))) | |
|
8280
5ee11a81688e
qp.m: convert b <= x <= b and b <= A*x <= b to equality constraints
Gabriele Pannocchia <g.pannocchia@ing.unipi.it>
parents:
7795
diff
changeset
|
276 ## These are actually an equality constraint |
| 10549 | 277 tmprow = A_in(i,:); |
|
8280
5ee11a81688e
qp.m: convert b <= x <= b and b <= A*x <= b to equality constraints
Gabriele Pannocchia <g.pannocchia@ing.unipi.it>
parents:
7795
diff
changeset
|
278 A = [A;tmprow]; |
|
5ee11a81688e
qp.m: convert b <= x <= b and b <= A*x <= b to equality constraints
Gabriele Pannocchia <g.pannocchia@ing.unipi.it>
parents:
7795
diff
changeset
|
279 b = [b; 0.5*(A_lb(i) + A_ub(i))]; |
| 10549 | 280 n_eq = n_eq + 1; |
| 281 else | |
| 282 tmprow = A_in(i,:); | |
| 283 Ain = [Ain; tmprow; -tmprow]; | |
| 284 bin = [bin; A_lb(i); -A_ub(i)]; | |
| 285 n_in = n_in + 2; | |
| 286 endif | |
| 287 endfor | |
| 288 endif | |
| 5289 | 289 endif |
| 290 endif | |
| 291 | |
| 292 ## Now we should have the following QP: | |
| 293 ## | |
| 294 ## min_x 0.5*x'*H*x + x'*q | |
| 295 ## s.t. A*x = b | |
| 296 ## Ain*x >= bin | |
| 297 | |
| 298 ## Discard inequality constraints that have -Inf bounds since those | |
| 299 ## will never be active. | |
| 300 idx = isinf (bin) & bin < 0; | |
| 6523 | 301 |
| 6526 | 302 bin(idx) = []; |
| 303 Ain(idx,:) = []; | |
| 5289 | 304 |
|
10059
665ad34efeed
qp.m: handle optimset options
Joshua Redstone <redstone@gmail.com>, John W. Eaton <jwe@octave.org>
parents:
9872
diff
changeset
|
305 n_in = numel (bin); |
| 5310 | 306 |
| 5289 | 307 ## Check if the initial guess is feasible. |
|
7795
df9519e9990c
Handle single precision eps values
David Bateman <dbateman@free.fr>
parents:
7017
diff
changeset
|
308 if (isa (x0, "single") || isa (H, "single") || isa (q, "single") || isa (A, "single") |
| 10549 | 309 || isa (b, "single")) |
|
7795
df9519e9990c
Handle single precision eps values
David Bateman <dbateman@free.fr>
parents:
7017
diff
changeset
|
310 rtol = sqrt (eps ("single")); |
|
df9519e9990c
Handle single precision eps values
David Bateman <dbateman@free.fr>
parents:
7017
diff
changeset
|
311 else |
|
df9519e9990c
Handle single precision eps values
David Bateman <dbateman@free.fr>
parents:
7017
diff
changeset
|
312 rtol = sqrt (eps); |
|
df9519e9990c
Handle single precision eps values
David Bateman <dbateman@free.fr>
parents:
7017
diff
changeset
|
313 endif |
| 5289 | 314 |
|
8280
5ee11a81688e
qp.m: convert b <= x <= b and b <= A*x <= b to equality constraints
Gabriele Pannocchia <g.pannocchia@ing.unipi.it>
parents:
7795
diff
changeset
|
315 eq_infeasible = (n_eq > 0 && norm (A*x0-b) > rtol*(1+abs (b))); |
|
5ee11a81688e
qp.m: convert b <= x <= b and b <= A*x <= b to equality constraints
Gabriele Pannocchia <g.pannocchia@ing.unipi.it>
parents:
7795
diff
changeset
|
316 in_infeasible = (n_in > 0 && any (Ain*x0-bin < -rtol*(1+abs (bin)))); |
| 5289 | 317 |
| 318 info = 0; | |
| 319 if (eq_infeasible || in_infeasible) | |
| 320 ## The initial guess is not feasible. | |
| 321 ## First define xbar that is feasible with respect to the equality | |
| 322 ## constraints. | |
| 323 if (eq_infeasible) | |
| 10549 | 324 if (rank (A) < n_eq) |
|
11589
b0084095098e
missing semicolons in script files
John W. Eaton <jwe@octave.org>
parents:
11587
diff
changeset
|
325 error ("qp: equality constraint matrix must be full row rank"); |
| 10549 | 326 endif |
| 327 xbar = pinv (A) * b; | |
| 5289 | 328 else |
| 10549 | 329 xbar = x0; |
| 5289 | 330 endif |
| 331 | |
| 332 ## Check if xbar is feasible with respect to the inequality | |
| 333 ## constraints also. | |
| 334 if (n_in > 0) | |
| 10549 | 335 res = Ain * xbar - bin; |
| 336 if (any (res < -rtol * (1 + abs (bin)))) | |
| 337 ## xbar is not feasible with respect to the inequality | |
| 338 ## constraints. Compute a step in the null space of the | |
| 339 ## equality constraints, by solving a QP. If the slack is | |
| 340 ## small, we have a feasible initial guess. Otherwise, the | |
| 341 ## problem is infeasible. | |
| 342 if (n_eq > 0) | |
| 343 Z = null (A); | |
| 344 if (isempty (Z)) | |
| 345 ## The problem is infeasible because A is square and full | |
| 346 ## rank, but xbar is not feasible. | |
| 347 info = 6; | |
| 348 endif | |
| 349 endif | |
| 5289 | 350 |
| 10549 | 351 if (info != 6) |
| 5289 | 352 ## Solve an LP with additional slack variables to find |
| 10549 | 353 ## a feasible starting point. |
| 354 gamma = eye (n_in); | |
| 355 if (n_eq > 0) | |
| 356 Atmp = [Ain*Z, gamma]; | |
| 357 btmp = -res; | |
| 358 else | |
| 359 Atmp = [Ain, gamma]; | |
| 360 btmp = bin; | |
| 361 endif | |
| 362 ctmp = [zeros(n-n_eq, 1); ones(n_in, 1)]; | |
| 363 lb = [-Inf(n-n_eq,1); zeros(n_in,1)]; | |
| 364 ub = []; | |
| 365 ctype = repmat ("L", n_in, 1); | |
| 366 [P, dummy, status] = glpk (ctmp, Atmp, btmp, lb, ub, ctype); | |
| 367 if ((status == 180 || status == 181 || status == 151) | |
| 368 && all (abs (P(n-n_eq+1:end)) < rtol * (1 + norm (btmp)))) | |
| 369 ## We found a feasible starting point | |
| 370 if (n_eq > 0) | |
| 371 x0 = xbar + Z*P(1:n-n_eq); | |
| 372 else | |
| 373 x0 = P(1:n); | |
| 5289 | 374 endif |
| 10549 | 375 else |
| 376 ## The problem is infeasible | |
| 377 info = 6; | |
| 378 endif | |
| 379 endif | |
| 380 else | |
| 381 ## xbar is feasible. We use it a starting point. | |
| 382 x0 = xbar; | |
| 383 endif | |
| 5289 | 384 else |
| 10549 | 385 ## xbar is feasible. We use it a starting point. |
| 386 x0 = xbar; | |
| 5289 | 387 endif |
| 388 endif | |
| 389 | |
| 390 if (info == 0) | |
| 391 ## The initial (or computed) guess is feasible. | |
| 392 ## We call the solver. | |
| 393 [x, lambda, info, iter] = __qp__ (x0, H, q, A, b, Ain, bin, maxit); | |
| 394 else | |
| 395 iter = 0; | |
| 396 x = x0; | |
| 397 lambda = []; | |
| 398 endif | |
| 399 obj = 0.5 * x' * H * x + q' * x; | |
| 400 INFO.solveiter = iter; | |
| 401 INFO.info = info; | |
| 402 | |
| 403 else | |
| 6046 | 404 print_usage (); |
| 5289 | 405 endif |
| 406 | |
| 407 endfunction |