SMS scnews item created by Andrew Mathas at Tue 20 Nov 2012 1248
Expiry: 20 Nov 2012
Calendar1: 20 Nov 2012 1600-1700
CalLoc1: AGR Carslaw 829
CalTitle1: AGR Seminar: Multi-term Relaxations for Multi-linear Programs
Auth: email@example.com (assumed)
Multi-term Relaxations for Multi-linear Programs
Professor Jeff Linderoth (University of Wisconsin-Madison)
University of Newcastle
Multi-linear functions appear in many global optimization problems, including reformulated quadratic and polynomial optimization problems. There is a extended formulation for the convex hull of the graph of a multi-linear function that requires the use of an exponential number of variables. Relying on this result, we study an approach that generates relaxations for multiple terms simultaneously, as opposed to methods that relax the nonconvexity of each term individually. In some special cases, we are able to establish analytic bounds on the ratio of the strength of the term-by-term and convex hull relaxations. To our knowledge, these are the first approximation-ratio results for the strength of relaxations of global optimization problems. The results lend insight into the design of practical (non-exponentially sized) relaxations. Computations demonstrate that the bounds obtained in this manner are competitive with the well-known semi-definite programming based bounds for these problems.
Ms Juliane Turner
If you are interested in attending this seminar in our access grid room then please check to see if the grid is already booked at this time and let Robert Pearson know that you would like to attend.