spectrahedra – Optimization Online

Solving rank-constrained semidefinite programs in exact arithmetic

Published: 2016/02/01, Updated: 2016/09/19

Semi-definite Programming computer algebra, determinantal varieties, exact algorithms, linear matrix inequalities, polynomial optimization, rank constraints, semidefinite programming, spectrahedra, sums-of-squares

We consider the problem of minimizing a linear function over an affine section of the cone of positive semidefinite matrices, with the additional constraint that the feasible matrix has prescribed rank. When the rank constraint is active, this is a non-convex optimization problem, otherwise it is a semidefinite program. Both find numerous applications especially in … Read more

A Semidefinite Hierarchy for Containment of Spectrahedra

Published: 2013/08/23, Updated: 2015/03/20

Kai Kellner

Thorsten Theobald

Christian Trabandt

Semi-definite Programming complete positivity, containment, moment relaxation, positive map, semidefinite programming, spectrahedra

A spectrahedron is the positivity region of a linear matrix pencil, thus defining the feasible set of a semidefinite program. We propose and study a hierarchy of sufficient semidefinite conditions to certify the containment of a spectrahedron in another one. This approach comes from applying a moment relaxation to a suitable polynomial optimization formulation. The … Read more