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.
Article
View Deriving the convex hull of a polynomial partitioning set through lifting and projection