FDLA and FMMC solutions for a 50-node, 200-edge graph
n = 50; threshold = 0.2529;
rand('state',209);
xy = rand(n,2);
angle = 10*pi/180;
Rotate = [ cos(angle) sin(angle); -sin(angle) cos(angle) ];
xy = (Rotate*xy')';
Dist = zeros(n,n);
for i=1:(n-1);
for j=i+1:n;
Dist(i,j) = norm( xy(i,:) - xy(j,:) );
end;
end;
Dist = Dist + Dist';
Ad = Dist < threshold;
Ad = Ad - eye(n);
m = sum(sum(Ad))/2;
A = zeros(n,m);
l = 0;
for i=1:(n-1);
for j=i+1:n;
if Ad(i,j)>0.5
l = l + 1;
A(i,l) = 1;
A(j,l) = -1;
end;
end;
end;
A = sparse(A);
[n,m] = size(A);
[ w_fdla, rho_fdla ] = fdla(A);
[ w_fmmc, rho_fmmc ] = fmmc(A);
[ w_md, rho_md ] = max_deg(A);
[ w_bc, rho_bc ] = best_const(A);
[ w_mh, rho_mh ] = mh(A);
tau_fdla = 1/log(1/rho_fdla);
tau_fmmc = 1/log(1/rho_fmmc);
tau_md = 1/log(1/rho_md);
tau_bc = 1/log(1/rho_bc);
tau_mh = 1/log(1/rho_mh);
eig_opt = sort(eig(eye(n) - A * diag(w_fdla) * A'));
eig_fmmc = sort(eig(eye(n) - A * diag(w_fmmc) * A'));
eig_mh = sort(eig(eye(n) - A * diag(w_mh) * A'));
eig_md = sort(eig(eye(n) - A * diag(w_md) * A'));
eig_bc = sort(eig(eye(n) - A * diag(w_bc) * A'));
fprintf(1,'\nResults:\n');
fprintf(1,'FDLA weights:\t\t rho = %5.4f \t tau = %5.4f\n',rho_fdla,tau_fdla);
fprintf(1,'FMMC weights:\t\t rho = %5.4f \t tau = %5.4f\n',rho_fmmc,tau_fmmc);
fprintf(1,'M-H weights:\t\t rho = %5.4f \t tau = %5.4f\n',rho_mh,tau_mh);
fprintf(1,'MAX_DEG weights:\t rho = %5.4f \t tau = %5.4f\n',rho_md,tau_md);
fprintf(1,'BEST_CONST weights:\t rho = %5.4f \t tau = %5.4f\n',rho_bc,tau_bc);
figure(1), clf
gplot(Ad,xy);
hold on;
plot(xy(:,1), xy(:,2), 'ko','LineWidth',4, 'MarkerSize',4);
axis([0.05 1.1 -0.1 0.95]);
title('Graph')
hold off;
figure(2), clf
v_fdla = [w_fdla; diag(eye(n) - A*diag(w_fdla)*A')];
[ifdla, jfdla, neg_fdla] = find( v_fdla.*(v_fdla < -0.001 ) );
v_fdla(ifdla) = [];
wbins = [-0.6:0.012:0.6];
hist(neg_fdla,wbins); hold on,
h = findobj(gca,'Type','patch');
set(h,'FaceColor','r')
hist(v_fdla,wbins); hold off,
axis([-0.6 0.6 0 12]);
xlabel('optimal FDLA weights');
ylabel('histogram');
figure(3), clf
xbins = (-1:0.015:1)';
ymax = 6;
subplot(3,1,1)
hist(eig_md, xbins); hold on;
max_md = max(abs(eig_md(1:n-1)));
plot([-max_md -max_md],[0 ymax], 'b--');
plot([ max_md max_md],[0 ymax], 'b--');
axis([-1 1 0 ymax]);
text(0,5,'MAX DEG');
title('Eigenvalue distributions')
subplot(3,1,2)
hist(eig_bc, xbins); hold on;
max_opt = max(abs(eig_bc(1:n-1)));
plot([-max_opt -max_opt],[0 ymax], 'b--');
plot([ max_opt max_opt],[0 ymax], 'b--');
axis([-1 1 0 ymax]);
text(0,5,'BEST CONST');
subplot(3,1,3)
hist(eig_opt, xbins); hold on;
max_opt = max(abs(eig_opt(1:n-1)));
plot([-max_opt -max_opt],[0 ymax], 'b--');
plot([ max_opt max_opt],[0 ymax], 'b--');
axis([-1 1 0 ymax]);
text(0,5,'FDLA');
figure(4), clf
xbins = (-1:0.015:1)';
ymax = 6;
subplot(3,1,1)
hist(eig_md, xbins); hold on;
max_md = max(abs(eig_md(1:n-1)));
plot([-max_md -max_md],[0 ymax], 'b--');
plot([ max_md max_md],[0 ymax], 'b--');
axis([-1 1 0 ymax]);
text(0,5,'MAX DEG');
title('Eigenvalue distributions')
subplot(3,1,2)
hist(eig_mh, xbins); hold on;
max_opt = max(abs(eig_mh(1:n-1)));
plot([-max_opt -max_opt],[0 ymax], 'b--');
plot([ max_opt max_opt],[0 ymax], 'b--');
axis([-1 1 0 ymax]);
text(0,5,'MH');
subplot(3,1,3)
hist(eig_fmmc, xbins); hold on;
max_opt = max(abs(eig_fmmc(1:n-1)));
plot([-max_opt -max_opt],[0 ymax], 'b--');
plot([ max_opt max_opt],[0 ymax], 'b--');
axis([-1 1 0 ymax]);
text(0,5,'FMMC');
figure(5), clf
v_fmmc = [w_fmmc; diag(eye(n) - A*diag(w_fmmc)*A')];
[ifmmc, jfmmc, nonzero_fmmc] = find( v_fmmc.*(v_fmmc > 0.001 ) );
hist(nonzero_fmmc,80);
axis([0 1 0 10]);
xlabel('optimal positive FMMC weights');
ylabel('histogram');
figure(6), clf
An = abs(A*diag(w_fmmc)*A');
An = (An - diag(diag(An))) > 0.0001;
gplot(An,xy,'b-'); hold on;
h = findobj(gca,'Type','line');
set(h,'LineWidth',2.5)
gplot(Ad,xy,'b:');
plot(xy(:,1), xy(:,2), 'ko','LineWidth',4, 'MarkerSize',4);
axis([0.05 1.1 -0.1 0.95]);
title('Subgraph with positive transition prob.')
hold off;
Calling sedumi: 2598 variables, 249 equality constraints
For improved efficiency, sedumi is solving the dual problem.
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 249, order n = 103, dim = 5050, blocks = 4
nnz(A) = 1050 + 0, nnz(ADA) = 62001, nnz(L) = 31125
it : b*y gap delta rate t/tP* t/tD* feas cg cg prec
0 : 1.04E+02 0.000
1 : -2.80E+00 9.57E+00 0.000 0.0920 0.9900 0.9900 -0.10 1 1 2.9E+01
2 : -1.19E+00 3.82E+00 0.000 0.3986 0.9000 0.9000 3.00 1 1 4.7E+00
3 : -9.45E-01 1.45E+00 0.000 0.3806 0.9000 0.9000 1.99 1 1 1.4E+00
4 : -9.31E-01 4.26E-01 0.000 0.2933 0.9000 0.9000 1.10 1 1 4.0E-01
5 : -9.09E-01 1.33E-01 0.000 0.3113 0.9000 0.9000 1.06 1 1 1.2E-01
6 : -9.04E-01 4.16E-02 0.000 0.3137 0.9000 0.9000 1.02 1 1 3.8E-02
7 : -9.03E-01 1.21E-02 0.000 0.2918 0.9000 0.9042 1.01 1 1 1.1E-02
8 : -9.02E-01 3.83E-03 0.000 0.3153 0.9000 0.9090 1.00 1 1 3.5E-03
9 : -9.02E-01 1.26E-03 0.000 0.3283 0.9000 0.7466 1.00 1 1 1.2E-03
10 : -9.02E-01 2.76E-04 0.000 0.2193 0.9032 0.9000 1.00 1 1 2.5E-04
11 : -9.02E-01 6.14E-05 0.000 0.2229 0.9023 0.9000 1.00 2 2 5.6E-05
12 : -9.02E-01 1.28E-05 0.000 0.2091 0.9013 0.9000 1.00 2 2 1.2E-05
13 : -9.02E-01 2.94E-06 0.000 0.2292 0.9040 0.9000 1.00 32 32 2.7E-06
14 : -9.02E-01 7.08E-07 0.000 0.2407 0.9000 0.9010 0.99 86 99 6.4E-07
Run into numerical problems.
iter seconds digits c*x b*y
14 2.0 7.8 -9.0207869906e-01 -9.0207871337e-01
|Ax-b| = 6.2e-07, [Ay-c]_+ = 1.2E-08, |x|= 1.7e+00, |y|= 7.1e+00
Detailed timing (sec)
Pre IPM Post
2.000E-02 1.980E+00 0.000E+00
Max-norms: ||b||=1, ||c|| = 9.800000e-01,
Cholesky |add|=0, |skip| = 48, ||L.L|| = 17005.7.
------------------------------------------------------------
Status: Inaccurate/Solved
Optimal value (cvx_optval): +0.902079
Calling sedumi: 2849 variables, 250 equality constraints
For improved efficiency, sedumi is solving the dual problem.
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 250, order n = 353, dim = 5301, blocks = 4
nnz(A) = 1349 + 0, nnz(ADA) = 62500, nnz(L) = 31375
it : b*y gap delta rate t/tP* t/tD* feas cg cg prec
0 : 7.13E+01 0.000
1 : -3.02E-01 4.70E+01 0.000 0.6583 0.9000 0.9000 5.58 1 1 7.2E+01
2 : -7.31E-01 2.26E+01 0.000 0.4804 0.9000 0.9000 1.51 1 1 3.3E+01
3 : -9.21E-01 6.86E+00 0.000 0.3040 0.9000 0.9000 1.79 1 1 6.8E+00
4 : -9.51E-01 1.44E+00 0.000 0.2106 0.9000 0.9000 1.45 1 1 1.2E+00
5 : -9.39E-01 3.68E-01 0.000 0.2547 0.9000 0.9000 1.12 1 1 2.9E-01
6 : -9.29E-01 1.81E-01 0.000 0.4927 0.9000 0.9000 1.05 1 1 1.4E-01
7 : -9.24E-01 9.93E-02 0.000 0.5475 0.9000 0.9000 1.04 1 1 7.5E-02
8 : -9.21E-01 5.38E-02 0.000 0.5419 0.9056 0.9000 1.03 1 1 4.0E-02
9 : -9.18E-01 3.59E-02 0.233 0.6668 0.9000 0.9499 1.02 1 1 2.7E-02
10 : -9.18E-01 2.47E-02 0.000 0.6884 0.9000 0.5393 1.01 1 1 1.9E-02
11 : -9.17E-01 1.23E-02 0.000 0.4966 0.9000 0.7809 1.01 1 1 9.3E-03
12 : -9.16E-01 5.50E-03 0.000 0.4490 0.9000 0.9000 1.01 1 1 4.2E-03
13 : -9.16E-01 2.82E-03 0.000 0.5118 0.9000 0.9000 1.01 1 1 2.1E-03
14 : -9.15E-01 1.04E-03 0.000 0.3689 0.9068 0.9000 1.00 1 1 7.7E-04
15 : -9.15E-01 4.67E-04 0.000 0.4493 0.9000 0.8589 1.00 1 1 3.5E-04
16 : -9.15E-01 1.51E-04 0.000 0.3236 0.9036 0.9000 1.00 1 1 1.1E-04
17 : -9.15E-01 5.02E-05 0.000 0.3324 0.9000 0.8411 1.00 1 1 3.8E-05
18 : -9.15E-01 1.06E-05 0.000 0.2112 0.9044 0.9000 1.00 2 2 7.8E-06
19 : -9.15E-01 7.61E-07 0.000 0.0717 0.9900 0.9879 1.00 11 11 5.7E-07
20 : -9.15E-01 4.95E-08 0.471 0.0651 0.9904 0.9900 0.99 16 17 3.4E-08
21 : -9.15E-01 1.78E-08 0.000 0.3596 0.9000 0.7795 1.00 94 99 1.3E-08
iter seconds digits c*x b*y
21 2.0 Inf -9.1515153957e-01 -9.1515153955e-01
|Ax-b| = 1.3e-08, [Ay-c]_+ = 8.5E-11, |x|= 1.3e+00, |y|= 7.0e+00
Detailed timing (sec)
Pre IPM Post
3.000E-02 2.040E+00 1.000E-02
Max-norms: ||b||=1, ||c|| = 9.800000e-01,
Cholesky |add|=0, |skip| = 27, ||L.L|| = 3556.84.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.915152
Results:
FDLA weights: rho = 0.9021 tau = 9.7037
FMMC weights: rho = 0.9152 tau = 11.2783
M-H weights: rho = 0.9489 tau = 19.0839
MAX_DEG weights: rho = 0.9706 tau = 33.5236
BEST_CONST weights: rho = 0.9470 tau = 18.3549