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}$.

  • 1
    $\begingroup$ By the way, the feasible region of your SDP is called elliptope. $\endgroup$ – Rodrigo de Azevedo Apr 17 at 5:25

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*}

  • $\begingroup$ Thank you for your input. Actually, I am more interested in finding the dual of the section 1.5 of the notes you have shared. So, the dual you wrote here and dual of the equivalent notion in section 1.5 (but dropping rank 1 constraint?!) should have similar interpretation or may be similar. What do you think? $\endgroup$ – user550103 Apr 16 at 5:00
  • $\begingroup$ But i give you +1 for your attempt as an appreciation token $\endgroup$ – user550103 Apr 16 at 5:02
  • $\begingroup$ The dual problem of the problem in section 1.5 is actually also the dual problem in the answer above. This is because taking the dual of a BQP twice yields its sdp relaxation (you can reason this heuristically by noticing that a dual problem is always convex). $\endgroup$ – Ryan Cory-Wright Apr 16 at 5:26
  • $\begingroup$ Ok, I get that. Thank you. $\endgroup$ – user550103 Apr 16 at 5:40

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}


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.