Added references.
[scilab.git] / scilab / modules / optimization / help / en_US / qp_solve.xml
1 <?xml version="1.0" encoding="UTF-8"?>
2 <refentry version="5.0-subset Scilab" xml:id="qp_solve" 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>qp_solve</refname>
15
16     <refpurpose>linear quadratic programming solver builtin</refpurpose>
17   </refnamediv>
18
19   <refsynopsisdiv>
20     <title>Calling Sequence</title>
21
22     <synopsis>[x [,iact [,iter [,f]]]]=qp_solve(Q,p1,C1,b,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>me</term>
66
67         <listitem>
68           <para>number of equality constraints (i.e. <literal>x'*C(:,1:me) =
69           b(1:me)'</literal>)</para>
70         </listitem>
71       </varlistentry>
72
73       <varlistentry>
74         <term>x</term>
75
76         <listitem>
77           <para>optimal solution found.</para>
78         </listitem>
79       </varlistentry>
80
81       <varlistentry>
82         <term>iact</term>
83
84         <listitem>
85           <para>vector, indicator of active constraints. The first non zero
86           entries give the index of the active constraints</para>
87         </listitem>
88       </varlistentry>
89
90       <varlistentry>
91         <term>iter</term>
92
93         <listitem>
94           <para>2x1 vector, first component gives the number of "main"
95           iterations, the second one says how many constraints were deleted
96           after they became active.</para>
97         </listitem>
98       </varlistentry>
99     </variablelist>
100   </refsection>
101
102   <refsection>
103     <title>Description</title>
104
105     <para>Minimize <literal> 0.5*x'*Q*x - p'*x</literal></para>
106
107     <para>under the constraints</para>
108
109     <programlisting>
110
111  x' C(:,j) = b(j),  j=1,...,me
112  x' C(:,j) &gt;= b(j), j=me+1,...,me+md
113    
114     </programlisting>
115
116     <para>This function requires <literal>Q</literal> to be symmetric positive
117     definite. If this hypothesis is not satisfied, one may use the contributed
118     <emphasis role="bold">quapro toolbox</emphasis>.</para>
119   </refsection>
120
121   <refsection>
122     <title>Examples</title>
123
124     <programlisting role="example">
125
126 //Find x in R^6 such that:
127 //x'*C1 = b1 (3 equality constraints i.e me=3)
128 C1= [ 1,-1, 2;
129      -1, 0, 5;
130       1,-3, 3;
131       0,-4, 0;
132       3, 5, 1;
133       1, 6, 0];
134 b1=[1;2;3];
135
136 //x'*C2 &gt;= b2 (2 inequality constraints)
137 C2= [ 0 ,1;
138      -1, 0;
139       0,-2;
140      -1,-1;
141      -2,-1;
142       1, 0];
143 b2=[ 1;-2.5];
144
145 //and minimize 0.5*x'*Q*x - p'*x with
146 p=[-1;-2;-3;-4;-5;-6]; Q=eye(6,6);
147
148 me=3;
149 [x,iact,iter,f]=qp_solve(Q,p,[C1 C2],[b1;b2],me)
150 //Only linear constraints (1 to 4) are active 
151  
152   </programlisting>
153   </refsection>
154
155   <refsection>
156     <title>See Also</title>
157
158     <simplelist type="inline">
159       <member><link linkend="optim">optim</link></member>
160
161       <member><link linkend="qld">qld</link></member>
162
163       <member><link linkend="qpsolve">qpsolve</link></member>
164     </simplelist>
165
166     <para>The contributed toolbox "quapro" may also be of interest, in
167     particular for singular <literal>Q</literal>.</para>
168   </refsection>
169
170   <refsection>
171     <title>Memory requirements</title>
172
173     <para>Let r be </para>
174
175     <programlisting>r=min(m,n)</programlisting>
176
177     <para>Then the memory required by qp_solve during the computations is
178     </para>
179
180     <programlisting>2*n+r*(r+5)/2 + 2*m +1</programlisting>
181   </refsection>
182
183   <refsection>
184     <title>Authors</title>
185
186     <variablelist>
187       <varlistentry>
188         <term>S. Steer</term>
189
190         <listitem>
191           <para>INRIA (Scilab interface)</para>
192         </listitem>
193       </varlistentry>
194
195       <varlistentry>
196         <term>Berwin A. Turlach</term>
197
198         <listitem>
199           <para>School of Mathematics and Statistics (M019), The University of
200           Western Australia, Crawley, AUSTRALIA (solver code)</para>
201         </listitem>
202       </varlistentry>
203     </variablelist>
204   </refsection>
205
206   <refsection>
207     <title>References</title>
208
209     <itemizedlist>
210       <listitem>
211         <para>Goldfarb, D. and Idnani, A. (1982). "Dual and Primal-Dual
212         Methods for Solving Strictly Convex Quadratic Programs", in J.P.
213         Hennart (ed.), Numerical Analysis, Proceedings, Cocoyoc, Mexico 1981,
214         Vol. 909 of Lecture Notes in Mathematics, Springer-Verlag, Berlin, pp.
215         226-239.</para>
216       </listitem>
217
218       <listitem>
219         <para>Goldfarb, D. and Idnani, A. (1983). "A numerically stable dual
220         method for solving strictly convex quadratic programs", Mathematical
221         Programming 27: 1-33.</para>
222       </listitem>
223
224       <listitem>
225         <para>QuadProg (Quadratic Programming Routines), Berwin A
226         Turlach,<ulink
227         url="http://www.maths.uwa.edu.au/~berwin/software/quadprog.html">http://www.maths.uwa.edu.au/~berwin/software/quadprog.html</ulink></para>
228       </listitem>
229     </itemizedlist>
230   </refsection>
231
232   <refsection>
233     <title>Used Functions</title>
234
235     <para>qpgen2.f and &gt;qpgen1.f (also named QP.solve.f) developped by
236     Berwin A. Turlach according to the Goldfarb/Idnani algorithm</para>
237   </refsection>
238 </refentry>