Explicit convex and concave envelopes through polyhedral subdivisions

Mohit Tawarmalani, Jean Philippe P. Richard, Chuanhui Xiong

Research output: Contribution to journalArticlepeer-review

46 Scopus citations

Abstract

In this paper, we derive explicit characterizations of convex and concave envelopes of several nonlinear functions over various subsets of a hyper-rectangle. These envelopes are obtained by identifying polyhedral subdivisions of the hyper-rectangle over which the envelopes can be constructed easily. In particular, we use these techniques to derive, in closed-form, the concave envelopes of concave-extendable supermodular functions and the convex envelopes of disjunctive convex functions.

Original languageEnglish (US)
Pages (from-to)531-577
Number of pages47
JournalMathematical Programming
Volume138
Issue number1-2
DOIs
StatePublished - Apr 2013
Externally publishedYes

Keywords

  • 52A27
  • 90C11
  • 90C26
  • Mathematics Subject Classification: 47N10

Fingerprint

Dive into the research topics of 'Explicit convex and concave envelopes through polyhedral subdivisions'. Together they form a unique fingerprint.

Cite this