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