# Finding the dual of a Linear Matrix Inequality feasible set

I am stuck at the following problem about semidefinite programming and linear matrix inequalities, taken from https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-972-algebraic-techniques-and-semidefinite-optimization-spring-2006/assignments/hw1.pdf Problem 3.

Given a set $\mathcal{S} \subseteq \mathbb{R}^n$ that strictly contains the origin, we define the dual set $\mathcal{S}^o$ as $$\mathcal{S}^o:=\{y \in \mathbb{R}^n: y^Tx\leq1, \forall x \in \mathcal{S}\}$$ Let $\mathcal{S}$ be the feasible set of an SDP i.e. $$\mathcal{S}:= \left \{x \in \mathbb{R}^n : \sum_{i=1}^kx_iA_i \preceq A_0 \right \}$$ where $A_0 \succeq 0$ and the $A_i$ are symmetric matrices. Here $X\succeq Y$ means that $\langle (X-Y)u,u\rangle\ge 0$ for all $u\in\Bbb R^n$.

Find a convenient description of $S^o$. Can you optimize a linear function over $S^o$?

I have tried the simple case where the set $\mathcal{S}$ is a bounded polytope, in this case the dual set is the dual polytope which can be characterized as the vectors $\{y: y^Tv_i \leq 1\, \forall i=1, \ldots, k \}$ where $v_i$ are the vertices of the polytope. In this case maximizing a linear function over the dual polytope $c^Ty$ yields $||c||$ the norm associated to the original polytope. But I have no idea what happens in the case of general linear matrix inequalities.

• What are the $A_i$? – amsmath Sep 13 '18 at 19:13
• Symmetric matrices of the same dimension – latorrefabian Sep 13 '18 at 19:32
• For $x\in\Bbb R^n$ let $H_x := \{y : y^Tx\le 1\}$ and define the map $\phi : \Bbb R^n\to\Bbb R^k$ by $\phi(y) := (y^TA_1y,\ldots,y^TA_ky)^T$. Moreover, let $B_0 := \{y : y^TA_0y = 1\}$. Then $S = \{x : \phi(B_0)\subset H_x\}$ and $S^\circ = \bigcap_{x\in S}H_x$. Hence, we trivially have $\phi(B_0)\subset S^\circ$. I guess that also the opposite inclusion holds, but I cannot show it. – amsmath Sep 13 '18 at 19:59

The condition $$y^Tx\leq1 \quad \forall x \in \mathbb{R}^n : \sum_{i=1}^kx_iA_i \preceq A_0$$ is equivalent with $$\max_{x \in \mathbb{R}^n} \{ y^Tx : \sum_{i=1}^kx_iA_i \preceq A_0 \} \leq 1$$ If you now apply SDP duality, you get a "$\min_y$" on the left hand side. You can then proceed to replace the min operator with "$\exists y$".