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

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

Abstract

In global optimization, the McCormick relaxation is the standard technique for approximating non-convex bilinear terms. However, the tightness of this relaxation relative to the true convex hull has long been a subject of theoretical debate. This paper investigates the approximation ratio between these two constructs, proving that the gap scales with the square root of the number of variables ($\sqrt{n}$). This result establishes that the McCormick relaxation's performance degrades as dimensionality increases, precluding the existence of a constant-factor bound independent of problem size.

Introduction

Global optimization of non-convex functions frequently relies on branch-and-bound algorithms. These algorithms require efficient convex relaxations to provide lower bounds on the optimal value. For bilinear functions—products of the form $x_i \cdot x_j$—the McCormick relaxation is the industry standard due to its low computational overhead. While computationally efficient, it is often looser than the convex hull, which represents the tightest possible convex relaxation.

This research, conducted by a collaborative team from Georgia Tech, the University of Newcastle, and PUC-Rio, quantifies the quality of the McCormick relaxation. The central question addressed is whether the ratio between the McCormick relaxation and the convex hull remains bounded by a constant as the number of variables ($n$) grows, or if the approximation becomes progressively worse.

Theoretical Framework and Methodology

The authors represent a bilinear function $b(x) = \sum a_{ij} x_i x_j$ as a weighted graph where variables correspond to vertices and coefficients $a_{ij}$ correspond to edge weights. This mapping allows the researchers to leverage tools from combinatorial graph theory and discrepancy theory.

The Cut Connection

A pivotal insight of the paper is the link between the "convex hull gap" and graph cuts. The authors demonstrate that at the center of the hypercube, the gap between the McCormick relaxation and the convex hull is exactly half the difference between the maximum and minimum cuts of the coefficient graph. This transformation shifts the problem from continuous optimization to a well-understood combinatorial framework.

Analytical Techniques

To establish formal bounds, the authors employed several sophisticated mathematical tools:

  • Probabilistic Analysis: Using the Chernoff inequality, the team analyzed random bilinear functions (where coefficients are chosen uniformly from $\{1, -1\}$) to show that the McCormick relaxation is almost certainly loose in high dimensions.
  • Discrepancy Theory: To determine the upper bound, they extended arguments from discrepancy theory—the study of point distribution—utilizing the Khintchine inequality.
  • Hadamard Matrices: The researchers used Hadamard matrices to construct explicit, non-random examples that achieve the theoretical lower bounds, confirming the tightness of their analysis.

Key Results

The study provides definitive bounds on the approximation ratio:

  1. The $\sqrt{n}$ Scaling Law: The most significant finding is that the error of the McCormick relaxation scales with $\sqrt{n}$. Specifically, for a random bilinear function, the ratio is at least $\sqrt{n}/4$ with high probability (Lower Bound), and for any bilinear function, the ratio is at most $600\sqrt{n}$ (Upper Bound).
  2. Characterization of Perfection: The authors identified the specific conditions under which the McCormick relaxation is identical to the convex hull. This occurs if and only if every cycle in the coefficient graph contains an even number of positive edges and an even number of negative edges, implying a bipartite structure.
  3. Positive Coefficient Refinement: In cases where all coefficients are positive, the ratio is significantly tighter, bounded by a small constant related to the chromatic number of the graph rather than the total number of variables.

Discussion and Limitations

While the $\sqrt{n}$ bound is a major theoretical advancement over the previously known linear ($n$) bounds, it highlights a fundamental limitation for high-dimensional global optimization: McCormick relaxations become significantly less effective as the number of variables increases.

However, some caveats remain. The constant factor in the upper bound (600) is likely an artifact of the proof technique and is expected to be much smaller in practice. Furthermore, the study focuses on the unit hypercube $[0, 1]^n$; different variable bounds found in real-world engineering problems may alter the behavior of the gap. Finally, while this paper settles the case for bilinear functions, extending these tight bounds to general multilinear functions (products of three or more variables) remains an open area for future research.

Summary updated

Abstract

We investigate how well the graph of a bilinear function \(b{:}\;[0,1]^n\rightarrow \mathbb {R}\) 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 \(c\geqslant \sqrt{n}/4\). On the other hand, we prove that \(c\leqslant 600\sqrt{n}\), 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.
BibTeX
@article{boland2017bounding,
  author = {Natashia Boland and Santanu S. Dey and Thomas Kalinowski and Marco Molinaro and Fabian Rigterink},
  title = {{Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions}},
  journal = {Math. Program.},
  year = {2017},
  doi = {10.1007/s10107-016-1031-5},
}
Figure