• Speaker: Prof Jeff Linderoth, Department of Industrial and Systems Engineering, University of Wisconsin-Madison
  • Title: Multi-term Relaxations for Multi-linear Programs
  • Location: Room V206, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Access Grid Venue: UNewcastle [ENQUIRIES]
  • Time and Date: 4:00 pm, Thu, 22nd Nov 2012
  • 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.

    Joint work with Jim Luedtke, University of Wisconsin-Madison, and Mahdi Namazifar, now with Opera Solutions.

  • [Permanent link]