Brute force search algorithm for semidefinite programming (representation of spectrahedron)

I was wondering if there exists a brute force search algorithm for semidefinite programming problems. Specifically, can we find finite number of points in the positive semidefinite cone such that for any objective, we can get a good approximation by searching over these finite points?

In a linear program, the answer is positive; we can search over all the vertices of the constraint, which is a convex polytope.

This question is closely related to the representation of a spectrahedron, which is the intersection of the PSD cone with planes or half-spaces. Specifically, if the spectrahedron is finite representable, then we can search the values of the objective over the basis of the representations.

• Oct 21, 2016 at 9:36
• Points inside the positive semidefinite cone are not necessarily inside the spectrahedron, for the spectrahedron is the intersection of the positive semidefinite cone with hyperplanes or convex polytopes. Aug 18, 2018 at 16:00

But if you mean to ask whether the feasible region of every SDP is the convex closure of finitely many extreme points, or whether, for any SDP, there is a finite set $S$ of points in the feasible region such that, for any linear objective, some point in $S$ is approximately optimal, the answer is surely no.
For example, fix $\epsilon>0$ and consider the SDP $$\min \{\epsilon X_{11} + X_{22} : X\in\mathbb{R}^{2\times 2},~X \text{ p.s.d.}, X_{12} = X_{21} = 1\}.$$ The feasible region consists of 2d p.s.d. matrices of the form $\left(\begin{array}{cc}x&1\\1&y\end{array}\right)$. The matrix is p.s.d. iff $x,y> 0$ and $xy\ge 1$. So there are infinitely many matrices $X$ (those with $y=1/x$) in the feasible region that are not convex combinations of other matrices in the region.
Further, the unique optimal point has $(x,y)=(1/\sqrt{\epsilon}, \sqrt{\epsilon})$ and has value $2\sqrt{\epsilon}$. The feasible region is independent of $\epsilon$, and, for any finite subset $S$ of that feasible region (where $S$ is independent of $\epsilon$), letting $x' = \min\{ X_{22} : X\in S\} > 0$, no point in $S$ has value less than $x'$. So, for sufficiently small $\epsilon$ (where $\sqrt\epsilon \ll x'$), no point in $S$ approximates the optimum well.