The simultaneous convex hull of multilinear functions — the tightest possible convex relaxation of their combined graphs — is fully determined by the values at corner points of axis-aligned regions. Not by the values everywhere. Not by sampling. By the corners alone.
Zhu, He, and Tawarmalani prove this geometric fact and use it to construct polyhedral relaxations for mixed-integer nonlinear programs. The practical impact: on 619 MINLPLib benchmark instances, their method provides superior dual bounds on roughly 30% of problems, with 10% showing gap reductions exceeding 50%.
The theoretical result is what matters. Multilinear functions over continuous domains have infinitely many values. The convex hull — the tightest convex outer approximation — depends on all of them, in general. But when the domains are axis-aligned (hyperrectangles), the hull collapses to dependence on finitely many corner points. The infinite-dimensional object is determined by finite data.
This extends a well-known result for single bilinear functions over rectangles (the McCormick envelope) to simultaneous hulls of multiple multilinear functions. The extension is nontrivial because the simultaneous hull — the hull of all function graphs taken together — can be tighter than the intersection of individual hulls. Taking the functions together introduces constraints that the individual functions don't have.
Corner sufficiency means that computational geometry tools (voxelization, QuickHull) can compute these hulls efficiently. The geometry of the problem is finite even when the domain is continuous. Knowing the corners is knowing enough.