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>