A convex envelope formula for multilinear functions. (English) Zbl 0881.90099

Summary: Convex envelopes of multilinear functions on a unit hypercube are polyhedral. This well-known fact makes the convex envelope approximation very useful in the linearization of nonlinear 0-1 programming problems and in global bilinear optimization. This paper presents necessary and sufficient conditions for a convex envelope to be a polyhedral function and illustrates how these conditions may be used in constructing of convex envelopes. The main result of the paper is a simple analytical formula, which defines some faces of the convex envelope of a multilinear function. This formula proves to be a generalization of the well known convex envelope formula for multilinear monomial functions.


90C09 Boolean programming
Full Text: DOI