# 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.

• – Rodrigo de Azevedo Oct 21 '16 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. – Rodrigo de Azevedo Aug 18 '18 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.