Piecewise-Linear Functions via SOS Variables

A piecewise-linear (PWL) function is specified by a sequence of breakpoints $(x_0, y_0), (x_1, y_1), \ldots, (x_n, y_n)$ with $x_0 < x_1 < \cdots < x_n$, connected by straight line segments. On the segment $[x_k, x_{k+1}]$, the graph is the line through $(x_k, y_k)$ and $(x_{k+1}, y_{k+1})$.

Any point $(x, f(x))$ on the graph lies on exactly one segment and can be written as a convex combination of its two endpoints. If $x \in [x_k, x_{k+1}]$, then for $t = \dfrac{x - x_k}{x_{k+1} - x_k} \in [0,1]$,

$$x = (1-t)\, x_k + t\, x_{k+1}, \qquad f(x) = (1-t)\, y_k + t\, y_{k+1}.$$

To prepare for a MIP encoding, introduce nonnegative weights $\lambda_0, \lambda_1, \ldots, \lambda_n$ — one per breakpoint — and write

$$x = \sum_{i=0}^n \lambda_i\, x_i, \qquad y = \sum_{i=0}^n \lambda_i\, y_i, \qquad \sum_{i=0}^n \lambda_i = 1, \qquad \lambda_i \geq 0.$$

Setting $\lambda_k = 1-t$, $\lambda_{k+1} = t$, and all other $\lambda_i = 0$ recovers the segment formula.

For example, with breakpoints $(0,0), (2,3), (5,9), (8,3)$ and $x = 4$: since $4 \in [2, 5]$, $t = (4-2)/(5-2) = 2/3$, so $\lambda_1 = 1/3$, $\lambda_2 = 2/3$, and $f(4) = (1/3)(3) + (2/3)(9) = 1 + 6 = 7$.