Nonlinear optimization via summation and integration

Friday, November 21, 2008 - 2:00pm - 2:45pm
EE/CS 3-180
Matthias Koeppe (University of California)
The classic idea to relate the maximum of a function over a
discrete or continuous domain to certain sums or integrals has
made its apppearance in a number of recent papers from the
point of view of optimization (A.I. Barvinok, Exponential
integrals and sums over convex polyhedra,
Funktsional. Anal. i Prilozhen. 26 (1992); J.B. Lasserre,
Generating functions and duality for integer programs,
Discrete Optim. 1 (2004)).

Efficient summation and integration procedures can give rise
to efficient approximation algorithms for optimization
problems. As an example, a fully polynomial-time
approximation scheme for optimizing arbitrary polynomial
functions over the integer points in polyhedra of arbitrary,
fixed dimension has been obtained (work with J. A. De Loera,
R. Hemmecke, R. Weismantel, Math. Oper. Res. 31 (2006)).

In this talk I report on recent work (with V. Baldoni,
N. Berline, J. A. De Loera, M. Vergne) to study the efficiency
of integration procedures for polynomial functions in high
dimension. The methods are related to Brion's formulas,
Barvinok's exponential sums, and also to the polynomial Waring
problem that asks to represent a polynomial as a sum of powers
of few linear forms.

MSC Code: