New Finite Relaxation Hierarchies for Disjoint Bilinear Programs
Presenter
August 30, 2024
Abstract
We introduce new relaxation hierarchies for concavo-convex programs, including disjoint bilinear and concave minimization. These hierarchies utilize rational functions that are barycentric coordinates of polytopes. The hierarchies have a geometric and an algebraic underpinning and converge to convex hull of the problem at a finite level. Relaxation techniques for this class of problems include disjunctive programming and reformulation-linearization technique. Our hierarchy provides the first unifying framework relating these hierarchies to one another while strengthening the relaxations. The new hierarchy exploits the linear precision of barycentric coordinates to improve the relaxation at each level and leverages recent advances in convexification of fractional optimization problems.