Deleted vectorized computation feature. Deleted neldermead_contour. Fixed the demos.
[scilab.git] / scilab / modules / optimization / help / en_US / semidef.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  * 
6  * This file must be used under the terms of the CeCILL.
7  * This source file is licensed as described in the file COPYING, which
8  * you should have received as part of this distribution.  The terms
9  * are also available at    
10  * http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
11  *
12  -->
13 <refentry version="5.0-subset Scilab" xml:id="semidef" xml:lang="en"
14           xmlns="http://docbook.org/ns/docbook"
15           xmlns:xlink="http://www.w3.org/1999/xlink"
16           xmlns:svg="http://www.w3.org/2000/svg"
17           xmlns:ns4="http://www.w3.org/1999/xhtml"
18           xmlns:mml="http://www.w3.org/1998/Math/MathML"
19           xmlns:db="http://docbook.org/ns/docbook">
20   <info>
21     <pubdate>$LastChangedDate: 2008-03-26 09:50:39 +0100 (mer, 26 mar 2008)
22     $</pubdate>
23   </info>
24
25   <refnamediv>
26     <refname>semidef</refname>
27
28     <refpurpose>semidefinite programming</refpurpose>
29   </refnamediv>
30
31   <refsynopsisdiv>
32     <title>Calling Sequence</title>
33
34     <synopsis>[x,Z,ul,info]=semidef(x0,Z0,F,blck_szs,c,options)</synopsis>
35   </refsynopsisdiv>
36
37   <refsection>
38     <title>Parameters</title>
39
40     <variablelist>
41       <varlistentry>
42         <term>x0</term>
43
44         <listitem>
45           <para>m x 1 real column vector (must be strictly primal feasible,
46           see below)</para>
47         </listitem>
48       </varlistentry>
49
50       <varlistentry>
51         <term>Z0</term>
52
53         <listitem>
54           <para>L x 1 real vector (compressed form of a strictly feasible dual
55           matrix, see below)</para>
56         </listitem>
57       </varlistentry>
58
59       <varlistentry>
60         <term>F</term>
61
62         <listitem>
63           <para>L x (m+1) real matrix</para>
64         </listitem>
65       </varlistentry>
66
67       <varlistentry>
68         <term>blck_szs</term>
69
70         <listitem>
71           <para>p x 2 integer matrix (sizes of the blocks) defining the
72           dimensions of the (square) diagonal blocks
73           <literal>size(Fi(j)=blck_szs(j) j=1,...,m+1</literal>.</para>
74         </listitem>
75       </varlistentry>
76
77       <varlistentry>
78         <term>c</term>
79
80         <listitem>
81           <para>m x 1 real vector</para>
82         </listitem>
83       </varlistentry>
84
85       <varlistentry>
86         <term>options</term>
87
88         <listitem>
89           <para>row vector with five entries
90           <literal>[nu,abstol,reltol,0,maxiters]</literal></para>
91         </listitem>
92       </varlistentry>
93
94       <varlistentry>
95         <term>ul</term>
96
97         <listitem>
98           <para>row vector with two entries</para>
99         </listitem>
100       </varlistentry>
101     </variablelist>
102   </refsection>
103
104   <refsection>
105     <title>Description</title>
106
107     <para><literal>[x,Z,ul,info]=semidef(x0,Z0,F,blck_szs,c,options)</literal>
108     solves semidefinite program:</para>
109
110     <informalequation>
111       <mediaobject>
112         <imageobject>
113           <imagedata align="center" fileref="../mml/semidef_equation_1.mml" />
114         </imageobject>
115       </mediaobject>
116     </informalequation>
117
118     <para>and its dual:</para>
119
120     <informalequation>
121       <mediaobject>
122         <imageobject>
123           <imagedata align="center" fileref="../mml/semidef_equation_2.mml" />
124         </imageobject>
125       </mediaobject>
126     </informalequation>
127
128     <para>exploiting block structure in the matrices
129     <literal>F_i</literal>.</para>
130
131     <para>It interfaces L. Vandenberghe and S. Boyd sp.c program.</para>
132
133     <para>The <literal>Fi's</literal> matrices are stored columnwise in
134     <literal>F</literal> in compressed format: if <literal>F_i^j</literal>,
135     i=0,..,m, j=1,...,L denote the jth (symmetric) diagonal block of
136     <literal>F_i</literal>, then</para>
137
138     <informalequation>
139       <mediaobject>
140         <imageobject>
141           <imagedata align="center" fileref="../mml/semidef_equation_3.mml" />
142         </imageobject>
143       </mediaobject>
144     </informalequation>
145
146     <para>where <literal>pack(M)</literal>, for symmetric
147     <literal>M</literal>, is the vector
148     <literal>[M(1,1);M(1,2);...;M(1,n);M(2,2);M(2,3);...;M(2,n);...;M(n,n)]</literal>
149     (obtained by scanning columnwise the lower triangular part of
150     <literal>M</literal>).</para>
151
152     <para><literal>blck_szs</literal> gives the size of block
153     <literal>j</literal>, ie,
154     <literal>size(F_i^j)=blck_szs(j)</literal>.</para>
155
156     <para>Z is a block diagonal matrix with L blocks <literal>Z^0, ...,
157     Z^{L-1}</literal>. <literal>Z^j</literal> has size <literal>blck_szs[j]
158     times blck_szs[j]</literal>. Every block is stored using packed storage of
159     the lower triangular part.</para>
160
161     <para>The 2 vector <literal>ul</literal> contains the primal objective
162     value <literal>c'*x</literal> and the dual objective value
163     <literal>-trace(F_0*Z</literal>).</para>
164
165     <para>The entries of <literal>options</literal> are respectively:
166     <literal>nu</literal> = a real parameter which ntrols the rate of
167     convergence. <literal>abstol</literal> = absolute tolerance.
168     <literal>reltol</literal> = relative tolerance (has a special meaning when
169     negative). <literal>tv</literal> target value, only referenced if
170     <literal>reltol &lt; 0</literal>. <literal>iters</literal> = on entry:
171     maximum number of iterations &gt;= 0, on exit: the number of iterations
172     taken. Notice that the absolute tolerance cannot be lower than 1.0e-8,
173     that is, the absolute tolerance used in the algorithm is the maximum of
174     the user-defined tolerance and the constant tolerance 1.0e-8.</para>
175
176     <para><literal>info</literal> returns 1 if maxiters exceeded, 2 if
177     absolute accuracy is reached, 3 if relative accuracy is reached, 4 if
178     target value is reached, 5 if target value is not achievable; negative
179     values indicate errors.</para>
180
181     <para>Convergence criterion:</para>
182
183     <programlisting role = ""><![CDATA[ 
184 (1) maxiters is exceeded
185 (2) duality gap is less than abstol
186 (3) primal and dual objective are both positive and
187     duality gap is less than (reltol * dual objective)
188     or primal and dual objective are both negative and
189     duality gap is less than (reltol * minus the primal objective)
190 (4) reltol is negative and
191     primal objective is less than tv or dual objective is greater
192     than tv
193  ]]></programlisting>
194   </refsection>
195
196   <refsection>
197     <title>Examples</title>
198
199     <programlisting role="example"><![CDATA[ 
200 F0=[2,1,0,0;
201     1,2,0,0;
202     0,0,3,1
203     0,0,1,3];
204
205 F1=[1,2,0,0;
206     2,1,0,0;
207     0,0,1,3;
208     0,0,3,1]
209
210 F2=[2,2,0,0;
211     2,2,0,0;
212     0,0,3,4;
213     0,0,4,4];
214
215 blck_szs=[2,2];
216
217 F01=F0(1:2,1:2);F02=F0(3:4,3:4);
218 F11=F1(1:2,1:2);F12=F1(3:4,3:4);
219 F21=F2(1:2,1:2);F22=F2(3:4,3:4);
220
221 x0=[0;0]
222 Z0=2*F0;
223 Z01=Z0(1:2,1:2);Z02=Z0(3:4,3:4);
224 FF=[[F01(:);F02(:)],[F11(:);F12(:)],[F21(:);F22(:)]]
225 ZZ0=[[Z01(:);Z02(:)]];
226
227 c=[trace(F1*Z0);trace(F2*Z0)];
228 options=[10,1.d-10,1.d-10,0,50];
229
230 [x,Z,ul,info]=semidef(x0,pack(ZZ0),pack(FF),blck_szs,c,options)
231
232 w=vec2list(unpack(Z,blck_szs),[blck_szs;blck_szs]);Z=sysdiag(w(1),w(2))
233
234 c'*x+trace(F0*Z)
235 spec(F0+F1*x(1)+F2*x(2))
236 trace(F1*Z)-c(1)
237 trace(F2*Z)-c(2)
238  ]]></programlisting>
239   </refsection>
240
241   <refsection>
242     <title>References</title>
243
244     <para>L. Vandenberghe and S. Boyd, " Semidefinite Programming,"
245     Informations Systems Laboratory, Stanford University, 1994.</para>
246
247     <para>Ju. E. Nesterov and M. J. Todd, "Self-Scaled Cones and
248     Interior-Point Methods in Nonlinear Programming," Working Paper, CORE,
249     Catholic University of Louvain, Louvain-la-Neuve, Belgium, April
250     1994.</para>
251
252     <para>SP: Software for Semidefinite Programming, <ulink
253     url="http://www.ee.ucla.edu/~vandenbe/sp.html">http://www.ee.ucla.edu/~vandenbe/sp.html</ulink></para>
254   </refsection>
255 </refentry>