4
$\begingroup$

I was wondering what the covering number of a positive semidefinite cone is. Consider the semidefinite optimization program \begin{align} \max\langle \mathbf{C}, \mathbf{X} \rangle~~\text{subject to}~~ \langle \mathbf{A}_i, \mathbf{X} \rangle \leq b_i, i= 1,\ldots, m, \mathbf{X} \succeq \mathbf{0}. \end{align} Is it possible to find finite number of elements $\{ \mathbf{V}_k \}_{k=1}^N$ in the SDP cone \begin{align} \left\{ {\bf {X} }\in \mathbb{R}^{n\times n}\colon \langle \mathbf{A}_i, \mathbf{X} \rangle \leq b_i, i= 1,\ldots, m, \mathbf{X} \succeq \mathbf{0} \right\} \end{align} such that $$\max_{1\leq k \leq N} \langle \mathbf{V}_k, \mathbf{C}\rangle $$ is a good approximation of the original SDP optimization program?

In linear programming, we know the answer is positive. We can just search over all the vertices of the constraint and get the exact objective value.

Improve this question
$\endgroup$
2
  • $\begingroup$ What do you mean by "good approximation"? In general, the SDP cone has infinitely many extremal points. Thus, you do not get the exact objective value by searching over finitely many points. $\endgroup$
    – gerw
    Commented Jul 26, 2016 at 8:01
  • $\begingroup$ Thanks for your reply. Is it possible to find finite number of points that are may not be extremal to obtain the objective value? If finding exact objective is impossible, is it possible to approximate the objective value? Say, get some (!+epsilon) approximation? $\endgroup$
    – Steve
    Commented Jul 29, 2016 at 6:27

0

Reset to default

You must log in to answer this question.