Added references.
[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     <para>Minimize <literal> 0.5*x'*Q*x + p'*x</literal></para>
128
129     <para>under the constraints</para>
130
131     <programlisting>
132
133  C(j,:) x = b(j),  j=1,...,me
134  C(j,:) x &lt;= b(j), j=me+1,...,me+md
135  ci &lt;= x &lt;= cs
136    
137     </programlisting>
138
139     <para>This function requires <literal>Q</literal> to be symmetric positive
140     definite. If that hypothesis is not satisfied, one may use the <link
141     linkend="quapro">quapro</link> function, which is provided in the Scilab
142     quapro toolbox.</para>
143
144     <para>The qpsolve solver is implemented as a Scilab script, which calls
145     the compiled qp_solve primitive. It is provided as a facility, in order to
146     be a direct replacement for the former quapro solver : indeed, the qpsolve
147     solver has been designed so that it provides the same interface, that is,
148     the same input/output arguments. But the x0 and imp input arguments are
149     available in quapro, but not in qpsolve.</para>
150   </refsection>
151
152   <refsection>
153     <title>Examples</title>
154
155     <programlisting role="example">
156
157 //Find x in R^6 such that:
158 //C1*x = b1 (3 equality constraints i.e me=3)
159 C1= [1,-1,1,0,3,1;
160     -1,0,-3,-4,5,6;
161      2,5,3,0,1,0];
162 b1=[1;2;3];
163 //C2*x &lt;= b2 (2 inequality constraints)
164 C2=[0,1,0,1,2,-1;
165     -1,0,2,1,1,0];
166 b2=[-1;2.5];
167 //with  x between ci and cs:
168 ci=[-1000;-10000;0;-1000;-1000;-1000];cs=[10000;100;1.5;100;100;1000];
169 //and minimize 0.5*x'*Q*x + p'*x with
170 p=[1;2;3;4;5;6]; Q=eye(6,6);
171 //No initial point is given;
172 C=[C1;C2] ; //
173 b=[b1;b2] ;  //
174 me=3;
175 [x,iact,iter,f]=qpsolve(Q,p,C,b,ci,cs,me)
176 //Only linear constraints (1 to 4) are active 
177  
178   </programlisting>
179   </refsection>
180
181   <refsection>
182     <title>See Also</title>
183
184     <simplelist type="inline">
185       <member><link linkend="optim">optim</link></member>
186
187       <member><link linkend="qp_solve">qp_solve</link></member>
188
189       <member><link linkend="qld">qld</link></member>
190     </simplelist>
191
192     <para>The contributed toolbox "quapro" may also be of interest, in
193     particular for singular <literal>Q</literal>.</para>
194   </refsection>
195
196   <refsection>
197     <title>Memory requirements</title>
198
199     <para>Let r be</para>
200
201     <programlisting>r=min(m,n)</programlisting>
202
203     <para>Then the memory required by qpsolve during the computations
204     is</para>
205
206     <programlisting>2*n+r*(r+5)/2 + 2*m +1</programlisting>
207   </refsection>
208
209   <refsection>
210     <title>Authors</title>
211
212     <variablelist>
213       <varlistentry>
214         <term>S. Steer</term>
215
216         <listitem>
217           <para>INRIA (Scilab interface)</para>
218         </listitem>
219       </varlistentry>
220
221       <varlistentry>
222         <term>Berwin A. Turlach</term>
223
224         <listitem>
225           <para>School of Mathematics and Statistics (M019), The University of
226           Western Australia, Crawley, AUSTRALIA (solver code)</para>
227         </listitem>
228       </varlistentry>
229     </variablelist>
230   </refsection>
231
232   <refsection>
233     <title>References</title>
234
235     <itemizedlist>
236       <listitem>
237         <para>Goldfarb, D. and Idnani, A. (1982). "Dual and Primal-Dual
238         Methods for Solving Strictly Convex Quadratic Programs", in J.P.
239         Hennart (ed.), Numerical Analysis, Proceedings, Cocoyoc, Mexico 1981,
240         Vol. 909 of Lecture Notes in Mathematics, Springer-Verlag, Berlin, pp.
241         226-239.</para>
242       </listitem>
243
244       <listitem>
245         <para>Goldfarb, D. and Idnani, A. (1983). "A numerically stable dual
246         method for solving strictly convex quadratic programs", Mathematical
247         Programming 27: 1-33.</para>
248       </listitem>
249
250       <listitem>
251         <para>QuadProg (Quadratic Programming Routines), Berwin A
252         Turlach,<ulink
253         url="http://www.maths.uwa.edu.au/~berwin/software/quadprog.html">http://www.maths.uwa.edu.au/~berwin/software/quadprog.html</ulink></para>
254       </listitem>
255     </itemizedlist>
256   </refsection>
257
258   <refsection>
259     <title>Used Functions</title>
260
261     <para>qpgen1.f (also named QP.solve.f) developped by Berwin A. Turlach
262     according to the Goldfarb/Idnani algorithm</para>
263   </refsection>
264 </refentry>