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