Page MenuHomec4science
Files F121880428

fmmc.html
No OneTemporary
Actions

File Metadata

Created
Mon, Jul 14, 14:02

fmmc.html
View Options

<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Computes fastest mixing Markov chain (FMMC) edge weights</title>
<link rel="canonical" href="http://cvxr.com/cvx/examples/graph_laplacian/html/fmmc.html">
<link rel="stylesheet" href="../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Computes fastest mixing Markov chain (FMMC) edge weights</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
Text output
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="keyword">function</span> [ w, cvx_optval ] = fmmc(A)
<span class="comment">% [W,S] = FMMC(A) gives a vector of the fastest mixing Markov chain</span>
<span class="comment">% edge weights for a graph described by the incidence matrix A (n x m).</span>
<span class="comment">% Here n is the number of nodes and m is the number of edges in the graph;</span>
<span class="comment">% each column of A has exactly one +1 and one -1.</span>
<span class="comment">%</span>
<span class="comment">% The FMMC edge weights are given the SDP:</span>
<span class="comment">%</span>
<span class="comment">% minimize s</span>
<span class="comment">% subject to -s*I &lt;= I - L - (1/n)11' &lt;= s*I</span>
<span class="comment">% w &gt;= 0, diag(L) &lt;= 1</span>
<span class="comment">%</span>
<span class="comment">% where the variables are edge weights w in R^m and s in R.</span>
<span class="comment">% Here L is the weighted Laplacian defined by L = A*diag(w)*A'.</span>
<span class="comment">% The optimal value is s, and is returned in the second output.</span>
<span class="comment">%</span>
<span class="comment">% For more details see references:</span>
<span class="comment">% "Fastest mixing Markov chain on a graph" by S. Boyd, P. Diaconis, and L. Xiao</span>
<span class="comment">% "Convex Optimization of Graph Laplacian Eigenvalues" by S. Boyd</span>
<span class="comment">%</span>
<span class="comment">% Written for CVX by Almir Mutapcic 08/29/06</span>
[n,m] = size(A);
I = eye(n,n);
J = I - (1/n)*ones(n,n);
cvx_begin <span class="string">sdp</span>
variable <span class="string">w(m,1)</span> <span class="comment">% edge weights</span>
variable <span class="string">s</span> <span class="comment">% epigraph variable</span>
variable <span class="string">L(n,n)</span> <span class="string">symmetric</span>
minimize( s )
subject <span class="string">to</span>
L == A * diag(w) * A';
J - L &lt;= +s * I;
J - L &gt;= -s * I;
w &gt;= 0;
diag(L) &lt;= 1;
cvx_end
</pre>
</div>
</body>
</html>

Event Timeline

c4science · Help