Jesus de Loera

Integer Polynomial Optimizatino in Fixed Dimension

In this minicourse I will begin by presenting a survey of what is known today about the problem of optimizing a polynomial function over polynomial constraints and a fixed number of integer valued variables. After explaining the status of the problem. I will introduce the audience to the theory of Barvinok's rational functions, a powerful tool in polynomial optimization. To illustrate its power I will prove the following result in detail:
\begin{theorem}[De Loera, Hemmecke, Koeppe, Weismantel] Let the number of variables $d$ be fixed. Let $f(x_1,\dots,x_d)$ be a polynomial of maximum total degree $D$ with integer coefficients, and let $P$ be a convex rational polytope defined by linear inequalities in $d$ variables. We obtain an increasing sequence of lower bounds $\{L_k\}$ and a decreasing sequence of upper bounds $\{U_k\}$ to the optimal value $$f^*=\hbox{maximize} \ f(x_1,x_2,\dots,x_d) \ \hbox{subject to} \ x \in P \cap {\mathbb Z}^d.\label{eq:maximize}$$ The bounds $L_k$, $U_k$ can be computed in time polynomial in~$k$, the input size of $P$ and $f$, and the maximum total degree~$D$ and they satisfy the inequality $U_k-L_k \leq f^* \cdot (\sqrt[k]{|P \cap {\mathbb Z}^d|}-1).$ More strongly, if $f$ is non-negative over the polytope (i.e. $f(x)\geq 0$ for all $x \in P$), there exists a fully polynomial-time approximation scheme (FPTAS) for the optimization problem~\eqref{eq:maximize}. \end{theorem}

The talk will cover the following items:

• Introduction survey of the integer optimization problem in fixed dimension.
• Barvinok's Algorithm, software demonstration of LattE.
• FPTAS for Integer Polynomial optimization over Polytopes.
• Further applications.