## 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)