Integer optimization on convex semialgebraic sets

Let Y be a convex set in R-k defined by polynomial inequalities and equatio ns of degree at most d greater than or equal to 2 with integer coefficients of binary length at most l. We show that if the set of optimal solutions o f the integer programming problem min{y(k) \ y = (y(1), ..., y(k)) is an el ement of Y boolean AND Z(k)} is not empty, then the problem has an optimal solution y* is an element of Y boolean AND Zk Of binary length ld(0(k4)). F or fixed k, bur bound implies a polynomial-time algorithm for computing an optimal integral solution y*. In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dim ension to semidefinite integer programming.