0
$\begingroup$

Let W be a graph Laplacian (symmetric diagonally dominant, and thus PSD), and X the matrix variable.

Let $<A,B>=Tr(A^TB)$.

$$\text{Maximize}\;\; \displaystyle\sum_{i,j} w_{ij}(x^{(i)}\cdot x^{(j)})$$ $$\text{Subject to}\;\; x^{(i)}\cdot x^{(i)}=1$$

I want to write this in standard semidefinite programming form. The best I've been able to do is

$$\text{Maximize}\;\; <W, X^TX>$$ $$\text{Subject to}\;\; <A_i, X^TX>=1$$

where $A_i$ is a matrix of zeros except for a $1$ at the $i^{th}$ slot on its diagonal, and where $X^TX$ is automatically PSD. If I replace $X^TX$ with $S$ in the above SDP and require that it be PSD, then I can clearly optimize with $S$ as my variable, but there may be no $X^{*}$ which corresponds to $S^{*}$, and if there is, it's not clear how I would recover it.

Also, I'm curious what about the Laplacian ensures the convexity of $\sum_{i,j} w_{ij}(x^{(i)}\cdot x^{(j)})$, is it just the fact that it's PSD, or does it need to be diagonally dominant?

$\endgroup$
2
$\begingroup$

A common definition of "positive semidefinite" is:

A real symmetric $n$ by $n$ matrix $S$ is positive semidefinite if and only if

$z^{T}Sz \geq 0$ for all $z \in R^{n}$.

Another equivalent definition is that a real symmetric $n$ by $n$ matrix $S$ is positive semidefinite if and only if all of its eigenvalues are non-negative. I won't go through the proof that these two definitions are equivalent (it's in lots of textbooks.)

A third equivalent definition that is not quite so well known is:

A real symmetric $n$ by $n$ matrix $S$ is positive semidefinite if and only if there is a real $n$ by $n$ matrix $X$ such that

$S=X^{T}X$.

To show that that this last definition is equivalent,

If $S$ is positive semidefinite, then we diagonalize $S$ as

$S=U \Lambda U^{T}$

where $U$ is orthogonal and $\Lambda$ is diagonal with non-negative elements on the diagonal. By taking the square roots of these non-negative diagonal elements, we can construct a diagonal matrix square root of $\Lambda$, $\Lambda^{1/2}$. We can then write $S$ as

$S=U \Lambda^{1/2} U^{T} U \Lambda^{1/2} U^{T}$.

Let $X=U \Lambda^{1/2} U^{T}$. Note that $X$ is symmetric. Thus

$S=XX=X^{T}X$.

Computationally, we can get the matrix square root $X$ from $S$ by computing the eigenvalue decomposition of $S$. In MATLAB, there's a sqrtm() function that does the work for you.

Conversely, suppose that $S$ is a real and symmetric $n$ by $n$ matrix with

$S=X^{T}X$.

Then for any $z \in R^{n}$,

$z^{T}Sz=z^{T}X^{T}Xz=\| Xz \|_{2}^{2} \geq 0$.

Thus $S$ is positive semidefinite.

To answer your last question,

$<W, S>$

is linear in the elements of $S$ and is thus a convex (and concave) function of $S$.

$\endgroup$
  • $\begingroup$ One issue is that the factorization $S=X^TX$ isn't unique, for instance the Cholesky factorization would be an alternative, how do I choose which factorization to use? $\endgroup$ – Thoth May 17 '15 at 20:29
  • 1
    $\begingroup$ Solutions to your original problem aren't unique either- any orthogonal transformation of the vectors $x^{(i)}$ results in another optimal solution. In practice the optimal objective value is used as a bound on the optimal value of the MAX-CUT problem and the optimal solution $S$ is used in a randomized algorithm to get cuts with expected value within a percentage of optimality. $\endgroup$ – Brian Borchers May 17 '15 at 22:03

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.