Convex extensions and envelopes of lower semi-continuous functions

Mohit Tawarmalani, Nikolaos V. Sahinidis

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)247-263
Number of pages17
JournalMathematical Programming, Series B
Volume93
Issue number2
DOIs
StatePublished - Dec 2002

Keywords

  • Convex hulls and envelopes
  • Disjunctive programming
  • Global optimization
  • Multilinear functions

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Convex extensions and envelopes of lower semi-continuous functions'. Together they form a unique fingerprint.

Cite this