concave envelope

concave envelope (plural concave envelopes)

1. (mathematics, optimisation theory, of a function on a set) For a given set ${\displaystyle S\subseteq \mathbb {R} ^{n}}$ and real-valued function f defined on the convex hull conv(S), the lowest-valued concave function that overestimates or equals f over S.
   • 1988, Ferenc Forgó, Nonconvex Programming, page 33:

     No immediate use of Theorem 4 can be made computationally since, with the exception of a few special cases (e.g. rectangular S and separable f) it is very hard to construct concave envelopes and convex hulls.

   • 2004, C. A. Meyer, C. A. Floudas, “Trilinear Monomials with Positive or Negative Domains: Facets of the Convex and Concave Envelopes”, in Christodoulos A. Floudas, Panos M. Pardalos, editors, Frontiers in Global Optimization, Springer,, page 327:

     Explicit expressions defining the facets of the convex and concave envelopes for trilinear monomials, with positive or negative bounded domains for each variable, are derived in this paper.

   • 2012, Joseph Geunes, Demand Flexibility in Supply Chain Planning‎, Springer (Kluwer Academic), page 20:

     The cost of this order plan is linear in price, and the associated line must form a segment of the piecewise linear concave envelope.

• (optimisation theory): upper concave envelope

• convex envelope