Integer optimization on convex semialgebraic sets (Q1971505): Difference between revisions

Let \(Y\) be a convex set in \(\mathbb{R}^k\) defined by polynomial inequalities and equations of degree at most \(d\geq 2\) with integer coefficients of binary length at most \(\ell\). The main result states that if the set of optimal solutions of the integer programming problem \(\min\{y_k\mid y=(y_1, \dots, y_k)\in Y\cap \mathbb{Z}^k\}\) is not empty, then the problem has an optimal solution \(y^*\in Y\cap \mathbb{Z}^k\) of binary length \(\ell d^{O(k4)}\). Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension is extended to semidefinite integer programming.