Convex Optimization of Graph Laplacian Eigenvalues
Stephen Boyd
Proceedings International Congress of Mathematicians, 3:13111319, 2006.
We consider the problem of choosing the edge weights of an undirected graph
so as to maximize or minimize some function of the eigenvalues of the
associated Laplacian matrix, subject to some constraints on the weights,
such as nonnegativity, or a given total value. In many interesting cases
this problem is convex, i.e., it involves minimizing a convex function
(or maximizing a concave function) over a convex set. This allows us to
give simple necessary and sufficient optimality conditions, derive
interesting dual problems, find analytical solutions in some cases, and
efficiently compute numerical solutions in all cases.
In this overview we briefly describe some more specific cases of this
general problem, which have been addressed in a series of recent papers.
Fastest mixing Markov chain.
Find edge transition probabilities that give the fastest mixing
(symmetric, discretetime) Markov chain on the graph.
Fastest mixing Markov process.
Find the edge transition rates that give the
fastest mixing (symmetric, continuoustime) Markov process on the graph
Absolute algebraic connectivity. Find edge weights that maximize
the algebraic connectivity of the graph (i.e., the smallest positive
eigenvalue of its Laplacian matrix). The optimal value is called the
absolute algebraic connectivity by Fielder.
Minimum total effective resistance. Find edge weights that minimize
the total effective resistance of the graph. This is same as minimizing
the average commute time from any node to any other, in the associated
Markov chain.
Fastest linear averaging.
Find weights in a distributed averaging network
that yield fastest convergence.
Least steadystate meansquare deviation. Find weights in a
distributed averaging network, driven by random noise,
that minimizes the steadystate
meansquare deviation of the node values.
