[BANANA] LA/Opt seminar Wed May 20 (Matthias Koeppe)

[Michael A. Saunders]

    Linear Algebra and Optimization Seminar (CME 510)
    iCME, Stanford University
    http://icme.stanford.edu/seminars/seminars.php

    4:15pm Wed May 20, 2009
    Terman 332

    Nonlinear Optimization via Summation and Integration

    Professor Matthias Koeppe
    Dept of Mathematics, UC Davis
    mkoeppe at math.ucdavis.edu
    http://www.math.ucdavis.edu/~mkoeppe

The classic idea of relating 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
(joint work with J. A. De Loera, R. Hemmecke, R. Weismantel,
Math. Oper. Res. 31 (2006)).  No other technique is known today
that matches this result.

In this talk I also report on recent work (with V. Baldoni,
N. Berline, J. A. De Loera, M. Vergne) to study the efficiency of
exact 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.