convex envelope

Noun

convex envelope (plural convex envelopes)

1. Convex hull.
   • 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.
   • 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.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
2. (optimisation theory) 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.
   • 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...2004, Fabio Tardella, “On the existence of polyhedral convex envelopes”, in Christodoulos A. Floudas, Panos M. Pardalos, editors, Frontiers in Global Optimization, Springer (Kluwer Academic), page 564
   • 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...2004, C. A. Floudas, I. G. Akrotiriankis, S. Caratzoulas, C. A. Meyer, J. Kallrath, “Global Optimization in the 21st Century: Advances and Challenges”, in Ana Paula Barbosa-Póvoa, Henrique Matos...