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 i.e md=2)
 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>