FDLA and FMMC solutions for an 8-node, 13-edge graph
A = [ 1 0 0 1 0 0 0 0 0 0 0 0 0;
-1 1 0 0 1 1 0 0 0 0 0 0 1;
0 -1 1 0 0 0 0 0 -1 0 0 0 0;
0 0 -1 0 0 -1 0 0 0 -1 0 0 0;
0 0 0 -1 0 0 -1 1 0 0 0 0 0;
0 0 0 0 0 0 1 0 0 0 1 0 0;
0 0 0 0 0 0 0 -1 1 0 -1 1 -1;
0 0 0 0 -1 0 0 0 0 1 0 -1 0];
xy = [ 1 2 3 3 1 1 2 3 ; ...
3 2.5 3 2 2 1 1.5 1 ]';
[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);
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
plotgraph(A,xy,w_fdla);
text(0.55,1.05,'FDLA optimal weights')
figure(2), clf
plotgraph(A,xy,w_fmmc);
text(0.55,1.05,'FMMC optimal weights')
figure(3), clf
plotgraph(A,xy,w_md);
text(0.5,1.05,'Max degree optimal weights')
figure(4), clf
plotgraph(A,xy,w_bc);
text(0.5,1.05,'Best constant optimal weights')
figure(5), clf
plotgraph(A,xy,w_mh);
text(0.46,1.05,'Metropolis-Hastings optimal weights')
Calling SDPT3: 75 variables, 17 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------
num. of constraints = 17
dim. of sdp var = 16, num. of sdp blk = 2
dim. of free var = 3 *** convert ublk to lblk
*******************************************************************
SDPT3: Infeasible path-following algorithms
*******************************************************************
version predcorr gam expon scale_data
HKM 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap mean(obj) cputime
-------------------------------------------------------------------
0|0.000|0.000|3.4e+01|6.0e+00|6.0e+02|-2.065595e+00| 0:0:00| chol 1 1
1|0.964|0.979|1.2e+00|2.2e-01|1.7e+01|-2.106087e+00| 0:0:00| chol 1 1
2|1.000|1.000|3.6e-06|1.0e-02|2.2e+00|-1.129974e+00| 0:0:00| chol 1 1
3|1.000|0.549|5.9e-06|5.1e-03|1.1e+00|-7.280170e-01| 0:0:00| chol 1 1
4|1.000|0.180|8.3e-06|4.9e-03|7.9e-01|-7.975754e-01| 0:0:00| chol 1 1
5|1.000|0.718|1.7e-07|1.4e-03|2.4e-01|-6.770093e-01| 0:0:00| chol 1 1
6|0.905|0.781|5.0e-08|3.0e-04|4.6e-02|-6.531766e-01| 0:0:00| chol 1 1
7|1.000|0.325|7.0e-09|2.1e-04|2.5e-02|-6.533737e-01| 0:0:00| chol 1 1
8|1.000|0.654|4.1e-09|7.1e-05|8.3e-03|-6.470579e-01| 0:0:00| chol 1 1
9|0.980|0.919|5.9e-10|5.7e-06|6.6e-04|-6.436398e-01| 0:0:00| chol 1 1
10|0.965|0.853|1.0e-10|8.2e-06|1.0e-04|-6.433776e-01| 0:0:00| chol 1 1
11|1.000|0.964|2.0e-12|1.2e-06|4.4e-06|-6.433330e-01| 0:0:00| chol 1 1
12|1.000|0.983|2.4e-13|5.5e-08|1.4e-07|-6.433314e-01| 0:0:00| chol 1 1
13|1.000|0.987|3.7e-14|1.8e-09|3.7e-09|-6.433314e-01| 0:0:00|
stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
number of iterations = 13
primal objective value = -6.43331401e-01
dual objective value = -6.43331404e-01
gap := trace(XZ) = 3.70e-09
relative gap = 1.62e-09
actual relative gap = 1.19e-09
rel. primal infeas = 3.67e-14
rel. dual infeas = 1.77e-09
norm(X), norm(y), norm(Z) = 8.3e-01, 2.1e+00, 3.2e+00
norm(A), norm(b), norm(C) = 1.3e+01, 2.0e+00, 4.5e+00
Total CPU time (secs) = 0.4
CPU time per iteration = 0.0
termination code = 0
DIMACS: 3.7e-14 0.0e+00 4.3e-09 0.0e+00 1.2e-09 1.6e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.643331
Calling SDPT3: 99 variables, 20 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------
num. of constraints = 20
dim. of sdp var = 16, num. of sdp blk = 2
dim. of linear var = 21
dim. of free var = 6 *** convert ublk to lblk
*******************************************************************
SDPT3: Infeasible path-following algorithms
*******************************************************************
version predcorr gam expon scale_data
HKM 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap mean(obj) cputime
-------------------------------------------------------------------
0|0.000|0.000|3.7e+01|1.1e+01|5.6e+03| 9.165151e+00| 0:0:00| chol 1 1
1|0.791|0.933|7.8e+00|8.3e-01|2.8e+02| 1.577577e+01| 0:0:00| chol 1 1
2|1.000|0.944|3.3e-06|5.5e-02|2.8e+01| 7.434088e+00| 0:0:00| chol 1 1
3|0.958|0.615|1.1e-06|2.2e-02|5.3e+00|-5.406302e-01| 0:0:00| chol 1 1
4|0.903|0.812|8.4e-07|4.1e-03|1.1e+00|-3.976032e-01| 0:0:00| chol 1 1
5|0.411|0.267|5.0e-07|3.0e-03|8.3e-01|-5.638855e-01| 0:0:00| chol 1 1
6|0.906|0.236|6.8e-08|2.3e-03|4.8e-01|-6.795009e-01| 0:0:00| chol 1 1
7|1.000|0.436|2.5e-08|1.3e-03|2.6e-01|-6.886207e-01| 0:0:00| chol 1 1
8|1.000|0.537|4.2e-09|6.0e-04|9.6e-02|-6.949475e-01| 0:0:00| chol 1 1
9|1.000|0.770|1.1e-09|1.4e-04|1.9e-02|-6.850979e-01| 0:0:00| chol 1 1
10|1.000|0.448|4.1e-10|7.7e-05|8.9e-03|-6.840757e-01| 0:0:00| chol 1 1
11|1.000|0.826|3.6e-10|1.3e-05|1.6e-03|-6.815158e-01| 0:0:00| chol 1 1
12|0.979|0.978|3.6e-11|1.0e-05|4.9e-05|-6.809727e-01| 0:0:00| chol 1 1
13|0.959|0.978|1.7e-12|3.2e-07|1.3e-06|-6.809609e-01| 0:0:00| chol 1 1
14|1.000|0.968|5.0e-14|8.5e-09|8.1e-08|-6.809607e-01| 0:0:00| chol 1 1
15|1.000|0.984|2.0e-13|5.3e-10|3.4e-09|-6.809607e-01| 0:0:01|
stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
number of iterations = 15
primal objective value = -6.80960674e-01
dual objective value = -6.80960676e-01
gap := trace(XZ) = 3.44e-09
relative gap = 1.46e-09
actual relative gap = 1.15e-09
rel. primal infeas = 2.03e-13
rel. dual infeas = 5.33e-10
norm(X), norm(y), norm(Z) = 1.1e+00, 1.7e+00, 3.6e+00
norm(A), norm(b), norm(C) = 1.4e+01, 2.0e+00, 5.4e+00
Total CPU time (secs) = 0.5
CPU time per iteration = 0.0
termination code = 0
DIMACS: 2.0e-13 0.0e+00 1.4e-09 0.0e+00 1.1e-09 1.5e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.680961
Results:
FDLA weights: rho = 0.6433 tau = 2.2671
FMMC weights: rho = 0.6810 tau = 2.6025
M-H weights: rho = 0.7743 tau = 3.9094
MAX_DEG weights: rho = 0.7793 tau = 4.0093
BEST_CONST weights: rho = 0.7119 tau = 2.9422