Convex envelopes for edge-concave functions

Deterministic global optimization algorithms frequently rely on the convex underestimation of nonconvex functions. In this paper we describe the structure of the polyhedral convex envelopes of edge-concave functions over polyhedral domains using geometric arguments. An algorithm for computing the facets of the convex envelope over hyperrectangles in R-3 is described. Sufficient conditions are described under which the convex envelope of a sum of edge-concave functions may be shown to be equivalent to the sum of the convex envelopes of these functions.