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">
4 <refname>qpsolve</refname>
5 <refpurpose>linear quadratic programming solver</refpurpose>
8 <title>Calling Sequence</title>
9 <synopsis>[x [,iact [,iter [,f]]]]=qpsolve(Q,p,C,b,ci,cs,me)</synopsis>
12 <title>Arguments</title>
18 real positive definite symmetric matrix (dimension <literal>n
29 real (column) vector (dimension <literal> n</literal>)
37 real matrix (dimension <literal> (me + md) x n</literal>).
38 This matrix may be dense or sparse.
46 RHS column vector (dimension <literal> m=(me +
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')
71 <para>column vector of upper-bounds. (Same remarks as above).</para>
78 number of equality constraints (i.e. <literal>C(1:me,:)*x =
88 <para>optimal solution found.</para>
94 <para>vector, indicator of active constraints. The first non zero
95 entries give the index of the active constraints
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.
111 <title>Description</title>
115 <imagedata align="center" fileref="../mml/qld_equation_1.mml"/>
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.
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.
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)
142 //C2*x <= b2 (2 inequality constraints i.e md=2)
147 //with x between ci and cs:
148 ci=[-1000;-10000;0;-1000;-1000;-1000];
149 cs=[10000;100;1.5;100;100;1000];
151 //and minimize 0.5*x'*Q*x + p'*x with
152 p=[1;2;3;4;5;6]; Q=eye(6,6);
154 //No initial point is given;
158 [x,iact,iter,f]=qpsolve(Q,p,C,b,ci,cs,me)
159 //Only linear constraints (1 to 4) are active
162 <refsection role="see also">
163 <title>See Also</title>
164 <simplelist type="inline">
166 <link linkend="optim">optim</link>
169 <link linkend="qp_solve">qp_solve</link>
172 <link linkend="qld">qld</link>
175 <para>The contributed toolbox "quapro" may also be of interest, in
176 particular for singular <literal>Q</literal>.
180 <title>Memory requirements</title>
181 <para>Let r be</para>
182 <programlisting role=""><![CDATA[
185 <para>Then the memory required by qpsolve during the computations
188 <programlisting role=""><![CDATA[
189 2*n+r*(r+5)/2 + 2*m +1
193 <title>References</title>
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.
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.
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>
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