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.
Exact and approximate results for convex envelopes of special structured functions over simplices / Locatelli, M.. - In: JOURNAL OF GLOBAL OPTIMIZATION. - ISSN 0925-5001. - (2021). [10.1007/s10898-021-01112-0]
Exact and approximate results for convex envelopes of special structured functions over simplices
Locatelli M.
2021-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.