Gaining or Losing Perspective for Piecewise-Linear Under-Estimators of Convex Univariate Functions.

We study mixed-integer nonlinear optimization (MINLO) formulations of the disjunction x ∈ { 0 } ∪ [ ℓ , u ] , where z is a binary indicator for 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 c for operating an activity at level x in the operating range [ ℓ , u ] , and then, there is a further (convex) variable cost f(x). So the overall cost is c z + f (x) . In applied situations, there can be N 4-tuples (f , ℓ , u , c) , and associated (x, y, z), and so, the combinatorial nature of the problem is that for any of the 2 N choices of the binary z-variables, the non-convexity associated with each of the (f , ℓ , u) goes away. 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 . [ABSTRACT FROM AUTHOR]