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

.

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