Dual of an SDP ${\min}_{X \in \mathcal{S}^n} \quad \ {\rm trace}( W X )$ s.t. $X_{ii} = 1$; $X \succeq 0$

Question

How to obtain the dual of the following semidefinite programming problem (SDP)

\begin{align} \text{minimize}_{X \in \mathcal{S}^n} \quad & {\rm trace}( W X ) \\ \text{subject to }\quad & X_{ii} = 1 \Longleftrightarrow {\rm trace}( e_i^T X e_i) = 1 \quad \forall i = 1,\ldots,n\\ & X \succeq 0 \ \Longleftrightarrow -{\rm trace}( a^T X a) \leq 0 , \quad {\rm for all } \ a \in \mathbb{R}^n \diagdown 0. \end{align} where $e \in \mathbb{R}^n$ is a standard basis vector, $X \in \mathcal{S}^{n \times n}$ symmetric matrices, and $W \in \mathbb{R}^{n \times n}$.

Answer 1

This is the SDP relaxation of a binary quadratic program. Therefore, as noted e.g. in section 1.2 of these notes, it has the following dual problem: \begin{align*} \max \quad & \mathrm{tr}(\Lambda)\\ \text{s.t.} \quad & W \succeq \Lambda,\\ & \Lambda_{i,j}=0, \ \forall i \neq j. \end{align*}

Answer 2

Here is my attempt to write the dual of the above problem. Can you experts please comment on my approach? Thank you in advance.

The Lagrangian can be formed as \begin{align} L(X, S, t) :&= {\rm trace}\left( W X \right) - {\rm trace}\left( S^T X \right) + t^T\left( {\rm diag}(X) - 1\right) \\ &= {\rm trace}\left( \left[ W - S^T + {\rm Diag}(t) \right] X \right) -1^T t \end{align} where $S \succeq 0$ matrix and $t$ column vector are Lagrange multipliers. ${\rm diag}(\cdot)$ creates a vector by extracting the diagonal elements of a matrix. ${\rm Diag}(\cdot)$ creates a diagonal matrix by stacking the vector elements along the main diagonal of a matrix. All ones-vector is shown as $1$.

Now, the dual function can be shown as \begin{align} g(S,y) :&= \inf_{X} L(X,S,t) \\ &= \left\{ \begin{matrix} -1^T t & \quad W - S^T + {\rm Diag}(t) =0 ; \\ -\infty & {\rm otherwise}. \end{matrix} \right. \end{align}

Without loss of generality, we can assume that $S$ is a symmetric matrix, i.e., $S^T = S$.

The dual problem is \begin{equation} \begin{aligned} & \underset{S, \ y}{\text{maximize}} & & -1^T t \\ & \text{subject to} & & {\rm Diag}(t) \ - S = W ,\\ &&& S \succeq 0 \ . \end{aligned} \end{equation}