1 <?xml version="1.0" encoding="UTF-8"?>
3 * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
4 * Copyright (C) 2008 - INRIA
5 * Copyright (C) 2010 - DIGITEO - Michael Baudin
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
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">
23 <refname>qp_solve</refname>
25 <refpurpose>linear quadratic programming solver builtin</refpurpose>
29 <title>Calling Sequence</title>
31 <synopsis>[x [,iact [,iter [,f]]]] = qp_solve(Q, p, C, b, me)</synopsis>
35 <title>Arguments</title>
43 real positive definite symmetric matrix (dimension <literal>n
56 real (column) vector (dimension <literal> n</literal>)
66 real matrix (dimension <literal> (me + md) x n</literal>).
67 This matrix may be dense or sparse.
77 RHS column vector (dimension <literal> m=(me +
90 number of equality constraints (i.e. <literal>x'*C(:,1:me) =
102 <para>optimal solution found.</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.
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.
133 <title>Description</title>
138 <imagedata align="center" fileref="../mml/qp_solve_equation_1.mml" />
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>.
151 <title>Examples</title>
153 <programlisting role="example"><![CDATA[
154 // Find x in R^6 such that:
155 // x'*C1 = b1 (3 equality constraints i.e me=3)
164 // x'*C2 >= b2 (2 inequality constraints i.e md=2)
173 // and minimize 0.5*x'*Q*x - p'*x with
174 p=[-1;-2;-3;-4;-5;-6]; Q=eye(6,6);
177 [x,iact,iter,f]=qp_solve(Q,p,[C1 C2],[b1;b2],me)
178 // Only linear constraints (1 to 4) are active
183 <title>See Also</title>
185 <simplelist type="inline">
187 <link linkend="optim">optim</link>
191 <link linkend="qld">qld</link>
195 <link linkend="qpsolve">qpsolve</link>
199 <para>The contributed toolbox "quapro" may also be of interest, in
200 particular for singular <literal>Q</literal>.
205 <title>Memory requirements</title>
207 <para>Let r be</para>
213 <para>Then the memory required by qp_solve during the computations
218 2*n+r*(r+5)/2 + 2*m +1
223 <title>References</title>
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.
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.
243 <para>QuadProg (Quadratic Programming Routines), Berwin A
245 url="http://www.maths.uwa.edu.au/~berwin/software/quadprog.html">http://www.maths.uwa.edu.au/~berwin/software/quadprog.html</ulink>
252 <title>Used Functions</title>
254 <para>qpgen2.f and >qpgen1.f (also named QP.solve.f) developped by
255 Berwin A. Turlach according to the Goldfarb/Idnani algorithm