Page Menu
Home
c4science
Search
Configure Global Search
Log In
Files
F121697318
larger_example.html
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Subscribers
None
File Metadata
Details
File Info
Storage
Attached
Created
Sun, Jul 13, 06:18
Size
15 KB
Mime Type
text/html
Expires
Tue, Jul 15, 06:18 (1 d, 23 h)
Engine
blob
Format
Raw Data
Handle
27354185
Attached To
R1252 EMPoWER
larger_example.html
View Options
<!DOCTYPE HTML>
<html>
<head>
<meta
charset=
"UTF-8"
>
<title>
FDLA and FMMC solutions for a 50-node, 200-edge graph
</title>
<link
rel=
"canonical"
href=
"http://cvxr.com/cvx/examples/graph_laplacian/html/larger_example.html"
>
<link
rel=
"stylesheet"
href=
"../../examples.css"
type=
"text/css"
>
</head>
<body>
<div
id=
"header"
>
<h1>
FDLA and FMMC solutions for a 50-node, 200-edge graph
</h1>
Jump to:
<a
href=
"#source"
>
Source code
</a>
<a
href=
"#output"
>
Text output
</a>
<a
href=
"#plots"
>
Plots
</a>
<a
href=
"../../index.html"
>
Library index
</a>
</div>
<div
id=
"content"
>
<a
id=
"source"
></a>
<pre
class=
"codeinput"
>
<span
class=
"comment"
>
% S. Boyd, et. al., "Convex Optimization of Graph Laplacian Eigenvalues"
</span>
<span
class=
"comment"
>
% ICM'06 talk examples (www.stanford.edu/~boyd/cvx_opt_graph_lapl_eigs.html)
</span>
<span
class=
"comment"
>
% Written for CVX by Almir Mutapcic 08/29/06
</span>
<span
class=
"comment"
>
% (figures are generated)
</span>
<span
class=
"comment"
>
%
</span>
<span
class=
"comment"
>
% In this example we consider a graph described by the incidence matrix A.
</span>
<span
class=
"comment"
>
% Each edge has a weight W_i, and we optimize various functions of the
</span>
<span
class=
"comment"
>
% edge weights as described in the referenced paper; in particular,
</span>
<span
class=
"comment"
>
%
</span>
<span
class=
"comment"
>
% - the fastest distributed linear averaging (FDLA) problem (fdla.m)
</span>
<span
class=
"comment"
>
% - the fastest mixing Markov chain (FMMC) problem (fmmc.m)
</span>
<span
class=
"comment"
>
%
</span>
<span
class=
"comment"
>
% Then we compare these solutions to the heuristics listed below:
</span>
<span
class=
"comment"
>
%
</span>
<span
class=
"comment"
>
% - maximum-degree heuristic (max_deg.m)
</span>
<span
class=
"comment"
>
% - constant weights that yield fastest averaging (best_const.m)
</span>
<span
class=
"comment"
>
% - Metropolis-Hastings heuristic (mh.m)
</span>
<span
class=
"comment"
>
% randomly generate a graph with 50 nodes and 200 edges
</span>
<span
class=
"comment"
>
% and make it pretty for plotting
</span>
n = 50; threshold = 0.2529;
rand(
<span
class=
"string"
>
'state'
</span>
,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);
<span
class=
"keyword"
>
for
</span>
i=1:(n-1);
<span
class=
"keyword"
>
for
</span>
j=i+1:n;
Dist(i,j) = norm( xy(i,:) - xy(j,:) );
<span
class=
"keyword"
>
end
</span>
;
<span
class=
"keyword"
>
end
</span>
;
Dist = Dist + Dist';
Ad = Dist
<
threshold;
Ad = Ad - eye(n);
m = sum(sum(Ad))/2;
<span
class=
"comment"
>
% find the incidence matrix
</span>
A = zeros(n,m);
l = 0;
<span
class=
"keyword"
>
for
</span>
i=1:(n-1);
<span
class=
"keyword"
>
for
</span>
j=i+1:n;
<span
class=
"keyword"
>
if
</span>
Ad(i,j)
>
0.5
l = l + 1;
A(i,l) = 1;
A(j,l) = -1;
<span
class=
"keyword"
>
end
</span>
;
<span
class=
"keyword"
>
end
</span>
;
<span
class=
"keyword"
>
end
</span>
;
A = sparse(A);
<span
class=
"comment"
>
% Compute edge weights: some optimal, some based on heuristics
</span>
[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,
<span
class=
"string"
>
'\nResults:\n'
</span>
);
fprintf(1,
<span
class=
"string"
>
'FDLA weights:\t\t rho = %5.4f \t tau = %5.4f\n'
</span>
,rho_fdla,tau_fdla);
fprintf(1,
<span
class=
"string"
>
'FMMC weights:\t\t rho = %5.4f \t tau = %5.4f\n'
</span>
,rho_fmmc,tau_fmmc);
fprintf(1,
<span
class=
"string"
>
'M-H weights:\t\t rho = %5.4f \t tau = %5.4f\n'
</span>
,rho_mh,tau_mh);
fprintf(1,
<span
class=
"string"
>
'MAX_DEG weights:\t rho = %5.4f \t tau = %5.4f\n'
</span>
,rho_md,tau_md);
fprintf(1,
<span
class=
"string"
>
'BEST_CONST weights:\t rho = %5.4f \t tau = %5.4f\n'
</span>
,rho_bc,tau_bc);
<span
class=
"comment"
>
% plot results
</span>
figure(1), clf
gplot(Ad,xy);
hold
<span
class=
"string"
>
on
</span>
;
plot(xy(:,1), xy(:,2),
<span
class=
"string"
>
'ko'
</span>
,
<span
class=
"string"
>
'LineWidth'
</span>
,4,
<span
class=
"string"
>
'MarkerSize'
</span>
,4);
axis([0.05 1.1 -0.1 0.95]);
title(
<span
class=
"string"
>
'Graph'
</span>
)
hold
<span
class=
"string"
>
off
</span>
;
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
<span
class=
"string"
>
on
</span>
,
h = findobj(gca,
<span
class=
"string"
>
'Type'
</span>
,
<span
class=
"string"
>
'patch'
</span>
);
set(h,
<span
class=
"string"
>
'FaceColor'
</span>
,
<span
class=
"string"
>
'r'
</span>
)
hist(v_fdla,wbins); hold
<span
class=
"string"
>
off
</span>
,
axis([-0.6 0.6 0 12]);
xlabel(
<span
class=
"string"
>
'optimal FDLA weights'
</span>
);
ylabel(
<span
class=
"string"
>
'histogram'
</span>
);
figure(3), clf
xbins = (-1:0.015:1)';
ymax = 6;
subplot(3,1,1)
hist(eig_md, xbins); hold
<span
class=
"string"
>
on
</span>
;
max_md = max(abs(eig_md(1:n-1)));
plot([-max_md -max_md],[0 ymax],
<span
class=
"string"
>
'b--'
</span>
);
plot([ max_md max_md],[0 ymax],
<span
class=
"string"
>
'b--'
</span>
);
axis([-1 1 0 ymax]);
text(0,5,
<span
class=
"string"
>
'MAX DEG'
</span>
);
title(
<span
class=
"string"
>
'Eigenvalue distributions'
</span>
)
subplot(3,1,2)
hist(eig_bc, xbins); hold
<span
class=
"string"
>
on
</span>
;
max_opt = max(abs(eig_bc(1:n-1)));
plot([-max_opt -max_opt],[0 ymax],
<span
class=
"string"
>
'b--'
</span>
);
plot([ max_opt max_opt],[0 ymax],
<span
class=
"string"
>
'b--'
</span>
);
axis([-1 1 0 ymax]);
text(0,5,
<span
class=
"string"
>
'BEST CONST'
</span>
);
subplot(3,1,3)
hist(eig_opt, xbins); hold
<span
class=
"string"
>
on
</span>
;
max_opt = max(abs(eig_opt(1:n-1)));
plot([-max_opt -max_opt],[0 ymax],
<span
class=
"string"
>
'b--'
</span>
);
plot([ max_opt max_opt],[0 ymax],
<span
class=
"string"
>
'b--'
</span>
);
axis([-1 1 0 ymax]);
text(0,5,
<span
class=
"string"
>
'FDLA'
</span>
);
figure(4), clf
xbins = (-1:0.015:1)';
ymax = 6;
subplot(3,1,1)
hist(eig_md, xbins); hold
<span
class=
"string"
>
on
</span>
;
max_md = max(abs(eig_md(1:n-1)));
plot([-max_md -max_md],[0 ymax],
<span
class=
"string"
>
'b--'
</span>
);
plot([ max_md max_md],[0 ymax],
<span
class=
"string"
>
'b--'
</span>
);
axis([-1 1 0 ymax]);
text(0,5,
<span
class=
"string"
>
'MAX DEG'
</span>
);
title(
<span
class=
"string"
>
'Eigenvalue distributions'
</span>
)
subplot(3,1,2)
hist(eig_mh, xbins); hold
<span
class=
"string"
>
on
</span>
;
max_opt = max(abs(eig_mh(1:n-1)));
plot([-max_opt -max_opt],[0 ymax],
<span
class=
"string"
>
'b--'
</span>
);
plot([ max_opt max_opt],[0 ymax],
<span
class=
"string"
>
'b--'
</span>
);
axis([-1 1 0 ymax]);
text(0,5,
<span
class=
"string"
>
'MH'
</span>
);
subplot(3,1,3)
hist(eig_fmmc, xbins); hold
<span
class=
"string"
>
on
</span>
;
max_opt = max(abs(eig_fmmc(1:n-1)));
plot([-max_opt -max_opt],[0 ymax],
<span
class=
"string"
>
'b--'
</span>
);
plot([ max_opt max_opt],[0 ymax],
<span
class=
"string"
>
'b--'
</span>
);
axis([-1 1 0 ymax]);
text(0,5,
<span
class=
"string"
>
'FMMC'
</span>
);
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(
<span
class=
"string"
>
'optimal positive FMMC weights'
</span>
);
ylabel(
<span
class=
"string"
>
'histogram'
</span>
);
figure(6), clf
An = abs(A*diag(w_fmmc)*A');
An = (An - diag(diag(An)))
>
0.0001;
gplot(An,xy,
<span
class=
"string"
>
'b-'
</span>
); hold
<span
class=
"string"
>
on
</span>
;
h = findobj(gca,
<span
class=
"string"
>
'Type'
</span>
,
<span
class=
"string"
>
'line'
</span>
);
set(h,
<span
class=
"string"
>
'LineWidth'
</span>
,2.5)
gplot(Ad,xy,
<span
class=
"string"
>
'b:'
</span>
);
plot(xy(:,1), xy(:,2),
<span
class=
"string"
>
'ko'
</span>
,
<span
class=
"string"
>
'LineWidth'
</span>
,4,
<span
class=
"string"
>
'MarkerSize'
</span>
,4);
axis([0.05 1.1 -0.1 0.95]);
title(
<span
class=
"string"
>
'Subgraph with positive transition prob.'
</span>
)
hold
<span
class=
"string"
>
off
</span>
;
</pre>
<a
id=
"output"
></a>
<pre
class=
"codeoutput"
>
Calling SDPT3: 2598 variables, 249 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------
num. of constraints = 249
dim. of sdp var = 100, num. of sdp blk = 2
dim. of free var = 48 *** 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 prim-obj dual-obj cputime
-------------------------------------------------------------------
0|0.000|0.000|1.3e+03|1.1e+02|1.0e+06|-3.054372e+01 0.000000e+00| 0:0:00| chol 1 1
1|0.925|0.974|9.6e+01|3.2e+00|8.5e+03| 1.302102e+01 -1.190896e+01| 0:0:00| chol 1 1
2|0.989|0.993|1.1e+00|4.9e-02|6.1e+01| 1.181474e-01 -1.229355e+01| 0:0:00| chol 1 1
3|1.000|1.000|4.3e-04|3.0e-03|6.7e+00| 6.215167e-03 -6.559567e+00| 0:0:00| chol 2 1
4|1.000|0.845|2.2e-04|8.0e-04|1.1e+00|-2.516558e-02 -1.084935e+00| 0:0:01| chol 1 1
5|0.635|0.437|8.1e-05|5.1e-04|6.3e-01|-5.388222e-01 -1.140827e+00| 0:0:01| chol 1 1
6|0.847|0.366|1.7e-05|3.4e-04|3.1e-01|-7.743386e-01 -1.064714e+00| 0:0:01| chol 1 1
7|0.915|0.609|3.6e-06|1.4e-04|1.0e-01|-8.637981e-01 -9.610145e-01| 0:0:01| chol 1 1
8|1.000|0.284|4.5e-07|9.9e-05|6.3e-02|-8.838014e-01 -9.438500e-01| 0:0:01| chol 1 1
9|1.000|0.430|2.8e-07|5.6e-05|3.3e-02|-8.939475e-01 -9.254959e-01| 0:0:01| chol 1 1
10|1.000|0.414|8.1e-08|3.3e-05|1.8e-02|-8.984543e-01 -9.157209e-01| 0:0:01| chol 2 2
11|1.000|0.379|2.2e-08|5.1e-05|1.1e-02|-9.003200e-01 -9.105304e-01| 0:0:01| chol 1 1
12|1.000|0.915|1.2e-09|3.0e-05|1.7e-03|-9.013297e-01 -9.028095e-01| 0:0:02| chol 2 1
13|1.000|0.898|9.3e-11|4.6e-06|3.5e-04|-9.018416e-01 -9.021701e-01| 0:0:02| chol 2 2
14|0.988|0.933|1.1e-10|9.3e-07|5.7e-05|-9.020349e-01 -9.020887e-01| 0:0:02| chol 2 2
15|1.000|0.961|1.4e-09|1.5e-07|8.8e-06|-9.020714e-01 -9.020798e-01| 0:0:02| chol 3 3
16|1.000|0.962|3.0e-09|2.4e-08|1.5e-06|-9.020774e-01 -9.020788e-01| 0:0:02| chol 5 5
17|1.000|0.963|5.3e-09|4.0e-09|2.4e-07|-9.020785e-01 -9.020787e-01| 0:0:02| chol 9 10
18|1.000|0.969|5.7e-09|7.0e-10|3.1e-08|-9.020786e-01 -9.020787e-01| 0:0:02|
stop: max(relative gap, infeasibilities)
<
1.49e-08
-------------------------------------------------------------------
number of iterations = 18
primal objective value = -9.02078640e-01
dual objective value = -9.02078663e-01
gap := trace(XZ) = 3.08e-08
relative gap = 1.10e-08
actual relative gap = 8.16e-09
rel. primal infeas = 5.72e-09
rel. dual infeas = 6.96e-10
norm(X), norm(y), norm(Z) = 9.6e-01, 7.0e+00, 1.1e+01
norm(A), norm(b), norm(C) = 4.7e+01, 2.0e+00, 9.3e+00
Total CPU time (secs) = 2.46
CPU time per iteration = 0.14
termination code = 0
DIMACS: 5.7e-09 0.0e+00 3.3e-09 0.0e+00 8.2e-09 1.1e-08
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.902079
Calling SDPT3: 2849 variables, 250 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------
num. of constraints = 250
dim. of sdp var = 100, num. of sdp blk = 2
dim. of linear var = 250
dim. of free var = 49 *** 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 prim-obj dual-obj cputime
-------------------------------------------------------------------
0|0.000|0.000|1.3e+03|1.1e+02|2.0e+06| 1.568490e+02 0.000000e+00| 0:0:00| chol 1 1
1|0.764|0.926|3.0e+02|8.0e+00|5.3e+04| 7.806708e+02 -1.228578e+01| 0:0:00| chol 1 1
2|0.901|0.968|3.0e+01|3.2e-01|2.6e+03| 8.418946e+02 -1.205433e+01| 0:0:00| chol 1 1
3|0.909|0.868|2.7e+00|6.3e-02|4.4e+02| 2.796621e+02 -1.295101e+01| 0:0:00| chol 1 1
4|0.995|0.607|1.3e-02|2.6e-02|5.1e+01| 3.057448e+01 -1.225165e+01| 0:0:01| chol 1 1
5|1.000|0.914|1.5e-05|5.0e-03|3.6e+00| 1.699810e+00 -1.702361e+00| 0:0:01| chol 1 1
6|1.000|0.632|5.0e-07|1.9e-03|1.5e+00| 4.796350e-01 -1.001701e+00| 0:0:01| chol 1 1
7|0.297|0.324|3.2e-07|1.3e-03|1.2e+00| 4.287331e-02 -1.160830e+00| 0:0:01| chol 1 1
8|0.925|0.231|3.6e-08|9.6e-04|5.0e-01|-6.307222e-01 -1.117206e+00| 0:0:01| chol 1 1
9|0.988|0.371|1.2e-08|6.1e-04|2.7e-01|-7.857468e-01 -1.048841e+00| 0:0:01| chol 1 1
10|0.691|0.436|6.7e-09|3.4e-04|1.7e-01|-8.292146e-01 -9.936525e-01| 0:0:01| chol 1 1
11|0.842|0.267|1.9e-09|2.5e-04|1.1e-01|-8.664913e-01 -9.741859e-01| 0:0:02| chol 1 1
12|0.770|0.330|8.4e-10|1.7e-04|7.4e-02|-8.836940e-01 -9.561709e-01| 0:0:02| chol 1 1
13|0.865|0.284|2.4e-10|1.2e-04|5.0e-02|-8.960108e-01 -9.454383e-01| 0:0:02| chol 1 1
14|0.922|0.347|8.0e-11|7.8e-05|3.2e-02|-9.043659e-01 -9.357673e-01| 0:0:02| chol 1 1
15|1.000|0.345|2.8e-11|5.6e-05|2.0e-02|-9.095103e-01 -9.291849e-01| 0:0:02| chol 1 1
16|1.000|0.940|2.5e-11|2.3e-05|4.4e-03|-9.126087e-01 -9.167670e-01| 0:0:02| chol 1 1
17|1.000|0.940|2.0e-11|5.0e-06|1.3e-03|-9.142866e-01 -9.156062e-01| 0:0:02| chol 2 2
18|1.000|0.941|3.9e-12|1.6e-06|3.8e-04|-9.149180e-01 -9.152851e-01| 0:0:02| chol 2 2
19|1.000|0.942|5.6e-12|4.3e-07|1.5e-04|-9.150589e-01 -9.152072e-01| 0:0:03| chol 2 2
20|1.000|0.959|2.0e-11|1.7e-07|3.7e-05|-9.151297e-01 -9.151653e-01| 0:0:03| chol 2 2
21|1.000|0.972|3.5e-11|4.2e-08|6.3e-06|-9.151478e-01 -9.151540e-01| 0:0:03| chol 2 2
22|1.000|0.976|3.9e-11|7.3e-09|8.1e-07|-9.151511e-01 -9.151519e-01| 0:0:03| chol 4 3
23|1.000|0.986|4.3e-11|9.4e-10|3.1e-08|-9.151515e-01 -9.151515e-01| 0:0:03|
stop: max(relative gap, infeasibilities)
<
1.49e-08
-------------------------------------------------------------------
number of iterations = 23
primal objective value = -9.15151520e-01
dual objective value = -9.15151550e-01
gap := trace(XZ) = 3.10e-08
relative gap = 1.09e-08
actual relative gap = 1.05e-08
rel. primal infeas = 4.31e-11
rel. dual infeas = 9.37e-10
norm(X), norm(y), norm(Z) = 9.4e-01, 2.8e+00, 1.1e+01
norm(A), norm(b), norm(C) = 4.7e+01, 2.0e+00, 9.6e+00
Total CPU time (secs) = 3.20
CPU time per iteration = 0.14
termination code = 0
DIMACS: 4.3e-11 0.0e+00 4.6e-09 0.0e+00 1.0e-08 1.1e-08
-------------------------------------------------------------------
------------------------------------------------------------
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
</pre>
<a
id=
"plots"
></a>
<div
id=
"plotoutput"
>
<img
src=
"larger_example__01.png"
alt=
""
>
<img
src=
"larger_example__02.png"
alt=
""
>
<img
src=
"larger_example__03.png"
alt=
""
>
<img
src=
"larger_example__04.png"
alt=
""
>
<img
src=
"larger_example__05.png"
alt=
""
>
<img
src=
"larger_example__06.png"
alt=
""
>
</div>
</div>
</body>
</html>
Event Timeline
Log In to Comment