# 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.

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:

49M37

Keywords: