Exact and approximate results for convex envelopes of special structured functions over simplices

In this paper we describe how to derive the convex envelope of a function f over the n-dimensional unit simplex Δ n at different levels of detail, depending on the properties of function f, by starting from its definition as the supremum of all the affine underestimators of f over Δ n. At the first level we are able to derive the closed-form formula of the convex envelope. At the second level we are able to derive the exact value of the convex envelope at some point x∈ Δ n, and a supporting hyperplane of the convex envelope itself at the same point, by solving a suitable convex optimization problem. Finally, at the third level we are able to derive an underestimating value which differs from the exact value of the convex envelope at some point x∈ Δ n by at most a given threshold δ. The underestimation is obtained by solving a suitable LP problem and may lead also to a convex piecewise linear underestimator of f.