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.

$\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
    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
    Jul 29, 2016 at 6:27

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.