Meaning of convex envelope | Babel Free

Definitions

1. Convex hull.
2. For a given set S⊆ℝⁿ and real-valued function f defined on the convex hull conv(S), the highest-valued convex function that underestimates or equals f over S.

Examples

“1965 [Holt Rinehart & Winston], Robert E. Edwards, Functional Analysis: Theory and Applications, Dover, 1995, Unabridged Corrected Edition, page 561, In E the closed convex envelope of a compact (resp. weakly compact) set is τ(E,E')-complete.”

“1987, H. G. Eggleston, S. Madan (translators), Nicolas Bourbaki, Topological Vector Spaces: Chapters 1–5, [1981, N. Bourbaki, Espaces Vectoriels Topologiques], Springer, page IR-10, Corollary 1. — The convex envelope of a subset A of E is identical with the set of linear combinations ∑ᵢλᵢx_i, where (x_i) is any finite family of points in A, the numbers λᵢ>0 for all i and ∑ᵢλᵢ=1.”

“The polytopes are, by definition, the convex envelopes of finite sets of points of an affine space.”

“One of the main reasons for the interest in convex envelopes is the fact that the set of global minimum points of f on S is contained in the set of global minimum points of conv_S(f) on S and the two minimum values coincide (see, e.g., [11, 17]). Hence, if the convex envelope were efficiently computable or available in closed form, one could replace the nonconvex problem of minimizing f on S with the convex problem of minimizing f on conv_S(f).”

“Tawarmalani and Sahinidis (2001) developed the convex envelope and concave envelope for x/y over a unit hypercube, compared it to the convex relaxation proposed by Zamora and Grosmmann (1998a), (1998b), (1999), proposed a semidefinite relaxation of x/y, and suggested convex envelopes for functions of the form f(x)y² and f(x)/y.”

“The concept of convex envelopes of nonconvex functions is a basic tool in theory and algorithms of global optimization, see e.g., Falk and Hoffman (1976), Horst and Tuy (1996), Horst et al. (2000).”

“Comparing the use of convex envelopes for bilinear and trilinear forms in building convex approximations for MINLPs motivated the study in [6], and comparisons involving more general functional forms motivate the present article.”

CEFR level