Minimizing trace of matrix inverse is an SDP?

Question

I'm reading through this paper and on page 8 (PDF page 9), Step 2 in Algorithm 1 reads $$ W \leftarrow \text{argmin} \{\text{tr}(WQW^T) + \alpha\, \text{tr}(Q^{−1}): Q \succeq \epsilon\, I_n , Q_{\text{off}} \leq 0, Q \,\mathbb{1}_n = \epsilon\, \mathbb{1}_n \} $$ where $Q$ is symmetric and $W$ is a $d\times n$ matrix. The following paragraphs claim this is an SDP, "since $\text{tr}(Q^{-1})\leq\beta$ can be rewritten as $$ \text{tr}(R)\leq\beta, \qquad \begin{bmatrix}R & I_n \\ I_n & Q\end{bmatrix} \succeq 0." $$ How are the two conditions equivalent? More importantly, how would this be implemented in an SDP solver like CVX?

Answer 1

You introduce a new variable $R$ for which it holds $R \succeq Q^{-1}$ from which you know $\text{tr}(R) \geq \text{tr}(Q^{-1})$. If you now add a cost in the objective of $\text{tr}(R)$, at optimality it would be optimal to select $R=Q^{-1}$ (otherwise you could decrease the objective by making $R$ smaller). The inequality $R \succeq Q^{-1}$ is then converted to an LMI using a Schur complement.

The reformulation introducing yet another variable $\beta$ to upper bound $\text{tr}(R)$ is just silly and adds nothing. Simply use $\text{tr}(R)$ in the objective.

The model is then an absolutely bog standard LMI and would be immediately implemented in CVX or YALMIP or your language of choice.