Convert a piecewise linear non-convex function into a linear optimisation problem.

Solution 1:

There are many ways to do this. Here are three:

Option 1

Let $y_i$ be a binary that equals $1$ if and only if $x$ is in the $i^{th}$ interval ($i\in \{[0,1],[1,2],[2,3]\}$). The idea is then to express $x$ as a convex combination of the extreme points of the intervals. Therefore, we introduce variables $\lambda_0, \lambda_1,\lambda_2,\lambda_3 \in \mathbb{R}^+$ with which we will achieve this.

The objective function is $$ f(0)\lambda_0+f(1)\lambda_1+f(2)\lambda_2+f(3)\lambda_3=\lambda_0+\lambda_2+1.5\lambda_3 $$

and the constraints are \begin{align*} &y_1+y_2+y_3 = 1\\ &x = 0\lambda_0+\lambda_1+2\lambda_2+3\lambda_3\\ &\lambda_0+\lambda_1+\lambda_2+\lambda_3=1\\ &y_1\le \lambda_0+\lambda_1\\ &y_2\le \lambda_1+\lambda_2\\ &y_3\le \lambda_2+\lambda_3\\ &y\in \{0,1\}\\ &\lambda\ge 0 \end{align*}

Option 2

Alternatively, you can write the objective function as $$ f=(1-x_1)+(x_2)+(\frac{x_3}{2}) $$ with constraints $$ x=x_1+x_2+x_3\\ x\le 3\\ y_1\le x_1 \le 1\\ y_2\le x_2 \le y_1\\ 0 \le x_3 \le y_2\\ y_1,y_2\in \{0,1\} $$

$y_1$ and $y_2$ are binaries that equal $1$ if and only if variables $x_1$ and $x_2$ reach their upper bound. This ensures that, for example, if $x=1.5$, the solver has to fix $x_1=1$ and $x_2=0.5$.

Option 3

Write the function as follows: $$ f=(y_1-x_1)+(x_2)+(\frac{x_3}{2}+y_3) $$ subject to $$ x=(x_1)+(x_2+y_2)+(x_3+2y_2)\\ y_1+y_2+y_3=1\\ 0\le x_1\le y_1\\ 0\le x_2\le y_2\\ 0\le x_3\le y_3\\ y_1,y_2,y_3\in \{0,1\} $$

This time, binaries $y_i$ equal $1$ if and only if $x$ is in the $i^{th}$ interval ($i\in \{[0,1],[1,2],[2,3]\}$).