0e24b13deec177cdf425b3643fe5dc6313473c2a
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" version="5.0-subset Scilab" xml:id="qp_solve" xml:lang="ja">
3     <refnamediv>
4         <refname>qp_solve</refname>
5         <refpurpose>組み込みの線形二次計画ソルバー</refpurpose>
6     </refnamediv>
7     <refsynopsisdiv>
8         <title>呼び出し手順</title>
9         <synopsis>[x [,iact [,iter [,f]]]]=qp_solve(Q,p1,C1,b,me)</synopsis>
10     </refsynopsisdiv>
11     <refsection>
12         <title>パラメータ</title>
13         <variablelist>
14             <varlistentry>
15                 <term>Q</term>
16                 <listitem>
17                     <para>
18                         実数正定対称行列 (次元 <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                         実数 (列) ベクトル (次元 <literal> n</literal>)
30                     </para>
31                 </listitem>
32             </varlistentry>
33             <varlistentry>
34                 <term>C</term>
35                 <listitem>
36                     <para>
37                         実数行列 (次元 <literal> (me + md) x n</literal>).
38                         この行列は通常行列または疎行列とすることができます.
39                     </para>
40                 </listitem>
41             </varlistentry>
42             <varlistentry>
43                 <term>b</term>
44                 <listitem>
45                     <para>
46                         RHS 列ベクトル (次元 <literal> m=(me +
47                             md)
48                         </literal>
49                         )
50                     </para>
51                 </listitem>
52             </varlistentry>
53             <varlistentry>
54                 <term>me</term>
55                 <listitem>
56                     <para>
57                         等式拘束の数 (すなわち <literal>x'*C(:,1:me) =
58                             b(1:me)'
59                         </literal>
60                         )
61                     </para>
62                 </listitem>
63             </varlistentry>
64             <varlistentry>
65                 <term>x</term>
66                 <listitem>
67                     <para>見つかった最適解.</para>
68                 </listitem>
69             </varlistentry>
70             <varlistentry>
71                 <term>iact</term>
72                 <listitem>
73                     <para>ベクトル, アクティブな拘束のインジケータ. 最初の
74                         非ゼロのエントリは
75                         アクティブの拘束のインデックスを出力します
76                     </para>
77                 </listitem>
78             </varlistentry>
79             <varlistentry>
80                 <term>iter</term>
81                 <listitem>
82                     <para>2x1ベクトル, 最初の要素には
83                         "main" 反復の数を出力します.
84                         2番目の要素には,アクティブになった後に削除された拘束の数を出力します.
85                     </para>
86                 </listitem>
87             </varlistentry>
88         </variablelist>
89     </refsection>
90     <refsection>
91         <title>説明</title>
92         <informalequation>
93             <mediaobject>
94                 <imageobject>
95                     <imagedata align="center" fileref="../mml/qp_solve_equation_1.mml"/>
96                 </imageobject>
97             </mediaobject>
98         </informalequation>
99         <para>
100             この関数は,<literal>Q</literal>が対称正定であることを必要とします.
101             この仮定が満たされない場合には, <emphasis role="bold">quaproツールボックス</emphasis>で
102             指定されたquapro 関数を使用することができます.
103         </para>
104     </refsection>
105     <refsection>
106         <title>例</title>
107         <programlisting role="example"><![CDATA[
108 // 以下のような x ( R^6)を探す:
109 // x'*C1 = b1 (3 個の等式拘束 すなわち me=3)
110 C1= [ 1,-1, 2;
111      -1, 0, 5;
112       1,-3, 3;
113       0,-4, 0;
114       3, 5, 1;
115       1, 6, 0];
116 b1=[1;2;3];
118 // x'*C2 >= b2 (2 個の不等式拘束)
119 C2= [ 0 ,1;
120      -1, 0;
121       0,-2;
122      -1,-1;
123      -2,-1;
124       1, 0];
125 b2=[ 1;-2.5];
127 // 以下の条件のもとで 0.5*x'*Q*x + p'*x を最小化
128 p=[-1;-2;-3;-4;-5;-6]; Q=eye(6,6);
130 me=3;
131 [x,iact,iter,f]=qp_solve(Q,p,[C1 C2],[b1;b2],me)
132 // 線形拘束 (1 から 4) のみアクティブ
133  ]]></programlisting>
134     </refsection>
135     <refsection role="see also">
136         <title>参照</title>
137         <simplelist type="inline">
138             <member>
140             </member>
141             <member>
143             </member>
144             <member>
146             </member>
147         </simplelist>
148         <para>
149             ツールボックス "quapro" も特に<literal>Q</literal>が
150             特異な場合には有用かもしれません.
151         </para>
152     </refsection>
153     <refsection>
154         <title>所要メモリ</title>
155         <para>rを以下とすると</para>
156         <programlisting>
157             r=min(m,n)
158         </programlisting>
159         <para>計算時にqp_solveに必要とされるメモリは,以下となります</para>
160         <programlisting>
161             2*n+r*(r+5)/2 + 2*m +1
162         </programlisting>
163     </refsection>
164     <refsection>
165         <title>参考文献</title>
166         <itemizedlist>
167             <listitem>
168                 <para>Goldfarb, D. and Idnani, A. (1982). "Dual and Primal-Dual
169                     Methods for Solving Strictly Convex Quadratic Programs", in J.P.
170                     Hennart (ed.), Numerical Analysis, Proceedings, Cocoyoc, Mexico 1981,
171                     Vol. 909 of Lecture Notes in Mathematics, Springer-Verlag, Berlin, pp.
172                     226-239.
173                 </para>
174             </listitem>
175             <listitem>
176                 <para>Goldfarb, D. and Idnani, A. (1983). "A numerically stable dual
177                     method for solving strictly convex quadratic programs", Mathematical
178                     Programming 27: 1-33.
179                 </para>
180             </listitem>
181             <listitem>