Convex extensions and envelopes of lower semi-continuous functions. (English) Zbl 1065.90062

Tawarmalani, Mohit; Sahinidis, Nikolaos V.

Math. Program. 93, No. 2 (A), 247-263 (2002).

Summary: 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.

MSC:

90C26	Nonconvex programming, global optimization
90C30	Nonlinear programming