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.