Convex and Concave Relaxations Given a convex set and a function , a function is said to be a convex relaxation (or convex underestimator) of f on Z if it is convex and
A function is said to be a concave relaxation (or concave overestimator) of f on Z if it is convex and
Factorable Function A function is said to be factorable if it can be formed from a finite recursive composition of binary sums, binary products and univariate functions with known convex and concave relaxations.
Factorable functions cover a quite general class of functions. The simplest subclass of factorable functions are those defined without recursion, e.g., :
where , and .
Convex and concave relaxations may be nonsmooth and therefore subgradients are needed:
Subgradient Let be a nonempty convex set, $ be a convex function, and $ be a concave function. A vector is called a subgradient of u at if
A vector is called a subgradient of o at if
Existence of subgradients on the interior of Z is guaranteed, and for differentiable convex and concave functions the unique subgradient is the gradient.