Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Question

Let $V\simeq \mathbb{R}^r$ be an $r$-dimensional vector space with the usual Euclidean inner product.

Let $\mathcal K\subset V$ be a cone defined as $$ \mathcal K=\Big\{x\in V\Big|\exists y\in\mathbb{R}^s~\mathrm{such~that}~\sum_{i=1}^r x_i X_i+\sum_{j=1}^s y_j Y_j\geq0\Big\}, $$ where $\{X_i\}_{1\leq i\leq r},\{Y_j\}_{1\leq j\leq s}\in B(H)^{sa}$ are self-adjoint operators acting on some finite-dimensional Hilbert space $H$. These cones are called semidefinite representable (SDR). They are projections of spectrahedra and have all the nice properties of the latter, plus some others. Some good reference on these beasts would be great.

The dual of $\mathcal K$ is defined as $\mathcal K^*=\{x'\in V\\,|\\, x\cdot x'\geq0~\forall x\in \mathcal K\}$.

Question: Is $\mathcal K^*$ an SDR cone? What are the corresponding operators?

In particular I am interested in an answer presented in the same form, i.e. some set of self-adjoint operators defining $\mathcal K^*$. However, but I'm not sure it's even possible.

Of course a general solution would be great, but I can settle by making a few assumptions.

Assumption 0: Without loss of generality, $\{Y_j\}$ can be assumed to be linearly independent.

Assumption 1: The cone $\mathcal K$ is pointed or salient; $\mathcal K\cap(-\mathcal K)=\{0\}$.

Assumption 2: The cone $\mathcal K$ is generating; $V=\mathcal K-\mathcal K$.


Some partial insights

Assumption 1 already tells us some things about $\{X_i\}$ and $\{Y_j\}$. A few immediate consequences are

  • Fact 1: $\{X_i\}$ are linearly independent. If they weren't $\mathcal K$ would contain some entire subspace of $V$, thus wouldn't be pointed.
  • Fact 2: $\mathrm{span}\{Y_i\}$ does not contain an order unit for $\mathrm{span}\{X_i\}$ or any subspace thereof. Same reason as above.
  • Fact 3: $\{X_i,Y_j\}$ are linearly independent.

Proof: Suppose they are not. Take $$\sum_i \alpha_i X_i+\sum_j \beta_j Y_j=0$$ with some nonzero coefficients, so that $\sum_i \alpha_i X_i=-\sum_j \beta_j Y_j$ is nonzero because $\{X_i\}$ and $\{Y_j\}$ are linearly independent. Then $\alpha\neq0$. For any $\lambda\in\mathbb{R}$, $\lambda\alpha\in\mathcal K$. Thus $\mathcal K$ is not pointed. $\blacksquare$

