Convex optimization problem Show that the set K X Y belongs

Convex optimization problem:

Show that the set K = {(X, Y) belongs to S^n Times S^n_+: X^2 lessthanorequalto Trace(Y). Y} is a spectrahedron.

Solution

Spectrahedra under linear projections are still useful for optimization. They are of the form {x Rⁿ | y R^mA (x, y) 0} , for some linear matrix polynomial A in n + m variables. These sets are called semidefinite representable sets Semidefinite representable sets are always convex and semialgebraic, but no other necessary condition is known so far. conjecture that every convex semialgebraic set is semidefinite representable.

1) Every spectrahedron is semidefinite representable. Projections of semidefinite representable sets are semidefinite representable. 2)Finite intersections of semidefinite representable sets are semidefinite representable.

Proof : Let S R m be convex and let : R ^m R ⁿ be a linear map. Then (relint(S)) = relint((S)). Proof. The inclusion ”” is clear. For ”” notice that since relint(S) is convex and dense in S, (relint(S)) is a convex and dense subset of (S).

Assume that S is a spectrahedron, defined by the linear matrix polynomial A . Then F is an exposed face of S Corollary 1), which means that there is an affine linear polynomial ` R[X] such that ` 0 on S and {` = 0} S = F. So we have F = {x R <sup>n</sup> | A (x) 0 `(x) = 0} and S \\ F = x R n | A (x) 0 1 1 `(x) 0 .

This shows that F is even a spectrahedron and S \\ F is semidefinite representable. Now let S be semidefinite representable and let Se R n+m be a spectrahedron such that S is the image of Se with respect to the projection pr: R ^n+m R ⁿ. Then Fe := pr1 (F) Se is a face of Se. Since Fe projects onto F and Se \\ Fe projects onto S \\ F, both sets are semidefinite representable. For a semidefinite representable set with only finitely many faces, i.e. for a polyhedron, we thus know that its interior is again semidefinite representable.