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