1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
.TH semidef 1 "April 1993" "Scilab Group" "Scilab Function"
.so ../sci.an
.SH NAME
semidef - semidefinite programming
.SH CALLING SEQUENCE
.nf
[x,Z,ul,info]=semidef(x0,Z0,F,blck_szs,c,options)
.fi
.SH PARAMETERS
.TP 10
x0
: m x 1 real column vector (must be strictly primal feasible, see below)
.TP
Z0
: L x 1 real vector (compressed form of a strictly feasible dual
matrix, see below)
.TP
F
: L x (m+1) real matrix
.TP
blck_szs
: p x 2 integer matrix (sizes of the blocks) defining the dimensions
of the (square) diagonal blocks \fVsize(Fi(j)=blck_szs(j) j=1,...,m+1\fR.
.TP
c
: m x 1 real vector
.TP
options
: row vector with five entries \fV[nu,abstol,reltol,0,maxiters]\fR
.TP
ul
: row vector with two entries
.SH DESCRIPTION
\fV[x,Z,ul,info]=semidef(x0,Z0,F,blck_szs,c,options)\fR
solves semidefinite program:
.nf
minimize c'*x
subject to F_0 + x_1*F_1 + ... + x_m*F_m >= 0
and its dual
maximize -Tr F_0 Z
subject to Tr F_i Z = c_i, i=1,...,m
Z >= 0
.fi
exploiting block structure in the matrices F_i.
.LP
It interfaces L. Vandenberghe and S. Boyd sp.c program.
.LP
The \fVFi's\fR matrices are stored columnwise in \fVF\fR in
compressed format: if F_i^j, i=0,..,m, j=1,...,L denote the jth
(symmetric) diagonal block of F_i, then
.nf
[ pack(F_0^1) pack(F_1^1) ... pack(F_m^1) ]
[ pack(F_0^2) pack(F_1^2) ... pack(F_m^2) ]
F= [ ... ... ... ]
[ pack(F_0^L) pack(F_1^L) ... pack(F_m^L) ]
.fi
where \fVpack(M)\fR, for symmetric \fVM\fR, is the vector
\fV[M(1,1);M(1,2);...;M(1,n);M(2,2);M(2,3);...;M(2,n);...;M(n,n)]\fR
(obtained by scanning columnwise the lower triangular part of \fVM\fR).
.LP
\fVblck_szs\fR gives the size of block \fVj\fR, ie,
\fVsize(F_i^j)=blck_szs(j)\fR.
.LP
Z is a block diagonal matrix with L blocks \fVZ^0, ..., Z^{L-1}\fR.
\fVZ^j\fR has size \fVblck_szs[j] times blck_szs[j]\fR.
Every block is stored using packed storage of the lower triangular part.
.LP
The 2 vector \fVul\fR contains the primal objective value \fVc'*x\fR
and the dual objective value \fV-Tr F_0*Z\fR.
.LP
The entries of \fVoptions\fR are respectively:
\fVnu\fR = a real parameter which ntrols the rate of convergence.
\fVabstol\fR = absolute tolerance.
\fVreltol\fR = relative tolerance (has a special meaning when negative).
\fVtv\fR target value, only referenced if \fVreltol < 0\fR.
\fViters\fR = on entry: maximum number of iterations >= 0, on exit:
the number of iterations taken.
.LP
\fVinfo\fR returns 1 if maxiters exceeded, 2 if absolute accuracy
is reached, 3 if relative accuracy is reached, 4 if target value is
reached, 5 if target value is not achievable; negative values
indicate errors.
.LP
Convergence criterion:
.nf
(1) maxiters is exceeded
(2) duality gap is less than abstol
(3) primal and dual objective are both positive and
duality gap is less than (reltol * dual objective)
or primal and dual objective are both negative and
duality gap is less than (reltol * minus the primal objective)
(4) reltol is negative and
primal objective is less than tv or dual objective is greater
than tv
.fi
.SH EXAMPLE
.nf
F0=[2,1,0,0;
1,2,0,0;
0,0,3,1
0,0,1,3];
F1=[1,2,0,0;
2,1,0,0;
0,0,1,3;
0,0,3,1]
F2=[2,2,0,0;
2,2,0,0;
0,0,3,4;
0,0,4,4];
blck_szs=[2,2];
F01=F0(1:2,1:2);F02=F0(3:4,3:4);
F11=F1(1:2,1:2);F12=F1(3:4,3:4);
F21=F2(1:2,1:2);F22=F2(3:4,3:4);
x0=[0;0]
Z0=2*F0;
Z01=Z0(1:2,1:2);Z02=Z0(3:4,3:4);
FF=[[F01(:);F02(:)],[F11(:);F12(:)],[F21(:);F22(:)]]
ZZ0=[[Z01(:);Z02(:)]];
c=[trace(F1*Z0);trace(F2*Z0)];
options=[10,1.d-10,1.d-10,0,50];
[x,Z,ul,info]=semidef(x0,pack(ZZ0),pack(FF),blck_szs,c,options)
w=vec2list(unpack(Z,blck_szs),[blck_szs;blck_szs]);Z=sysdiag(w(1),w(2))
c'*x+trace(F0*Z)
spec(F0+F1*x(1)+F2*x(2))
trace(F1*Z)-c(1)
trace(F2*Z)-c(2)
.fi
|
