On the Complexity of Real and Integer Semidefinite Programming

We consider the general feasibility problem for semidefinite programming: Determine whether a given system of linear inequalities has a solution in the cone of symmetric positive semidefinite matrices. We give upper bounds on the size of real feasible solutions and obtain a strongly polynomial-time algorithm for testing the feasibility of semidefinite programs in fixed dimension whose required number of arithmetic operations grows linearly in the number of constraints. We also consider semidefinite systems in integral matrices and extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension to integer semidefinite programming. In fact, we address the more general problem of computing an integral point in an arbitrary convex semi-algebraic set, and show that in fixed dimension this problem can be solved in polynomial time.Technical report DCS-TR-33