HOME    »    SCIENTIFIC RESOURCES    »    Volumes
SCIENTIFIC RESOURCES

Abstracts and Talk Materials
Algebraic Algorithms in Optimization
January 12 - 13, 2007

Demo and introduction to LattE
January 13, 2007

Barvinok's algorithm for counting
1. Generating functions and non-linear integer optimization
2. Other Rational Functions (Vergne, Lasserre,Nesterov)

Barvinok's algorithm for counting
1. Original approach
2. Homogenized algorithm
3. Integer linear programming in fixed dimension

We consider the problem (P) of minimizing a polynomial function over a semialgebraic set defined by polynomial inequalities and equations. This is a hard problem, which includes well known NP-hard instances such as 0/1 linear programming, the partition problem for integer sequences, or matrix copositivity.

While it is hard to test whether a polynomial is nonnegative, one can test efficiently whether it can be written as a sum of squares of polynomials using semidefinite programming. Based on this paradigm, one can formulate tractable semidefinite programming relaxations for (P) by replacing the hard `nonnegativity' condition by the tractable 'sum of squares' condition. The corresponding dual semidefinite programs involve positive semidefinite moment matrices, which reflects the classical duality theory between positive polynomials and moment sequences.

The objective of this tutorial is to present in detail the main properties of these semidefinite programming relaxations: asymptotic/finite convergence, optimality certificate, and extraction of global optimum solutions for (P), and to review the underlying mathematical tools: representation theorems for positive polynomials from real algebraic geometry, results about the truncated moment problem, and the algebraic eigenvalue method for solving systems of polynomial equations. These characteristic features are implemented in GloptiPoly, a solver for polynomial optimization developped by Henrion and Lasserre, and will be demonstrated on examples. Additional topics that may be covered if time allows include: various algebraic approaches to unconstrained polynomial minimization, link to combinatorial methods for 0/1 polynomial optimization, techniques for exploiting symmetry, sparsity, etc.

Part II
1. The Gröebner fan.
2. Total dual integrality.
3. Group relaxations.

Part I
1. Linear programming and triangulations.
2. The integer program and toric ideals.
3. Test sets, Gröebner bases and initial ideals.

 Connect With Us: Go
 © 2015 Regents of the University of Minnesota. All rights reserved. The University of Minnesota is an equal opportunity educator and employer Last modified on October 06, 2011 Twin Cities Campus:   Parking & Transportation   Maps & Directions Directories   Contact U of M   Privacy