On convex envelopes of bilinear terms over polygonal domains
math.OC
Submitted: 2026-10-29
Updated: 2026-10-29
Comments: 32 pages, 13 figures
License: http://creativecommons.org/licenses/by/4.0/
The gist: We develop an algorithm for computing the convex envelope of the bilinear function f(x,y)=xy over possibly nonconvex 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 papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise