1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ By the way, the feasible region of your SDP is called elliptope. $\endgroup$ Apr 17 '19 at 5:25
2
$\begingroup$

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

$\endgroup$
4
  • $\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 '19 at 5:00
  • $\begingroup$ But i give you +1 for your attempt as an appreciation token $\endgroup$
    – user550103
    Apr 16 '19 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$ Apr 16 '19 at 5:26
  • $\begingroup$ Ok, I get that. Thank you. $\endgroup$
    – user550103
    Apr 16 '19 at 5:40
0
$\begingroup$

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}

$\endgroup$

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.