Minimize trace($MX$) with $M$ rank-deficient and $X$ positive semidefinite

I have an optimization problem of the following form:

$$\min_{X\succeq0} \mathrm{trace\;} MX$$

under the linear constraint $\mbox{diag} (X) = \mathrm{Id}$ and the non-convex constraint $\mbox{rank} (X) = 1$. The matrix $M$ is square and rank-deficient.

The convex relaxation of this problem corresponds to dropping the rank-1 constraint, and merely keeping $X$ positive semidefinite.

I tried running a standard SDP solver (Mosek) on this problem but it yields a matrix $X$ which, despite satisfying the linear constraint and being positive semidefinite, is not of rank one. Instead, it is typically of rank $(n - \mathrm{rank\;} M)$ where $n$ is the number of rows of $X$.

Can you explain why I am getting this result?

You removed the rank-one constraint. The optimization will no longer find a rank-one matrix. However, for your problem, you may not need a solver. Let $M$ be a $n\times n$ matrix. Observe that $X\geq 0$ and $rank(X)=1$ implies that $X=xx^T$ for some vector $x\in\mathbb{R}^n$. Then $trace\{MX\}=x^TMx$. Also, $diag(X)=Id$ will imply $x_i^2=1$ where $x=[x_1,\dots,x_n]$. Thus, your optimization problem becomes $$\min_{x\in\mathbb{R}^n}~x^TMx \\s.t.~x_i\in\{-1,1\} \forall i .$$ Let $M$ be symmetric (try convincing yourself that this doesn't lose generality). Then $M$ has a decomposition of form $$M =\sum_{i=1}^{n}\lambda_iv_iv_i^T$$ where $\lambda_1<\dots<\lambda_n$ are eigenvalues and $v_i$ are corresponding eigenvectors. Thus, we have $$x^TMx=\sum_{i=1}^{n}\lambda_i(x^Tv_i)^2$$ Also, note that $\sum_{i}x_i<=n$. Given this, can you try and show that $x = sign(v_1)$. Here $sign(.)$ is +1 or -1 corresponding to positive and negative entries of the argument vector.

Let $\mathrm Q : = \frac 12 \left( \mathrm M + \mathrm M^{\top}\right)$ be the symmetric part of $\mathrm M$. Consider the following binary quadratic program

$$\begin{array}{ll} \text{minimize} & \mathrm x^{\top} \mathrm Q \,\mathrm x\\ \text{subject to} & \mathrm x \in \{\pm 1\}^n\end{array}$$

$$\begin{array}{ll} \text{minimize} & \mathrm x^{\top} \mathrm Q \,\mathrm x\\ \text{subject to} & x_i^2 = 1 \quad \forall i \in [n]\\ & \mathrm x \in \mathbb R^n\end{array}\tag{QCQP}$$

where $[n] := \{1,2,\dots,n\}$. Both optimization problems above are hard (even when $\mathrm Q \succeq \mathrm O_n$).

Primal relaxation

$$\mathrm x^{\top} \mathrm Q \,\mathrm x = \mbox{tr} (\mathrm x^{\top} \mathrm Q \,\mathrm x) = \mbox{tr} (\mathrm Q \,\mathrm x \mathrm x^{\top})$$

where $\mathrm x \mathrm x^{\top}$ is symmetric, positive semidefinite, rank-$1$ and has $n$ ones on its main diagonal. Lifting, we obtain the following (non-convex) optimization problem

$$\begin{array}{ll} \text{minimize} & \mbox{tr} (\mathrm Q \mathrm X)\\ \text{subject to} & \mathrm X_{ii} = 1 \quad \forall i \in [n]\\ & \mathrm X \succeq \mathrm O_n\\ & \mbox{rank} (\mathrm X) = 1\end{array}$$

Dropping the non-convex rank constraint, we obtain the following semidefinite program (SDP)

$$\begin{array}{ll} \text{minimize} & \mbox{tr} (\mathrm Q \mathrm X)\\ \text{subject to} & \mathrm X_{ii} = 1 \quad \forall i \in [n]\\ & \mathrm X \succeq \mathrm O_n\end{array}$$

which is easy to solve. If the solution of this SDP, which we denote by $\mathrm X^*$, is

• rank-$1$, then we have solved the original QCQP.
• not rank-$1$, then we do need a rounding scheme.

If matrix $\mathrm Q$ is nonnegative with zeros on the main diagonal, then it is the adjacency matrix of an undirected, weighted graph and we can use Goemans & Williamson's famous randomized rounding scheme for MAX CUT [MG&DW'95, BG&JM'12].

Dual

The QCQP yields the following Lagrangian

$$\mathcal{L} (\mathrm x, \lambda) := \mathrm x^{\top} \mathrm Q \,\mathrm x - \sum_{i=1}^n \lambda_i (x_i^2 - 1) = \mathrm x^{\top} \left( \mathrm Q - \mbox{diag} (\lambda) \right) \mathrm x + 1_n^{\top} \lambda$$

The dual of the QCQP [PP&SL'03, PP&SL'06] is, thus,

$$\begin{array}{ll} \text{maximize} & 1_n^{\top} \lambda\\ \text{subject to} & \mbox{diag} (\lambda) \preceq \mathrm Q\end{array}$$

Hence, we have the following SDP in $\Lambda$

$$\begin{array}{ll} \text{maximize} & \mbox{tr} (\Lambda)\\ \text{subject to} & \Lambda_{ij} = 0 \quad \forall i \neq j\\ & \Lambda \preceq \mathrm Q\end{array}$$

which is convex and, thus, easy (unlike the QCQP). This SDP does provide a lower bound on the minimum of the QCQP. If $\mathrm x \in \{\pm 1\}^n$ is in the feasible region of the QCQP, then

$$\mathrm x^{\top} \mathrm Q \,\mathrm x \geq \mathrm x^{\top} \Lambda \,\mathrm x = \sum_{i=1}^n \Lambda_{ii} x_i^2 = \sum_{i=1}^n \Lambda_{ii} = \mbox{tr} (\Lambda)$$

References

[MG&DW'95] Michel X. Goemans, David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, Vol. 42, No. 6, November 1995.

[BG&JM'12] Bernd Gärtner, Jiří Matoušek, Approximation Algorithms and Semidefinite Programming, Springer 2012.