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$
  • $\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 '16 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 '16 at 6:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.