Multi-term Relaxations for Multi-linear Programs

Host Institution:

University of Newcastle

Title of Seminar:

Multi-term Relaxations for Multi-linear Programs

Speaker's Name:

Professor Jeff Linderoth

Speaker's Institution:

Dept. of Industrial and Systems Engineering, University of Wisconsin-Madison

Time and Date:

Thursday 22 November, 4.00pm (EDT)

Seminar Abstract:

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.

Seminar Convenor:

This email address is being protected from spambots. You need JavaScript enabled to view it.

AGR IT support: