I am stuck at problem 3 of this homework assignment about semidefinite programming and linear matrix inequalities (LMIs).
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.
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$".