In semidefinite programming we don't have a full dimensional convex set to use ellipsoid method

Question

In chapter 2 of Gärtner & Matousek's Approximation Algorithms and Semidefinite Programming, when solving a semidefinite program, the authors want to use the ellipsoid method. To use the ellipsoid method we should have a full dimensional convex set. Using the Frobenious norm, the set of solutions of a semidefinite program is of course a convex set. But because of linear equalities it is not full dimensional.

So the authors consider the affine solution space of the system of linear equalities in the semidefinite program. And state that we can restrict the feasible space to this space and so it is full dimensional.

My problem is that, this affine solution space how can be full dimensional. Really it is not full dimensional because it is intersection of affine sets and every affine set should be full dimensional if the intersection is full dimensional.

Answer 1

You seem to be referring to this quote from page 21 of the book:

This set C is convex but not full-dimensional, due to the linear equality constraints in the semidefinite program. But since the affine solution space L of the set of linear equalities can be computed in polynomial time through Gaussian elimination, we may restrict C to this space and then we have a full-dimensional convex set. Technically, this can either be done through an explicit coordinate transformation, or dealt with implicitly (we will do the latter).

When you're asking a question about a specific part of a book or paper, it's best to quote the material and provide a full citation (including page number.) If this isn't what you're referring to, then please do point us to a quote from the book rather than giving your (possibly incorrect) interpretation of what the authors have written.

This is actually stated very clearly in the book. You can deal with the problem by expressing the set of solutions to $Ax=b$ in terms of a point in the set and a linear combination of basis vectors for the null space of $A$. You can then optimize over the coefficients in that linear combination. This requires an LU factorization of $A$, but that can (in theory at least) be done easily in polynomial time.

Keep in mind that this is only a theoretical approach. In computational practice, the ellipsoid algorithm isn't used to solve SDP's. Most commonly, primal-dual interior point methods are used, and these deal directly with the linear equality constraints. Alternatively, first-order convex optimization methods can be used, but these also have no particular problem with the linear constraints.