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
\begin{equation}
f^*=\hbox{maximize} \ f(x_1,x_2,\dots,x_d) \ \hbox{subject to} \ x
\in P \cap {\mathbb Z}^d.\label{eq:maximize}
\end{equation}
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.

reading:

draft text for the participants

slides:

slides of talk