Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 247-263 |
Number of pages | 17 |
Journal | Mathematical Programming, Series B |
Volume | 93 |
Issue number | 2 |
DOIs | |
State | Published - Dec 2002 |
Keywords
- Convex hulls and envelopes
- Disjunctive programming
- Global optimization
- Multilinear functions
ASJC Scopus subject areas
- Software
- Mathematics(all)