Deriving convex hulls through lifting and projection

• 成果类型: Article
• 署名作者: Nguyen, Trang T.; Richard, Jean-Philippe P.; Tawarmalani, Mohit
• 署名单位: State University System of Florida; University of Florida; Purdue University System; Purdue University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1138-3
• 发表日期: 2018
• 页码: 377-415
• 关键词: concave envelopes; relaxations; PROGRAMS; REPRESENTATIONS

摘要

We consider convex hull descriptions for certain sets described by inequality constraints over a hypercube and propose a lifting-and-projection technique to construct them. The general procedure obtains the convex hulls as an intersection of semi-infinite families of linear inequalities, each derived using lifting techniques that are interpreted using convexification tools. We demonstrate that differentiability and concavity of certain perturbation functions help reduce the number of inequalities needed for this characterization. Each family of inequalities yields a few linear/nonlinear constraints fully characterized in the space of the original problem variables, when the projection problems are amenable to a closed-form solution. In particular, we illustrate the complete procedure by constructing the convex hulls of the subsets of a compact hypercube defined by the constraints x(1)(b1) x(2)(b2) >= x(3)and x(1)x(2)(b2) <= x(3), where b(1), b(2) >= 1. As a consequence, we obtain a closed-form description of the convex hull of the bilinear equality x(1)x(2)=x(3), in the presence of variable bounds, as an intersection of a few linear and nonlinear inequalities. This explicit characterization, hitherto unknown, can improve relaxation techniques for factorable functions, which utilize this equality to relax products of functions with known relaxations.