New finite relaxation hierarchies for concavo-convex, disjoint bilinear programs, and facial disjunctions
本文为凹-凸规划问题引入新的松弛层次，该问题包含不相交双线性规划和凹最小化作为特例，核心是基于双描述算法计算多面体锥的重心坐标，在m次迭代内达到凸包，并统一了析取规划和重构线性化技术的松弛分析。
Abstract This paper introduces novel relaxation hierarchies for concavo-convex programs (CXP), a class of problems that includes disjoint bilinear programming (DBP) and concave minimization (CM) as special cases. At the core of these hierarchies is an algorithm based on double-description (DD) that computes the barycentric coordinates of a polyhedral cone as rational, non-negative functions representing multipliers associated with the cone’s rays. These hierarchies combine geometric structure derived from barycentric coordinates with algebraic techniques via rational functions, achieving the convex hull in m iterations, where m is the number of inequalities that a subset of the variables must satisfy. Our framework offers the first unified approach to analyze and tighten relaxations from disjunctive programming (DP) and reformulation-linearization technique (RLT) for CXP. We also demonstrate that our methods extend to facial disjunctive programs (FDP), where solutions are constrained to lie on faces of a Cartesian product of polytopes, generalizing known hierarchies for 0-1 programs.