Reformulate linear program as semidefinite program

Question

We consider the linear program

$$\min_{x \in R^n} \{c^Tx \mid a_1^Tx \le b_1, a_2^Tx \le b_2\}$$

where $c, a_1, a_2 \in \mathbb R^n$ and $b_1, b_2 \in \mathbb R$ are given. Now we need to reformulate this LP as an SDP.

Can someone help with this task? Thank you!

Answer 1

Use the following linear matrix inequality (LMI) instead of the two linear inequalities

$$\begin{bmatrix} b_1 - \mathrm a_1^{\top} \mathrm x & 0\\ 0 & b_2 - \mathrm a_2^{\top} \mathrm x\end{bmatrix} \succeq \mathrm O_2$$

Take a look at Sylvester's criterion for positive semidefiniteness.

Answer 2

You have to put it in the form $$ \min_{x\in \mathbb{R}^n} c^T x $$ $$ s.b. F_0 + \sum_i x_i F_i \succeq 0 $$ where $F_i,\, i=0...$ are symmetric matrices of order $2$.

Take $$ F_0= \begin{pmatrix} b_1 &0 \\ 0 & b_2 \end{pmatrix} $$ and $$ F_i= \begin{pmatrix} -a_{1i} &0 \\ 0 & -a_{2i} \end{pmatrix} $$ where $a_j=(a_{j1},\ldots a_{jn})^T, \; j=1,2$