dissect
dissect can be used to transform extremely large sparse and structured SDP constraints to a set of smaller SDP constraints, at the price of introducing more variables.
Syntax
F = dissect(X)
Examples
NOTE : For the examples below to work, you need to have (http://www.cerfacs.fr/algor/Softs/MESHPART/MESHPART) installed.
Let us begin by defining a large but low bandwidth SDP constraint.
n = 500;
r = 3;
B = randn(n,r+1);
S = spdiags(B,0:r,n,n);S = S+S';
x = sdpvar(n,1);
X = diag(x)-S;
p = randperm(n);
X = X(p,p);
F = X >= 0
spy(F)
+++++++++++++++++++++++++++++++++++++++++++++++++++++
| ID| Constraint| Type|
+++++++++++++++++++++++++++++++++++++++++++++++++++++
| #1| Numeric value| Matrix inequality 500x500|
+++++++++++++++++++++++++++++++++++++++++++++++++++++
Applying the dissect command simplifies the constraint to a set of two smaller SDP constraints, at the price of introducing 6 additional variables.
length(getvariables(dissect(F)))
ans =
506
dissect(F)
+++++++++++++++++++++++++++++++++++++++++++++++++++++
| ID| Constraint| Type|
+++++++++++++++++++++++++++++++++++++++++++++++++++++
| #1| Numeric value| Matrix inequality 252x252|
| #2| Numeric value| Matrix inequality 251x251|
+++++++++++++++++++++++++++++++++++++++++++++++++++++
length(getvariables(dissect(F)))
ans =
506
The procedure can be recursively applied.
dissect(dissect(F))
+++++++++++++++++++++++++++++++++++++++++++++++++++++
| ID| Constraint| Type|
+++++++++++++++++++++++++++++++++++++++++++++++++++++
| #1| Numeric value| Matrix inequality 128x128|
| #2| Numeric value| Matrix inequality 127x127|
| #3| Numeric value| Matrix inequality 127x127|
| #4| Numeric value| Matrix inequality 127x127|
+++++++++++++++++++++++++++++++++++++++++++++++++++++
length(getvariables(dissect((dissect(F)))))
ans =
518
To see the impact of the dissection, let us solve an SDP problem for various levels of dissection
sol = optimize(F,trace(X));sol.solvertime
ans =
123.2810
F = dissect(F);
sol = optimize(F,trace(X));sol.solvertime
ans =
36.0940
F = dissect(F);
sol = optimize(F,trace(X));sol.solvertime
ans =
11.9070
F = dissect(F);
sol = optimize(F,trace(X));sol.solvertime
ans =
4.6410
F = dissect(F);
sol = optimize(F,trace(X));sol.solvertime
ans =
3.8430
F = dissect(F);
sol = optimize(F,trace(X));sol.solvertime
ans =
3.9370
Note that the dissection command can be applied to arbitrary SDP problems in YALMIP (nonlinear problems, mixed semidefinite and second order cone problems etc).
The algorithm in the command is based on finding a vertex separator of the matrix in the SDP constraint, applying a Dulmage-Mendelsohn permutation to detect corresponding blocks, followed by a series of Schur completions.
