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

1 Answer

The question is not very well defined. E.g., if the SDP has an optimal solution, then "searching" that one optimal solution is (trivially) enough to find a good approximate (in fact optimal) solution. Similarly, any algorithm that solves the SDP in finite time will find a "good approximate solution" while considering only finitely many points of the SDP.

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.