Optimization module: minor improvements in qpsolve() and qld() docs
[scilab.git] / scilab / modules / optimization / help / en_US / qp_solve.xml
1 <?xml version="1.0" encoding="UTF-8"?>
2 <!--
3  * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
4  * Copyright (C) 2008 - INRIA
5  * Copyright (C) 2010 - DIGITEO - Michael Baudin
6  *
7  * This file must be used under the terms of the CeCILL.
8  * This source file is licensed as described in the file COPYING, which
9  * you should have received as part of this distribution.  The terms
10  * are also available at
11  * http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
12  *
13  -->
14 <refentry xml:id="qp_solve" xml:lang="en"
15           xmlns="http://docbook.org/ns/docbook"
16           xmlns:xlink="http://www.w3.org/1999/xlink"
17           xmlns:svg="http://www.w3.org/2000/svg"
18           xmlns:ns3="http://www.w3.org/1999/xhtml"
19           xmlns:mml="http://www.w3.org/1998/Math/MathML"
20           xmlns:db="http://docbook.org/ns/docbook"
21           xmlns:scilab="http://www.scilab.org">
22     <refnamediv>
23         <refname>qp_solve</refname>
24         
25         <refpurpose>linear quadratic programming solver builtin</refpurpose>
26     </refnamediv>
27     
28     <refsynopsisdiv>
29         <title>Calling Sequence</title>
30         
31         <synopsis>[x [,iact [,iter [,f]]]] = qp_solve(Q, p, C, b, me)</synopsis>
32     </refsynopsisdiv>
33     
34     <refsection>
35         <title>Arguments</title>
36         
37         <variablelist>
38             <varlistentry>
39                 <term>Q</term>
40                 
41                 <listitem>
42                     <para>
43                         real positive definite symmetric matrix (dimension <literal>n
44                             x n
45                         </literal>
46                         ).
47                     </para>
48                 </listitem>
49             </varlistentry>
50             
51             <varlistentry>
52                 <term>p</term>
53                 
54                 <listitem>
55                     <para>
56                         real (column) vector (dimension <literal> n</literal>)
57                     </para>
58                 </listitem>
59             </varlistentry>
60             
61             <varlistentry>
62                 <term>C</term>
63                 
64                 <listitem>
65                     <para>
66                         real matrix (dimension <literal> (me + md) x n</literal>).
67                         This matrix may be dense or sparse.
68                     </para>
69                 </listitem>
70             </varlistentry>
71             
72             <varlistentry>
73                 <term>b</term>
74                 
75                 <listitem>
76                     <para>
77                         RHS column vector (dimension <literal> m=(me +
78                             md)
79                         </literal>
80                         )
81                     </para>
82                 </listitem>
83             </varlistentry>
84             
85             <varlistentry>
86                 <term>me</term>
87                 
88                 <listitem>
89                     <para>
90                         number of equality constraints (i.e. <literal>x'*C(:,1:me) =
91                             b(1:me)'
92                         </literal>
93                         )
94                     </para>
95                 </listitem>
96             </varlistentry>
97             
98             <varlistentry>
99                 <term>x</term>
100                 
101                 <listitem>
102                     <para>optimal solution found.</para>
103                 </listitem>
104             </varlistentry>
105             
106             <varlistentry>
107                 <term>iact</term>
108                 
109                 <listitem>
110                     <para>
111                         vector, indicator of active constraints.
112                         The non zero entries give the index of the active constraints.
113                         The entries of the iact vector are ordered this way: equality constraints come first, 
114                         then come the inequality constraints.
115                     </para>
116                 </listitem>
117             </varlistentry>
118             
119             <varlistentry>
120                 <term>iter</term>
121                 
122                 <listitem>
123                     <para>2x1 vector, first component gives the number of "main"
124                         iterations, the second one says how many constraints were deleted
125                         after they became active.
126                     </para>
127                 </listitem>
128             </varlistentry>
129         </variablelist>
130     </refsection>
131     
132     <refsection>
133         <title>Description</title>
134         
135         <informalequation>
136             <mediaobject>
137                 <imageobject>
138                     <imagedata align="center" fileref="../mml/qp_solve_equation_1.mml" />
139                 </imageobject>
140             </mediaobject>
141         </informalequation>
142         
143         <para>
144             This function requires <literal>Q</literal> to be symmetric positive
145             definite. If this hypothesis is not satisfied, one may use the contributed
146             <emphasis role="bold">quapro toolbox</emphasis>.
147         </para>
148     </refsection>
149     
150     <refsection>
151         <title>Examples</title>
152         
153         <programlisting role="example"><![CDATA[ 
154 // Find x in R^6 such that:
155 // x'*C1 = b1 (3 equality constraints i.e me=3)
156 C1= [ 1,-1, 2;
157      -1, 0, 5;
158       1,-3, 3;
159       0,-4, 0;
160       3, 5, 1;
161       1, 6, 0];
162 b1=[1;2;3];
163
164 // x'*C2 >= b2 (2 inequality constraints i.e md=2)
165 C2= [ 0 ,1;
166      -1, 0;
167       0,-2;
168      -1,-1;
169      -2,-1;
170       1, 0];
171 b2=[ 1;-2.5];
172
173 // and minimize 0.5*x'*Q*x - p'*x with
174 p=[-1;-2;-3;-4;-5;-6]; Q=eye(6,6);
175
176 me=3;
177 [x,iact,iter,f]=qp_solve(Q,p,[C1 C2],[b1;b2],me)
178 // Only linear constraints (1 to 4) are active 
179  ]]></programlisting>
180     </refsection>
181     
182     <refsection>
183         <title>See Also</title>
184         
185         <simplelist type="inline">
186             <member>
187                 <link linkend="optim">optim</link>
188             </member>
189             
190             <member>
191                 <link linkend="qld">qld</link>
192             </member>
193             
194             <member>
195                 <link linkend="qpsolve">qpsolve</link>
196             </member>
197         </simplelist>
198         
199         <para>The contributed toolbox "quapro" may also be of interest, in
200             particular for singular <literal>Q</literal>.
201         </para>
202     </refsection>
203     
204     <refsection>
205         <title>Memory requirements</title>
206         
207         <para>Let r be</para>
208         
209         <programlisting> 
210             r=min(m,n)
211         </programlisting>
212         
213         <para>Then the memory required by qp_solve during the computations
214             is
215         </para>
216         
217         <programlisting> 
218             2*n+r*(r+5)/2 + 2*m +1
219         </programlisting>
220     </refsection>
221     
222     <refsection>
223         <title>References</title>
224         
225         <itemizedlist>
226             <listitem>
227                 <para>Goldfarb, D. and Idnani, A. (1982). "Dual and Primal-Dual
228                     Methods for Solving Strictly Convex Quadratic Programs", in J.P.
229                     Hennart (ed.), Numerical Analysis, Proceedings, Cocoyoc, Mexico 1981,
230                     Vol. 909 of Lecture Notes in Mathematics, Springer-Verlag, Berlin, pp.
231                     226-239.
232                 </para>
233             </listitem>
234             
235             <listitem>
236                 <para>Goldfarb, D. and Idnani, A. (1983). "A numerically stable dual
237                     method for solving strictly convex quadratic programs", Mathematical
238                     Programming 27: 1-33.
239                 </para>
240             </listitem>
241             
242             <listitem>
243                 <para>QuadProg (Quadratic Programming Routines), Berwin A
244                     Turlach,<ulink
245         url="http://www.maths.uwa.edu.au/~berwin/software/quadprog.html">http://www.maths.uwa.edu.au/~berwin/software/quadprog.html</ulink>
246                 </para>
247             </listitem>
248         </itemizedlist>
249     </refsection>
250     
251     <refsection>
252         <title>Used Functions</title>
253         
254         <para>qpgen2.f and &gt;qpgen1.f (also named QP.solve.f) developped by
255             Berwin A. Turlach according to the Goldfarb/Idnani algorithm
256         </para>
257     </refsection>
258 </refentry>