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$ Commented Apr 17, 2019 at 5:25

2 Answers 2

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .