  


Lifting convex inequalities for bipartite bilinear programs
Xiaoyi Gu (xiaoyigugatech.edu) Abstract: The goal of this paper is to derive new classes of valid convex inequalities for quadratically constrained quadratic programs (QCQPs) through the technique of lifting. Our first main result shows that, for sets described by one bipartite bilinear constraint together with bounds, it is always possible to sequentially lift a seed inequality that is valid for a restriction obtained by fixing variables to their bounds, when the lifting is accomplished using affine functions of the fixed variables. In this setting, sequential lifting involves solving a nonconvex nonlinear optimization problem each time a variable is lifted, just as in Mixed Integer Linear Programming. To reduce the computational burden associated with this procedure, we develop a framework based on subadditive approximations of lifting functions that permits sequenceindependent lifting of seed inequalities for separable bipartite bilinear sets. In particular, this framework permits the derivation of closedform valid inequalities. We then study a separable bipartite bilinear set where the coefficients form a minimal cover with respect to the righthandside. For this set, we introduce a bilinear cover inequality, which is secondorder cone representable. We argue that this bilinear cover inequality is strong by showing that it yields a constantfactor approximation of the convex hull of the original set. We study its lifting function and construct a twoslope subadditive upper bound. Using this subadditive approximation, we lift fixed variable pairs in closedform, thus deriving a lifted bilinear cover inequality that is valid for general separable bipartite bilinear sets with box constraints. Keywords: Lifting Separable bipartite bilinear sets Subadditivity Category 1: Global Optimization (Theory ) Category 2: Integer Programming (Cutting Plane Approaches ) Category 3: Nonlinear Optimization (Other ) Citation: Download: [PDF] Entry Submitted: 06/01/2021 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  