Page MenuHomec4science
Files F121816887

small_example.html
No OneTemporary
Actions

File Metadata

Created
Mon, Jul 14, 03:12

small_example.html
View Options

<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>FDLA and FMMC solutions for an 8-node, 13-edge graph</title>
<link rel="canonical" href="http://cvxr.com/cvx/examples/graph_laplacian/html/small_example.html">
<link rel="stylesheet" href="../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>FDLA and FMMC solutions for an 8-node, 13-edge graph</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#plots">Plots</a>
&nbsp;&nbsp;&nbsp;&nbsp;<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">% small example (incidence matrix A)</span>
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];
<span class="comment">% x and y locations of the graph nodes</span>
xy = [ 1 2 3 3 1 1 2 3 ; <span class="keyword">...</span>
3 2.5 3 2 2 1 1.5 1 ]';
<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);
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
plotgraph(A,xy,w_fdla);
text(0.55,1.05,<span class="string">'FDLA optimal weights'</span>)
figure(2), clf
plotgraph(A,xy,w_fmmc);
text(0.55,1.05,<span class="string">'FMMC optimal weights'</span>)
figure(3), clf
plotgraph(A,xy,w_md);
text(0.5,1.05,<span class="string">'Max degree optimal weights'</span>)
figure(4), clf
plotgraph(A,xy,w_bc);
text(0.5,1.05,<span class="string">'Best constant optimal weights'</span>)
figure(5), clf
plotgraph(A,xy,w_mh);
text(0.46,1.05,<span class="string">'Metropolis-Hastings optimal weights'</span>)
</pre>
<a id="output"></a>
<pre class="codeoutput">
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 prim-obj dual-obj cputime
-------------------------------------------------------------------
0|0.000|0.000|8.0e+01|1.2e+01|1.9e+03|-3.497627e-10 0.000000e+00| 0:0:00| chol 1 1
1|0.972|0.990|2.2e+00|2.2e-01|5.4e+01|-1.843692e-01 -9.715673e+00| 0:0:00| chol 1 1
2|1.000|1.000|1.0e-05|1.0e-02|6.6e+00|-5.104794e-02 -6.614948e+00| 0:0:00| chol 1 1
3|1.000|0.884|3.0e-05|2.0e-03|7.8e-01|-9.619746e-02 -8.750034e-01| 0:0:00| chol 1 1
4|0.537|0.052|1.4e-05|2.3e-03|4.5e-01|-4.520268e-01 -8.823069e-01| 0:0:00| chol 1 1
5|1.000|0.639|2.1e-07|8.2e-04|1.4e-01|-6.041293e-01 -7.417547e-01| 0:0:00| chol 1 1
6|0.968|0.872|1.2e-07|1.1e-04|1.6e-02|-6.397187e-01 -6.555178e-01| 0:0:00| chol 1 1
7|0.975|0.664|1.5e-08|3.6e-05|4.5e-03|-6.430462e-01 -6.474735e-01| 0:0:00| chol 1 1
8|1.000|0.486|4.1e-09|1.8e-05|2.2e-03|-6.432587e-01 -6.454740e-01| 0:0:00| chol 1 1
9|0.997|0.885|8.9e-10|2.1e-06|2.5e-04|-6.433290e-01 -6.435785e-01| 0:0:00| chol 1 1
10|0.968|0.950|2.0e-10|3.7e-06|1.4e-05|-6.433313e-01 -6.433437e-01| 0:0:00| chol 1 1
11|1.000|0.967|1.4e-12|2.1e-07|6.9e-07|-6.433313e-01 -6.433319e-01| 0:0:00| chol 1 1
12|1.000|0.988|3.8e-13|1.0e-08|1.8e-08|-6.433314e-01 -6.433314e-01| 0:0:00|
stop: max(relative gap, infeasibilities) &lt; 1.49e-08
-------------------------------------------------------------------
number of iterations = 12
primal objective value = -6.43331397e-01
dual objective value = -6.43331410e-01
gap := trace(XZ) = 1.75e-08
relative gap = 7.66e-09
actual relative gap = 5.62e-09
rel. primal infeas = 3.81e-13
rel. dual infeas = 1.02e-08
norm(X), norm(y), norm(Z) = 8.3e-01, 1.8e+00, 3.2e+00
norm(A), norm(b), norm(C) = 1.3e+01, 2.0e+00, 3.8e+00
Total CPU time (secs) = 0.26
CPU time per iteration = 0.02
termination code = 0
DIMACS: 3.8e-13 0.0e+00 1.9e-08 0.0e+00 5.6e-09 7.7e-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 prim-obj dual-obj cputime
-------------------------------------------------------------------
0|0.000|0.000|8.2e+01|1.9e+01|7.2e+03| 3.125000e+01 0.000000e+00| 0:0:00| chol 1 1
1|0.873|0.940|1.0e+01|1.2e+00|4.6e+02| 4.388291e+01 -9.677668e+00| 0:0:00| chol 1 1
2|0.984|0.942|1.7e-01|7.9e-02|4.8e+01| 2.886495e+01 -8.898537e+00| 0:0:00| chol 1 1
3|0.981|0.409|3.1e-03|4.7e-02|1.2e+01| 3.565297e+00 -6.727515e+00| 0:0:00| chol 1 1
4|0.924|0.878|2.3e-04|6.5e-03|1.3e+00| 2.602925e-01 -1.038169e+00| 0:0:00| chol 1 1
5|0.412|0.280|1.4e-04|4.7e-03|1.1e+00| 1.753882e-02 -1.022032e+00| 0:0:00| chol 1 1
6|1.000|0.237|4.8e-08|3.6e-03|5.6e-01|-4.336252e-01 -9.646711e-01| 0:0:00| chol 1 1
7|1.000|0.454|4.1e-08|2.0e-03|3.0e-01|-5.415724e-01 -8.356419e-01| 0:0:00| chol 1 1
8|1.000|0.670|8.4e-09|6.5e-04|8.3e-02|-6.489498e-01 -7.298491e-01| 0:0:00| chol 1 1
9|1.000|0.506|1.1e-09|3.2e-04|3.2e-02|-6.742302e-01 -7.051267e-01| 0:0:00| chol 1 1
10|0.917|0.841|7.5e-10|5.1e-05|5.1e-03|-6.797412e-01 -6.847919e-01| 0:0:00| chol 1 1
11|0.953|0.473|8.4e-11|2.7e-05|2.3e-03|-6.807518e-01 -6.829896e-01| 0:0:00| chol 1 1
12|0.985|0.966|7.5e-11|2.1e-05|1.0e-04|-6.809546e-01 -6.810312e-01| 0:0:00| chol 1 1
13|0.955|0.977|3.5e-12|9.1e-07|2.9e-06|-6.809604e-01 -6.809623e-01| 0:0:00| chol 1 1
14|1.000|0.967|3.3e-14|2.6e-08|1.6e-07|-6.809606e-01 -6.809607e-01| 0:0:00| chol 1 1
15|1.000|0.985|1.2e-14|1.5e-09|6.0e-09|-6.809607e-01 -6.809607e-01| 0:0:00|
stop: max(relative gap, infeasibilities) &lt; 1.49e-08
-------------------------------------------------------------------
number of iterations = 15
primal objective value = -6.80960673e-01
dual objective value = -6.80960677e-01
gap := trace(XZ) = 6.05e-09
relative gap = 2.56e-09
actual relative gap = 1.94e-09
rel. primal infeas = 1.24e-14
rel. dual infeas = 1.45e-09
norm(X), norm(y), norm(Z) = 1.1e+00, 1.3e+00, 3.6e+00
norm(A), norm(b), norm(C) = 1.4e+01, 2.0e+00, 3.9e+00
Total CPU time (secs) = 0.37
CPU time per iteration = 0.02
termination code = 0
DIMACS: 1.2e-14 0.0e+00 3.1e-09 0.0e+00 1.9e-09 2.6e-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
</pre>
<a id="plots"></a>
<div id="plotoutput">
<img src="small_example__01.png" alt=""> <img src="small_example__02.png" alt=""> <img src="small_example__03.png" alt=""> <img src="small_example__04.png" alt=""> <img src="small_example__05.png" alt="">
</div>
</div>
</body>
</html>

Event Timeline

c4science · Help