4
$\begingroup$

On page 5 of Stephen Boyd's Convex Optimization of Graph Laplacian Eigenvalues, a weighted undirected graph has nonnegative weights $w \in \mathbb R^m$ associated to its edges, with $\mathbf{1}^T w = 1$. The problem of finding the weights $w$ such that the smallest positive eigenvalue of the Laplacian is maximized is written as

$$\begin{array}{ll} \text{maximize} & \lambda_2\\ \text{subject to} & \mathbf{1}^T w = 1\\ & w \geq 0\end{array}$$

where $\lambda_2$ is the smallest positive eigenvalue (i.e., the second smallest) of the Laplacian matrix. Note that the smallest eigenvalue of the Laplacian matrix of an undirected graph with nonnegative weights is always 0.

Boyd rewrites the optimization problem above as the following semidefinite program (SDP) in $\gamma, \beta \in \mathbb R$ and $w \in \mathbb R^m$

$$\begin{array}{ll} \text{maximize} & \gamma\\ \text{subject to} & \gamma I \preceq L + \beta \mathbf{11}^T\\ & \mathbf{1}^T w = 1\\ & w \geq 0\end{array}$$

where $L$ is the Laplacian matrix of a weighted graph. He doesn't explain how these two problems are equivalent, and I haven't figured that out yet. Does anyone have any idea about how to derive this SDP?

$\endgroup$
1
$\begingroup$

I think that we can explain this through the spectral decomposition of a matrix.

We have that $L=\lambda_1v_1v_1^T+\lambda_2v_2v_2^T+\ldots+\lambda_mv_mv_m^T$, where $\lambda_i$ and $v_i$ are the $i$-th eigenvalue and eigenvector of $L$, with $||v_i||=1$ and $v_i\perp v_j$. Matrix $L$ is the Laplacian matrix of a weighted undirected graph with nonnegative weights, so $\lambda_i\ge0$, $\lambda_1=0$, and $v_1=\frac{1}{m}\mathbf{1}$ (assuming $\lambda_1\le \lambda_2\le \cdots$). That is, $$L=(0)\frac{1}{m^2}\mathbf{1}\mathbf{1}^T+\lambda_2v_2v_2^T+\ldots+\lambda_mv_mv_m^T$$

Now, using these eigenvectors, we can write the spectral decomposition of $\gamma I$ as $$\gamma I=\gamma\frac{1}{m^2}\mathbf{1}\mathbf{1}^T+\gamma v_2v_2^T+\ldots+\gamma v_m v_m^T$$

The constraint of the SDP problem can be written as $M=L-\gamma I + \beta \mathbf{1}\mathbf{1}^T \succeq 0$. Using the two equations above, this constraint can be written as

$$M=(\beta-\gamma+0)\frac{1}{m^2}\mathbf{1}\mathbf{1}^T+(\lambda_2-\gamma)v_2v_2^T+\ldots+(\lambda_m-\gamma)v_mv_m^T \succeq 0$$ It means that $M$ has the same eigenvectors as $L$, and its eigenvalues are $(\beta-\gamma+0)$ and $\lambda_i-\gamma$, with $i=2,\ldots, m$.

In order to keep $M$ positive semidefinite, the weights that define $L$ have to be such that its eigenvalues are greater or equal than $\gamma$. Since $\gamma$ is being maximized, then the eigenvalues are maximized as well (and therefore, $\lambda_2$ is maximized). $L$'s first eigenvalue (which is $0$) shouldn't affect the optimization process, so $\beta$ is an unconstrained variable that is introduced to take any value that makes $\beta-\gamma\ge0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.