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

Rikun, Anatoliy D.

J. Glob. Optim. 10, No. 4, 425-437 (1997).

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.

MSC:

90C09

Boolean programming

Keywords:

concave extension; convex envelopes of multilinear functions; nonlinear 0-1 programming; bilinear optimization; polyhedral function