Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions

DOI10.1007/S10107-016-1031-5MaRDI QIDQ517317zbMATH OpenOpenAlexWikidataFDO

Authors Natashia Boland, Santanu S. Dey, Thomas Kalinowski, Marco Molinaro, Fabian Rigterink

Publication date 23 March 2017

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

bilinear functionconvex hullglobal optimization

Mathematics Subject Classification ID

Quadratic programming (90C20) Nonconvex programming, global optimization (90C26)

Abstract: We investigate how well the graph of a bilinear function $b:[0,1{]}^{n}omathbbR$ can be approximated by its McCormick relaxation. In particular, we are interested in the smallest number $c$ such that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is at most $c$ times the difference between the concave and convex envelopes. Answering a question of Luedtke, Namazifar and Linderoth, we show that this factor $c$ cannot be bounded by a constant independent of $n$. More precisely, we show that for a random bilinear function $b$ we have asymptotically almost surely $cgeqslantsqrtn/4$. On the other hand, we prove that $cleqslant600sqrtn$, which improves the linear upper bound proved by Luedtke, Namazifar and Linderoth. In addition, we present an alternative proof for a result of Misener, Smadbeck and Floudas characterizing functions $b$ for which the McCormick relaxation is equal to the convex hull.

Recommendations

• Convex relaxations and integrality gaps
• Relaxation of convex functionals: the gap problem
• The bilinear multiplier problem for strictly convex compact sets
• Extended formulations for convex hulls of some bilinear functions
• Valid inequalities and convex hulls for multilinear functions
• Improved convex and concave relaxations of composite bilinear forms
• On the strength of recursive McCormick relaxations for binary polynomial optimization
• Convex functions and approximate Birkhoff-James orthogonality
• Bilinear optimality constraints for the cone of positive polynomials
• Bounds for linear functionals on convex sets

Cites work

• A convex envelope formula for multilinear functions
• 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
• Concave extensions for nonlinear 0-1 maximization problems
• Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets
• Cutting a graph into two dissimilar halves
• Discrepancy in graphs and hypergraphs
• Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2
• Explicit convex and concave envelopes through polyhedral subdivisions
• scientific article; zbMATH DE number 47153 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 1445458 (Why is no real title available?)
• Imbalances in k‐colorations
• Jointly Constrained Biconvex Programming
• Some results on the strength of relaxations of multilinear functions
• The best constants in the Khintchine inequality

Cited in

(14)

• Strong formulations for quadratic optimization with M-matrices and indicator variables
• On solving a large-scale problem on facility location and customer assignment with interaction costs along a time horizon
• Convexification of bilinear forms through non-symmetric lifting
• Exact and approximate results for convex envelopes of special structured functions over simplices
• A new framework to relax composite functions in nonlinear programs
• On tightness and anchoring of McCormick and other relaxations
• New SOCP relaxation and branching rule for bipartite bilinear programs
• Error bounds for monomial convexification in polynomial optimization
• Tractable relaxations of composite functions
• \(2 \times 2\)-convexifications for convex quadratic optimization with indicator variables
• The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints
• (Global) optimization: historical notes and recent developments
• Unifying view on sparse convex relaxations in polynomial optimization
• Extended formulations for convex hulls of some bilinear functions

Describes a project that uses

Uses Software

• GloMIQO
• BARON

This page was built for publication: Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions

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