  


Deriving the convex hull of a polynomial partitioning set through lifting and projection
Trang T. Nguyen(trangufl.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, closedform 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 semiinfinite 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 ) Citation: Download: [PDF] Entry Submitted: 02/28/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  