Optimization Online


Convex Hull Representations for Bounded Products of Variables

Kurt Anstreicher(kurt-anstreicher***at***uiowa.edu)
Sam Burer(samuel-burer***at***uiowa.edu)
Kyungchan Park(kyungchan-park***at***uiowa.edu)

Abstract: It is well known that the convex hull of {(x,y,xy)}, where (x,y) is constrained to lie in a box, is given by the Reformulation-Linearization Technique (RLT) constraints. Belotti et al. (2010) and Miller et al. (2011) showed that if there are additional upper and/or lower bounds on the product z=xy, then the convex hull can be represented by adding an infinite family of inequalities, requiring a separation algorithm to implement. Nguyen et al. (2018) derived convex hulls with bounds on z for the more general case of z=x^{b_1}y^{b_2}, where b_1 >= 1, b_2 >= 1. We focus on the most important case where b_1 = b_2 = 1 and show that the convex hull with either an upper bound or lower bound on the product is given by RLT constraints, the bound on z and a single Second-Order Cone (SOC) constraint. With both upper and lower bounds on the product, the convex hull can be represented using no more than three SOC constraints, each applicable on a subset of (x,y) values. In addition to the convex hull characterizations, volumes of the convex hulls with either an upper or lower bound on z are calculated and compared to the relaxation that imposes only the RLT constraints. As an application of these volume results, we show how spatial branching can be applied to the product variable so as to minimize the sum of the volumes for the two resulting subproblems.

Keywords: Convex Hull, Second-Order Cone, Bilinear Product, Global Optimization

Category 1: Global Optimization (Theory )

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Dept. of Business Analytics, Tippie College of Business, University of Iowa, Iowa City, IA 52242, April 2020.

Download: [PDF]

Entry Submitted: 04/15/2020
Entry Accepted: 04/16/2020
Entry Last Modified: 04/15/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society