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.

  • $\begingroup$ What are the $A_i$? $\endgroup$ – amsmath Sep 13 '18 at 19:13
  • $\begingroup$ Symmetric matrices of the same dimension $\endgroup$ – latorrefabian Sep 13 '18 at 19:32
  • $\begingroup$ 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. $\endgroup$ – 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$".

  • $\begingroup$ Thank you very much! This leads to the answer. $\endgroup$ – latorrefabian Sep 14 '18 at 16:15

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.