Convex hull representations for bounded products of variables

DOI10.1007/S10898-021-01046-7MaRDI QIDQ2046306zbMATH OpenOpenAlexFDO

Authors Kurt M. Anstreicher, Samuel Burer, Kyungchan Park

Publication date 17 August 2021

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.07233

zbMATH Keywords

bilinear productconvex hullglobal optimizationsecond-order cone

Mathematics Subject Classification ID

Mixed integer programming (90C11) Quadratic programming (90C20) Semidefinite programming (90C22) Convex programming (90C25) Nonconvex programming, global optimization (90C26)

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 {em et al.,}(2010) and Miller {em 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 {em 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}ge1$, $b_{2}ge1$. 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.

Recommendations

• Semidefinite Representation of Convex Sets and Convex Hulls
• Representation theorems for \(h\)-convexity
• Inner products for convex bodies
• scientific article; zbMATH DE number 3708998
• The convex hull of the interpolating Blaschke products
• Convex hull representations of special monomials of binary variables
• scientific article; zbMATH DE number 4138666
• Semidefinite representation of convex hulls of rational varieties
• scientific article; zbMATH DE number 1098747
• A class of bounds for convex bodies in Hilbert space

Cites work

• A new reformulation-linearization technique for bilinear programming problems
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs
• Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations
• BARON: A general purpose global optimization software package
• Branching and bounds tighteningtechniques for non-convex MINLP
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Computable representations for convex hulls of low-dimensional quadratic forms
• Deriving convex hulls through lifting and projection
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Jointly Constrained Biconvex Programming
• New SOCP relaxation and branching rule for bipartite bilinear programs
• On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation
• Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming
• Strong formulations for the pooling problem
• The Convex Envelope of (n–1)-Convex Functions
• The convex hull of a quadratic constraint over a polytope
• Valid inequalities and convex hulls for multilinear functions

Cited in

(8)

• Deriving convex hulls through lifting and projection
• Tightening methods based on nontrivial bounds on bilinear terms
• Convex hull representations of special monomials of binary variables
• Computable representations for convex hulls of low-dimensional quadratic forms
• Lifting convex inequalities for bipartite bilinear programs
• Tightening discretization-based MILP models for the pooling problem using upper bounds on bilinear terms
• Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held August 13--18, 2023
• Convex envelopes of bounded monomials on two-variable cones

Describes a project that uses

Uses Software

• BARON

This page was built for publication: Convex hull representations for bounded products of variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2046306)