1 | function varargout = dissect(X); |
---|
2 | % DISSECT Dissect SDP constraint |
---|
3 | % |
---|
4 | % G = unblkdiag(F) Converts SDP to several smaller SDPs with more variables |
---|
5 | % |
---|
6 | % See also UNBLKDIAG |
---|
7 | |
---|
8 | % Author Johan Löfberg |
---|
9 | % $Id: dissect.m,v 1.7 2006/05/10 10:07:02 joloef Exp $ |
---|
10 | |
---|
11 | |
---|
12 | switch class(X) |
---|
13 | case 'sdpvar' |
---|
14 | % Get sparsity pattern |
---|
15 | Z=spy(X); |
---|
16 | |
---|
17 | % Partition as |
---|
18 | % [A1 0 C1 |
---|
19 | % 0 A2 C2 |
---|
20 | % C1' C2' E] |
---|
21 | |
---|
22 | % Find a dissection |
---|
23 | try |
---|
24 | sep = metismex('NodeBisect',Z); |
---|
25 | catch |
---|
26 | error('You have to install the MATLAB interface to METIS, http://www.cerfacs.fr/algor/Softs/MESHPART/'); |
---|
27 | end |
---|
28 | |
---|
29 | % Indicies for elements in Ai |
---|
30 | s = setdiff(1:length(Z),sep); |
---|
31 | |
---|
32 | % re-order Ais to get diagonal blocks |
---|
33 | Z = Z(s,s); |
---|
34 | AB = X(s,s); |
---|
35 | CD = X(s,sep); |
---|
36 | [v,dummy,r,dummy2]=dmperm(Z); |
---|
37 | |
---|
38 | for i = 1:length(r)-1 |
---|
39 | A{i} = AB(v(r(i):r(i+1)-1),v(r(i):r(i+1)-1)); |
---|
40 | C{i}= CD(v(r(i):r(i+1)-1),:); |
---|
41 | end |
---|
42 | E = X(sep,sep); |
---|
43 | varargout{1} = A; |
---|
44 | varargout{2} = C; |
---|
45 | varargout{3} = E; |
---|
46 | |
---|
47 | case 'lmi' |
---|
48 | Fnew=set([]); |
---|
49 | % decompose trivial block diagonal stuff |
---|
50 | X = unblkdiag(X); |
---|
51 | for i = 1:length(X) |
---|
52 | if is(X(i),'sdp') & length(sdpvar(X(i))) |
---|
53 | if 0 |
---|
54 | [A,B,C,D,E]=dissect(sdpvar(X(i))); |
---|
55 | if ~isempty(B) |
---|
56 | S=sdpvar(size(E,1)); |
---|
57 | S = S.*inversesparsity(E,D,B); |
---|
58 | Fnew=Fnew+set([A C;C' S])+set([E-S D';D B]); |
---|
59 | else |
---|
60 | Fnew = Fnew + X(i); |
---|
61 | end |
---|
62 | |
---|
63 | else |
---|
64 | [A,C,E]=dissect(sdpvar(X(i))); |
---|
65 | if length(A)>1 |
---|
66 | allS = 0; |
---|
67 | for i = 1:length(A)-1 |
---|
68 | S{i}=sdpvar(size(E,1)); |
---|
69 | S{i} = S{i}.*inversesparsity(E,C{i},A{i}); |
---|
70 | allS = allS + S{i}; |
---|
71 | Fnew=Fnew+set([A{i} C{i};C{i}' S{i}]); |
---|
72 | end |
---|
73 | i = i + 1; |
---|
74 | S{i}=E-allS; |
---|
75 | S{i} = S{i}.*inversesparsity(E,C{i},A{i}); |
---|
76 | Fnew=Fnew+set([A{i} C{i};C{i}' S{i}]); |
---|
77 | else |
---|
78 | Fnew = Fnew + X(i); |
---|
79 | end |
---|
80 | |
---|
81 | end |
---|
82 | |
---|
83 | else |
---|
84 | Fnew=Fnew+X(i); |
---|
85 | end |
---|
86 | end |
---|
87 | varargout{1} = Fnew; |
---|
88 | end |
---|
89 | |
---|
90 | |
---|
91 | function S = inversesparsity(E,D,B) |
---|
92 | |
---|
93 | if isa(E,'sdpvar') |
---|
94 | E = spy(E).*randn(size(E)); |
---|
95 | else |
---|
96 | E = E.*randn(size(E)); |
---|
97 | end |
---|
98 | if isa(D,'sdpvar') |
---|
99 | D = spy(D).*randn(size(D)); |
---|
100 | else |
---|
101 | D = D.*randn(size(D)); |
---|
102 | end |
---|
103 | if isa(B,'sdpvar') |
---|
104 | B = spy(B).*randn(size(B)); |
---|
105 | else |
---|
106 | B = B.*randn(size(B)); |
---|
107 | end |
---|
108 | S = E-D'*inv(B)*D; |
---|
109 | S = S | S'; |
---|
110 | |
---|
111 | |
---|