Deleted vectorized computation feature. Deleted neldermead_contour. Fixed the demos.
[scilab.git] / scilab / modules / optimization / help / en_US / qpsolve.xml
1 <?xml version="1.0" encoding="UTF-8"?>
2 <refentry version="5.0-subset Scilab" xml:id="qpsolve" xml:lang="en"
3           xmlns="http://docbook.org/ns/docbook"
4           xmlns:xlink="http://www.w3.org/1999/xlink"
5           xmlns:svg="http://www.w3.org/2000/svg"
6           xmlns:ns3="http://www.w3.org/1999/xhtml"
7           xmlns:mml="http://www.w3.org/1998/Math/MathML"
8           xmlns:db="http://docbook.org/ns/docbook">
9   <info>
10     <pubdate>March 2008</pubdate>
11   </info>
12
13   <refnamediv>
14     <refname>qpsolve</refname>
15
16     <refpurpose>linear quadratic programming solver</refpurpose>
17   </refnamediv>
18
19   <refsynopsisdiv>
20     <title>Calling Sequence</title>
21
22     <synopsis>[x [,iact [,iter [,f]]]]=qpsolve(Q,p,C,b,ci,cs,me)</synopsis>
23   </refsynopsisdiv>
24
25   <refsection>
26     <title>Parameters</title>
27
28     <variablelist>
29       <varlistentry>
30         <term>Q</term>
31
32         <listitem>
33           <para>real positive definite symmetric matrix (dimension <literal>n
34           x n</literal>).</para>
35         </listitem>
36       </varlistentry>
37
38       <varlistentry>
39         <term>p</term>
40
41         <listitem>
42           <para>real (column) vector (dimension <literal> n</literal>)</para>
43         </listitem>
44       </varlistentry>
45
46       <varlistentry>
47         <term>C</term>
48
49         <listitem>
50           <para>real matrix (dimension <literal> (me + md) x n</literal>).
51           This matrix may be dense or sparse.</para>
52         </listitem>
53       </varlistentry>
54
55       <varlistentry>
56         <term>b</term>
57
58         <listitem>
59           <para>RHS column vector (dimension <literal> m=(me +
60           md)</literal>)</para>
61         </listitem>
62       </varlistentry>
63
64       <varlistentry>
65         <term>ci</term>
66
67         <listitem>
68           <para>column vector of lower-bounds (dimension
69           <literal>n</literal>). If there are no lower bound constraints, put
70           <literal>ci = []</literal>. If some components of
71           <literal>x</literal> are bounded from below, set the other
72           (unconstrained) values of <literal>ci</literal> to a very large
73           negative number (e.g. <literal>ci(j) =
74           -number_properties('huge')</literal>.</para>
75         </listitem>
76       </varlistentry>
77
78       <varlistentry>
79         <term>cs</term>
80
81         <listitem>
82           <para>column vector of upper-bounds. (Same remarks as above).</para>
83         </listitem>
84       </varlistentry>
85
86       <varlistentry>
87         <term>me</term>
88
89         <listitem>
90           <para>number of equality constraints (i.e. <literal>C(1:me,:)*x =
91           b(1:me)</literal>)</para>
92         </listitem>
93       </varlistentry>
94
95       <varlistentry>
96         <term>x</term>
97
98         <listitem>
99           <para>optimal solution found.</para>
100         </listitem>
101       </varlistentry>
102
103       <varlistentry>
104         <term>iact</term>
105
106         <listitem>
107           <para>vector, indicator of active constraints. The first non zero
108           entries give the index of the active constraints</para>
109         </listitem>
110       </varlistentry>
111
112       <varlistentry>
113         <term>iter</term>
114
115         <listitem>
116           <para>. 2x1 vector, first component gives the number of "main"
117           iterations, the second one says how many constraints were deleted
118           after they became active.</para>
119         </listitem>
120       </varlistentry>
121     </variablelist>
122   </refsection>
123
124   <refsection>
125     <title>Description</title>
126
127     <informalequation>
128       <mediaobject>
129         <imageobject>
130           <imagedata align="center" fileref="../mml/qld_equation_1.mml" />
131         </imageobject>
132       </mediaobject>
133     </informalequation>
134
135     <para>This function requires <literal>Q</literal> to be symmetric positive
136     definite. If that hypothesis is not satisfied, one may use the quapro
137     function, which is provided in the Scilab quapro toolbox.</para>
138
139     <para>The qpsolve solver is implemented as a Scilab script, which calls
140     the compiled qp_solve primitive. It is provided as a facility, in order to
141     be a direct replacement for the former quapro solver : indeed, the qpsolve
142     solver has been designed so that it provides the same interface, that is,
143     the same input/output arguments. But the x0 and imp input arguments are
144     available in quapro, but not in qpsolve.</para>
145   </refsection>
146
147   <refsection>
148     <title>Examples</title>
149
150     <programlisting role="example"><![CDATA[ 
151 //Find x in R^6 such that:
152 //C1*x = b1 (3 equality constraints i.e me=3)
153 C1= [1,-1,1,0,3,1;
154     -1,0,-3,-4,5,6;
155      2,5,3,0,1,0];
156 b1=[1;2;3];
157
158 //C2*x <= b2 (2 inequality constraints)
159 C2=[0,1,0,1,2,-1;
160     -1,0,2,1,1,0];
161 b2=[-1;2.5];
162
163 //with  x between ci and cs:
164 ci=[-1000;-10000;0;-1000;-1000;-1000];
165 cs=[10000;100;1.5;100;100;1000];
166
167 //and minimize 0.5*x'*Q*x + p'*x with
168 p=[1;2;3;4;5;6]; Q=eye(6,6);
169
170 //No initial point is given;
171 C=[C1;C2];
172 b=[b1;b2];
173 me=3;
174 [x,iact,iter,f]=qpsolve(Q,p,C,b,ci,cs,me)
175 //Only linear constraints (1 to 4) are active 
176  ]]></programlisting>
177   </refsection>
178
179   <refsection>
180     <title>See Also</title>
181
182     <simplelist type="inline">
183       <member><link linkend="optim">optim</link></member>
184
185       <member><link linkend="qp_solve">qp_solve</link></member>
186
187       <member><link linkend="qld">qld</link></member>
188     </simplelist>
189
190     <para>The contributed toolbox "quapro" may also be of interest, in
191     particular for singular <literal>Q</literal>.</para>
192   </refsection>
193
194   <refsection>
195     <title>Memory requirements</title>
196
197     <para>Let r be</para>
198
199     <programlisting role = ""><![CDATA[  
200 r=min(m,n)
201  ]]></programlisting>
202
203     <para>Then the memory required by qpsolve during the computations
204     is</para>
205
206     <programlisting role =""><![CDATA[ 
207 2*n+r*(r+5)/2 + 2*m +1
208  ]]></programlisting>
209   </refsection>
210
211   <refsection>
212     <title>Authors</title>
213
214     <variablelist>
215       <varlistentry>
216         <term>S. Steer</term>
217
218         <listitem>
219           <para>INRIA (Scilab interface)</para>
220         </listitem>
221       </varlistentry>
222
223       <varlistentry>
224         <term>Berwin A. Turlach</term>
225
226         <listitem>
227           <para>School of Mathematics and Statistics (M019), The University of
228           Western Australia, Crawley, AUSTRALIA (solver code)</para>
229         </listitem>
230       </varlistentry>
231     </variablelist>
232   </refsection>
233
234   <refsection>
235     <title>References</title>
236
237     <itemizedlist>
238       <listitem>
239         <para>Goldfarb, D. and Idnani, A. (1982). "Dual and Primal-Dual
240         Methods for Solving Strictly Convex Quadratic Programs", in J.P.
241         Hennart (ed.), Numerical Analysis, Proceedings, Cocoyoc, Mexico 1981,
242         Vol. 909 of Lecture Notes in Mathematics, Springer-Verlag, Berlin, pp.
243         226-239.</para>
244       </listitem>
245
246       <listitem>
247         <para>Goldfarb, D. and Idnani, A. (1983). "A numerically stable dual
248         method for solving strictly convex quadratic programs", Mathematical
249         Programming 27: 1-33.</para>
250       </listitem>
251
252       <listitem>
253         <para>QuadProg (Quadratic Programming Routines), Berwin A
254         Turlach,<ulink
255         url="http://www.maths.uwa.edu.au/~berwin/software/quadprog.html">http://www.maths.uwa.edu.au/~berwin/software/quadprog.html</ulink></para>
256       </listitem>
257     </itemizedlist>
258   </refsection>
259
260   <refsection>
261     <title>Used Functions</title>
262
263     <para>qpgen1.f (also named QP.solve.f) developped by Berwin A. Turlach
264     according to the Goldfarb/Idnani algorithm</para>
265   </refsection>
266 </refentry>