AbstractWe 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.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).