Dictionary

convex envelope en · NOUN

Meanings

1. (of a set) Convex hull.
   • 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. 2010, Marcel Berger, Geometry Revealed: A Jacob's Ladder to Modern Higher Geometry, Springer, page 505:
   • 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.
2. (of a function on a set, qualifier: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.
   • 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). 2005, Nguyen Van Thoai, “4: General Quadratic Programing”, in Charles Audet, Pierre Hansen, Giles Savard, editors, Essays and Surveys in Global Optimization, Springer, page 120:
   • 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). 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:
   • 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. 2012, Petro Bilotti, Sonia Cafieri, Jon Lee, Leo Liberti, Andrew J. Miller, On the Composition of Convex Envelopes for Quadrilinear Terms:
   • 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. 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, editors, European Symposium on Computer Aided Process Engineering-14: 37th European Symposium of the Working Party, Elsevier, page 25:

Forms

Coordinates

upper concave envelope · concave envelope

Synonyms

lower convex envelope (optimisation theory)