Optimization Online


Deriving the convex hull of a polynomial partitioning set through lifting and projection

Trang T. Nguyen(trang***at***ufl.edu)
Jean-Philippe P. Richard(richard***at***ise.ufl.edu)
Mohit Tawarmalani(mtawarma***at***purdue.edu)

Abstract: Relaxations of the bilinear term, $x_1x_2=x_3$, play a central role in constructing relaxations of factorable functions. This is because they can be used directly to relax products of functions with known relaxations. In this paper, we provide a compact, closed-form description of the convex hull of this and other more general bivariate monomial terms (which have similar applications in relaxation constructions) in the space of the original variables assuming that the variables and the monomial are restricted to lie in a hyperrectangle. This description is obtained as an intersection of convex hulls of related packing, $x_1x_2^{b_2}\le x_3$, and covering, $x_1^{b_1}x_2^{b_2}\ge x_3$, sets, where $b_1$ and $b_2$ are constants greater than or equal to one. The convex hull of each packing/covering set is first obtained as an intersection of semi-infinite families of linear inequalities, each derived using lifting techniques. Then, each family is projected into a few linear/nonlinear inequalities which are fully characterized in the space of the original problem variables.

Keywords: convexification techniques, polynomial partitioning sets, nonlinear cuts

Category 1: Global Optimization (Theory )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 02/28/2014
Entry Accepted: 02/28/2014
Entry Last Modified: 02/28/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society