On convex envelopes of bilinear terms over polygonal domains
Abstract
We develop an algorithm for computing the convex envelope of the bilinear function f(x,y)=xy over possibly nonconvex polygonal domains. Building on existing methods for convex polytopes, our approach uses the Karush-Kuhn-Tucker conditions and an analysis of the contact points between affine underestimators and the graph of f. Nonconvex domains admit additional contact configurations that prevent several simplifications available in the convex case. We resolve these configurations explicitly and show that the envelope admits a finite polyhedral subdivision with affine, quadratic, or rational expressions on its cells. For orthogonal polygons, whose edges are horizontal or vertical, we establish substantial reductions in the generator sets needed to compute the envelope. We also present methods for constructing such domains as relaxations of two-dimensional projections of nonlinear optimization problems. An illustrative example quantifies the loss in relaxation strength caused by convexifying the domain before computing the envelope. Computational experiments on MINLPLib instances show that cuts derived from orthogonal polygons strengthen root relaxations and reduce branch-and-bound nodes in aggregate.
Related
- Forest Characterization of When SDP-RLT Strengthens RLT for Bilinear Terms
- Kinetic Wedge Layers and Diffusive Limit of Neutron Transport in Polygonal Domains
- Identification of generic polygonal domains by integral-geometric invariants
- Maximal Lp-Lq regularity of finite element methods for stochastic parabolic equations in polygonal domains
- Accelerated primal-dual dynamics and algorithms for strongly convex-concave bilinear saddle point problems
BibTeX
@misc{goß2026convex,
title = {{On convex envelopes of bilinear terms over polygonal domains}},
author = {Adrian Göß and Jan Krause and Martina Kuchlbauer and Tobias Kuen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39826},
eprint = {2610.39826},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39826},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On convex envelopes of bilinear terms over polygonal domains
AU - Adrian Göß
AU - Jan Krause
AU - Martina Kuchlbauer
AU - Tobias Kuen
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39826
UR - https://arxiv.org/abs/2610.39826
AB - We develop an algorithm for computing the convex envelope of the bilinear function f(x,y)=xy over possibly nonconvex polygonal domains. Building on existing methods for convex polytopes, our approach uses the Karush-Kuhn-Tucker conditions and an analysis of the contact points between affine underestimators and the graph of f. Nonconvex domains admit additional contact configurations that prevent several simplifications available in the convex case. We resolve these configurations explicitly and show that the envelope admits a finite polyhedral subdivision with affine, quadratic, or rational expressions on its cells. For orthogonal polygons, whose edges are horizontal or vertical, we establish substantial reductions in the generator sets needed to compute the envelope. We also present methods for constructing such domains as relaxations of two-dimensional projections of nonlinear optimization problems. An illustrative example quantifies the loss in relaxation strength caused by convexifying the domain before computing the envelope. Computational experiments on MINLPLib instances show that cuts derived from orthogonal polygons strengthen root relaxations and reduce branch-and-bound nodes in aggregate.
ER -