Gaining or Losing Perspective for Piecewise-Linear Under-Estimators of Convex Univariate Functions
share
We study MINLO (mixed-integer nonlinear optimization) formulations of the disjunction x∈{0}∪[ℓ,u], where z is a binary indicator of x∈[ℓ,u] (0 ≤ℓ <u), and y "captures" f(x), which is assumed to be convex and positive on its domain [ℓ,u], but otherwise y=0 when x=0. This model is very useful in nonlinear combinatorial optimization, where there is a fixed cost of operating an activity at level x in the operating range [ℓ,u], and then there is a further (convex) variable cost f(x). In particular, we study relaxations related to the perspective transformation of a natural piecewise-linear under-estimator of f, obtained by choosing linearization points for f. Using 3-d volume (in (x,y,z)) as a measure of the tightness of a convex relaxation, we investigate relaxation quality as a function of f, ℓ, u, and the linearization points chosen. We make a detailed investigation for convex power functions f(x):=x^p, p>1.
READ FULL TEXT