Explicit Convex and Concave Envelopes through Polyhedral Subdivisions

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.

Citation

Krannert Working Paper

Article

Download

View Explicit Convex and Concave Envelopes through Polyhedral Subdivisions