Piecewise linear approximation

Authors: Tianhong Tan, Shoudong Zhu (CHEME 6800, 2021 Fall)

Introduction

Currently, approximating a complex non-linear function or smooth curve is very common in industry area. Like the very popular one, piecewise linear approximation, which is applied in a variety of real-world areas, such as signal processing and image processing in electronics information industry, pattern recognition in AI area. The problem of piecewise linear approximation can be classified by which type of norms applied in approximating process, whether the length of segments is fixed or not and whether the approximation is continuity or discontinuity. We can use piecewise linear approximation to represent any non-linear or linear function by any accuracy order by any accuracy by adding more nodes or segments until the accuracy is met. The meaning of piecewise linear approximation's existence is it allow us to transform non-linear problem to be solved by linear formation, which is easier to be executed by machine and the amount of calculation is acceptable.

Theory, Methodology & Algorithms

Theory

For a function $f(x)$ in a finite range $[x_{1},x_{n}]$, one can find $n$ sampling points $x_{1},x_{2},...,x_{n}$ to evaluate the function values. Then the $f(x)$ can be approximated by a series of linear segments $[(x_{i},f(x_{i})),(x_{i+1},f(x_{i+1}))]$, where $i=1,2,...,n-1$. Any given value $x'$ between $x_{i}$ and $x_{i+1}$ can be written as the following form:

$x'=\lambda x_{i}+(1-\lambda )x_{i+1}$ (1)

$\lambda$ is a unique number between $0$ and $1$.

The approximation of $f(x')$ is calculated by a convex combination of $f(x_{i})$ and $f(x_{i+1})$:

$f_{a}(x')=\lambda f(x_{i})+(1-\lambda )f(x_{i+1})$ (2)

Methodology & Algorithms

For the ease of applications in a MILP solver, the above formulation is further developed to include both binary and continuous variables with several constraints to force the $x'$ values become associated with the neighboring pair of consecutive break points. The constraints are listed below:

$\sum _{i=0}^{n}h_{i}=1$ (3)

$\alpha _{i}\leq h_{i-1}+h_{i}$ $(i=1,2,...,n)$ (4)

$x=\sum _{i=1}^{n}\alpha _{i}x_{i}$ (5)

$f_{a}=\sum _{i=1}^{n}\alpha _{i}f(x_{i})$ (6)

(4) indicates that only one $h$ takes the value of $1$ and all the other $h$'s are $0$. Therefore, (5) imposes that the only $\alpha$'s which is not $0$ are $\alpha _{i}$ and $\alpha _{i+1}$, which are corresponding to the two neighbors of $x'$: $x_{i}$ and $x_{i+1}$. (6) and (7) ensure that $\alpha _{i}=\lambda$ and $\alpha _{i+1}=1-\lambda$, which is consistent with the expression of the approximation $f_{a}$ in (2) .

The above formulation utilizes the idea of Special Ordered Sets (SOSs), which are powerful tools to model piecewise linear approximation problems . They are defined as ordered sets of variables. In type 1 SOS (S1), only one variable can be non-zero, and $h_{i}$'s in (3) form an S1. In type 2 SOS (S2), only two neighboring variables can be non-zero, and $\alpha _{i}$'s in (4) form an S2.

Numerical Example

Consider the trigonometric function $f(x)=sin(x),-\pi \leq x\leq \pi$, as an example. The approximation straight lines are very close to the original function with only 9 sampling points.