How to convert a semidefinite program to an optimization problem that can be solved by the ellipsoid method?

91 Views Asked by At

Suppose we have the following set of linear inequalities in $x \in \mathbb R^n$

$$\begin{aligned} a_1^T x &\leq b_1\\ a_2^T x &\leq b_2\\ &\vdots\\ a_k^T x &\leq b_k\end{aligned}$$

If the feasible set of these set of linear inequalities is a bounded full-dimensional set and contains a ball of radius $r > 0$ then the ellipsoid method finds a feasible point in polynomial time.

In some papers I have read that feasibility of every semidefinite program can be solved with the ellipsoid method.

My problem is that how we can convert the following form of a semidefinite programming to a set of inequalities (to be solved by the ellipsoid method)?

$$\text{s.t. }\langle A_{i},X \rangle=b_{i} , i=1,\ldots,m$$ $$X\succeq0$$

I will be grateful for every hint.