From Fact 3 we can complete the set of operators to $\{X_i,Y_j,Z_k\}_{(1\leq i\leq r, 1\leq j\leq s, 1\leq k\leq t)}$ to form a basis of $B(H)^{sa}$. In addition, define the conjugate basis with respect to the Hilbert-Schmidt inner product \begin{align} \begin{array}{ccc} \mathrm{tr}[X_i \tilde X_{i'}]=\delta_{ii'}, &\mathrm{tr}[X_i \tilde Y_{j'}]=0&\mathrm{tr}[X_i \tilde Z_{k'}]=0\\\ \mathrm{tr}[Y_j \tilde X_{i'}]=0, &\mathrm{tr}[Y_j \tilde Y_{j'}]=\delta_{jj'}&\mathrm{tr}[Y_j \tilde Z_{k'}]=0\\\ \mathrm{tr}[Z_k \tilde X_{i'}]=0, &\mathrm{tr}[Z_k \tilde Y_{j'}]=0&\mathrm{tr}[Z_k \tilde Z_{k'}]=\delta_{kk'}\\\ \end{array} \end{align}

Partial answer: With the conjugate basis one can define $$ \mathcal C=\Big\{a\in V\Big|\exists c\in\mathbb{R}^t~\mathrm{such~that}~\sum_{i=1}^r a_i \tilde X_i+\sum_{k=1}^t c_k \tilde Z_k\geq0\Big\}. $$ and show that $\mathcal C\subseteq\mathcal K^*$.

Proof: Let $a\in\mathcal C$. Then there is $c\in\mathbb{R}^t$ such that $$ \mathcal A=\sum_{i}a_{i} \tilde X_{i}+\sum_{k}c_{k} \tilde Z_k\geq0. $$ For any $x\in\mathcal K$, there is $y\in\mathbb{R}^s$ such that $$ \mathcal X=\sum_{i}x_i X_i+\sum_{j}y_j Y_j\geq0 $$ thus the inner product $x\cdot a=\mathrm{tr}[\mathcal X\mathcal A]\geq0$. Therefore, $$ a\in\mathcal C~~\Rightarrow~~ x\cdot a\geq0~\forall x\in\mathcal K~~\Rightarrow~~ a\in\mathcal K^*. $$

Alternative Question: Under what conditions it is true that $\mathcal K^*=\mathcal C$?

[Edit] Partial answer: A sufficient condition for equality is that $\mathrm{span}\{X_i,Y_j\}$ intersects the interior of the positive semidefinite cone, as Noah explains in his answer. Whether Assumption 2 guarantees this is an open question (for me). Interestingly, for spectrahedra, this is always the case.

share|improve this question

2 Answers 2

Edited in response to Alex Monras's correction in the comments:

The cone $\mathcal{K}^*$ is always SDR: this is just the conic / homogeneous version of Theorem 5.57 in the new book "Semidefinite Optimization and Convex Algebraic Geometry" by Blekherman, Parrilo, and Thomas. This book is also a good source for more background about this field.

As for the proof, it consists of writing the semidefinite program: minimize $Y\bullet X$ subject to $X\in\mathcal{K}$. This is always feasible (take $X=0$) and so has optimum either $0$ or $-\infty$. Take the usual dual semidefinite program. If strong duality holds (e.g. there is an $(x,y)$ pair making the constraint strictly positive definite), the dual has zero objective and the set of $Y$ for which it is feasible defines exactly the semidefinite representation of $\mathcal{K}^*$.

To show $\mathcal{K} ^ * $ is SDR without imposing a constraint qualification like the Slater condition, you need an extended dual SDP construction like the one proposed by Ramana. In either case, working through the details of the proof will (at least in principle) give the precise form of the representation for $\mathcal{K}^*$.

share|improve this answer
    
Thanks for the reference. Very useful indeed. I am going through it, but it seems that they use a different notion of duality $\mathcal K^\circ=\\{x'|x\cdot x'\leq 1~\forall x\in\mathcal K\\}$? Are they related? (for the homogeneous case!) –  Alex Monras Mar 20 '13 at 11:14
1  
They are equivalent in the homogeneous case. Define $\mathcal{K}^\circ = \{y \mid x\cdot y \leq 1\forall x\in\mathcal{K}$. If $x\in\mathcal{K}$ then $cx\in\mathcal{K}$ for all $c\geq 0$ by homogeneity. Thus for any $y\in\mathcal{K}^\circ$ and $x\in\mathcal{K}$ we actually have $cx\cdot y\leq 1$ for all $c\geq 0$. That is, $x\cdot y\leq 0$. So in your notation $\mathcal{K}^* = -\mathcal{K}^\circ$. –  Noah Stein Mar 20 '13 at 11:41
    
There should be a } at the end of the second sentence. –  Noah Stein Mar 20 '13 at 11:41
    
I worked out the dual and its feasibility region gives me the $C$ cone indeed, as I expected. However, the dual only proves inclusion, and to prove equality one needs to invoke strong duality. I would get strong duality if it were clear that $\mathrm{span}\{X_i,Y_j\}$ intersects with the interior of the PSD cone. For a spectrahedron, such assumption can always be made (Lemma 2.3, arXiv:math/0306180) by restricting to the right subspace, but for an SDR I cannot see this. I am very curious to understand how you see it so clearly. You surely are invoking a more general Slater condition than mine. –  Alex Monras Mar 31 '13 at 7:16
    
You are right. I made a mistake in thinking that an element of the interior of $\mathcal{K}$ would make the constraint strictly positive definite, which of course it does not. I believe the argument that $\mathcal{K}^*$ iS SDR still goes through if you use Ramana's extended dual (which does not require a Slater-type constraint qualification), but this might give you slightly different operators in cases where Slater's condition does not hold. –  Noah Stein Apr 1 '13 at 0:35

It's a long comment, not an answer.

Already the well-known SDR cone $\Sigma_{n,d}$ of sums of squares of homogeneous $n$-variate degreed $d$ polynomials has an interesting dual (also SDR), described e.g. in B.Reznick's AMS Memoir, Theorem 3.16. At least this gives interesting examples to play with.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.