Seminar: Valid Polynomial Inequality Generation in Polynomial Optimization

SPEAKER:               Professor Miguel F. Anjos
                                    Mathematics and Industrial Engineering
                                    Ecole Polytechnique de Montreal, Canada
 
DATE / TIME:          Monday, June 13, 2011
                                    2:00 – 3:00 p.m.
 
LOCATION:             Room 453 Mohler Lab, 200 W. Packer Avenue
 
 
ABSTRACT:  Polynomial optimization problems are normally solved using hierarchies of convex relaxations.  These schemes rapidly become computationally expensive, and are usually tractable only for problems of small sizes.  We propose a novel dynamic scheme for generating valid polynomial inequalities for general polynomial optimization problems.  These valid inequalities are then used to construct better approximations of the original problem.  For the special case of binary polynomial problems, we prove that the proposed scheme converges to the global optimal solution under mild assumptions on the initial approximation of the problem.  We also present examples illustrating the computational behavior of the scheme and compare it to other methods in the literature.
 
This is joint work with Bissan Ghaddar (U of Waterloo) and Juan Vera (Tilburg U).