convex envelope

English

Noun

convex envelope (plural convex envelopes)

1. (mathematical analysis, of a set) 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 $\tau (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 $\sum _{i}\lambda _{i}x_{i}$, where $(x_{i})$ is any finite family of points in A, the numbers $\lambda _{i}>0$ for all i and $\sum _{i}\lambda _{i}=1$.

   • 2010, Marcel Berger, Geometry Revealed: A Jacob's Ladder to Modern Higher Geometry, Springer, page 505:

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

2. (mathematics, optimisation theory, of a function on a set) For a given set $S\subseteq \mathbb {R} ^{n}$ and real-valued function f defined on the convex hull conv(S), the highest-valued convex function that underestimates or equals f over S.
   • 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:

     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, 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:

     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.

   • 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:

     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).

   • 2012, Petro Bilotti, Sonia Cafieri, Jon Lee, Leo Liberti, Andrew J. Miller, On the Composition of Convex Envelopes for Quadrilinear Terms:

     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.

Usage notes

(optimisation theory): Called the convex envelope of f on S. Notations include ${\text{conv}}_{S}(f)$ and, assuming S is understood, ${\hat {f}}$.

Synonyms

• (optimisation theory): lower convex envelope

Coordinate terms

• concave envelope
• upper concave envelope