Deleted vectorized computation feature. Deleted neldermead_contour. Fixed the demos.
[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     <informalequation>
106       <mediaobject>
107         <imageobject>
108           <imagedata align="center" fileref="../mml/qp_solve_equation_1.mml" />
109         </imageobject>
110       </mediaobject>
111     </informalequation>
112
113     <para>This function requires <literal>Q</literal> to be symmetric positive
114     definite. If this hypothesis is not satisfied, one may use the contributed
115     <emphasis role="bold">quapro toolbox</emphasis>.</para>
116   </refsection>
117
118   <refsection>
119     <title>Examples</title>
120
121     <programlisting role="example"><![CDATA[ 
122 // Find x in R^6 such that:
123 // x'*C1 = b1 (3 equality constraints i.e me=3)
124 C1= [ 1,-1, 2;
125      -1, 0, 5;
126       1,-3, 3;
127       0,-4, 0;
128       3, 5, 1;
129       1, 6, 0];
130 b1=[1;2;3];
131
132 // x'*C2 >= b2 (2 inequality constraints)
133 C2= [ 0 ,1;
134      -1, 0;
135       0,-2;
136      -1,-1;
137      -2,-1;
138       1, 0];
139 b2=[ 1;-2.5];
140
141 // and minimize 0.5*x'*Q*x - p'*x with
142 p=[-1;-2;-3;-4;-5;-6]; Q=eye(6,6);
143
144 me=3;
145 [x,iact,iter,f]=qp_solve(Q,p,[C1 C2],[b1;b2],me)
146 // Only linear constraints (1 to 4) are active 
147  ]]></programlisting>
148   </refsection>
149
150   <refsection>
151     <title>See Also</title>
152
153     <simplelist type="inline">
154       <member><link linkend="optim">optim</link></member>
155
156       <member><link linkend="qld">qld</link></member>
157
158       <member><link linkend="qpsolve">qpsolve</link></member>
159     </simplelist>
160
161     <para>The contributed toolbox "quapro" may also be of interest, in
162     particular for singular <literal>Q</literal>.</para>
163   </refsection>
164
165   <refsection>
166     <title>Memory requirements</title>
167
168     <para>Let r be</para>
169
170     <programlisting> 
171 r=min(m,n)
172  </programlisting>
173
174     <para>Then the memory required by qp_solve during the computations
175     is</para>
176
177     <programlisting> 
178 2*n+r*(r+5)/2 + 2*m +1
179  </programlisting>
180   </refsection>
181
182   <refsection>
183     <title>Authors</title>
184
185     <variablelist>
186       <varlistentry>
187         <term>S. Steer</term>
188
189         <listitem>
190           <para>INRIA (Scilab interface)</para>
191         </listitem>
192       </varlistentry>
193
194       <varlistentry>
195         <term>Berwin A. Turlach</term>
196
197         <listitem>
198           <para>School of Mathematics and Statistics (M019), The University of
199           Western Australia, Crawley, AUSTRALIA (solver code)</para>
200         </listitem>
201       </varlistentry>
202     </variablelist>
203   </refsection>
204
205   <refsection>
206     <title>References</title>
207
208     <itemizedlist>
209       <listitem>
210         <para>Goldfarb, D. and Idnani, A. (1982). "Dual and Primal-Dual
211         Methods for Solving Strictly Convex Quadratic Programs", in J.P.
212         Hennart (ed.), Numerical Analysis, Proceedings, Cocoyoc, Mexico 1981,
213         Vol. 909 of Lecture Notes in Mathematics, Springer-Verlag, Berlin, pp.
214         226-239.</para>
215       </listitem>
216
217       <listitem>
218         <para>Goldfarb, D. and Idnani, A. (1983). "A numerically stable dual
219         method for solving strictly convex quadratic programs", Mathematical
220         Programming 27: 1-33.</para>
221       </listitem>
222
223       <listitem>
224         <para>QuadProg (Quadratic Programming Routines), Berwin A
225         Turlach,<ulink
226         url="http://www.maths.uwa.edu.au/~berwin/software/quadprog.html">http://www.maths.uwa.edu.au/~berwin/software/quadprog.html</ulink></para>
227       </listitem>
228     </itemizedlist>
229   </refsection>
230
231   <refsection>
232     <title>Used Functions</title>
233
234     <para>qpgen2.f and &gt;qpgen1.f (also named QP.solve.f) developped by
235     Berwin A. Turlach according to the Goldfarb/Idnani algorithm</para>
236   </refsection>
237 </refentry>