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

Abstract: We study MINLO (mixed-integer non-linear optimization) formulations of the disjunction x ∈ {0} ∪ [l, u], where z is a binary indicator of x ∈ [l,u] (0 ≤ l < u), and y "captures" f(x), which is assumed to be convex and positive on its domain [l, u], but otherwise y=0 when x=0. This model is very useful in non-linear combinatorial optimization, where there is a fixed cost of operating an activity at level x in the operating range [l, 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, l, u, and the linearization points chosen. We make a careful investigation for convex power functions f(x) := xp, p > 1.

This is joint work with Daphne Skipper, Emily Speakman, and Luze Xu.

game theorymachine learningmathematical softwarecomputer science theorycombinatoricsoptimization and control

Audience: researchers in the topic

---

Mixed Integer Programming Workshop 2021

Series comments: The 18th Mixed Integer Programming Workshop will be held online on May 24-27, 2021.

It will feature 21 distinguished invited speakers covering most aspects of Mathematical Optimization, an interactive, gamified MIP student poster session with 50 posters, and a casual business meeting.

Registration is free of charge. Register here: fico.zoom.us/webinar/register/2416186463858/WN_DVLhGOToQkKyvKYPiA4cQw

Find the website of MIP2021 at sites.google.com/view/mipworkshop2021/.

---