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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2021
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]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11381/2905630`
##### Citazioni
• ND
• 0
• ND