Convex extensions and envelopes of lower semi-continuous functions

 We define a convex extension of a lower semi-continuous function to be a convex function that is identical to the given function over a pre-specified subset of its domain. Convex extensions are not necessarily constructible or unique. We identify conditions under which a convex extension can be constructed. When multiple convex extensions exist, we characterize the tightest convex extension in a well-defined sense. Using the notion of a generating set, we establish conditions under which the tightest convex extension is the convex envelope. Then, we employ convex extensions to develop a constructive technique for deriving convex envelopes of nonlinear functions. Finally, using the theory of convex extensions we characterize the precise gaps exhibited by various underestimators of $x/y$ over a rectangle and prove that the extensions theory provides convex relaxations that are much tighter than the relaxation provided by the classical outer-linearization of bilinear terms. Received: December 2000 / Accepted: May 2002 Published online: September 5, 2002 RID="*" ID="*" The research was funded in part by a Computational Science and Engineering Fellowship to M.T., and NSF CAREER award (DMI 95-02722) and NSF/Lucent Technologies Industrial Ecology Fellowship (NSF award BES 98-73586) to N.V.S. Key words. convex hulls and envelopes – multilinear functions – disjunctive programming – global optimization