Yet Another Math Programming Consultant: Getting rid of non-linearities

Sunday, May 1, 2022

Getting rid of non-linearities

In [1], an attempt was made to implement the following non-linear constraint:

$\frac{\displaystyle\sum_t \max\left\{\sum_i CF_{i,t}\cdot q_i -L_t, 0 \right\}}{\displaystyle\sum_t L_t} \le 0.015$ Obviously code like:

cfm = quicksum( max(quicksum(cf[i][t] * q[i] - L[t] for i in range(I)), 0) for t in range(T) /  quicksum(L[t] for t in range(T)) <= 0.015

is really not what we want to see. It is best, not to directly start up your editor and write Python code like this. Rather, get a piece of paper, and focus on the math.

There are two non-linearities: a division and a

$\max()$ function. Note that I am not sure which symbols are variables or parameters. I'll try to explain some possible cases below.

Division

Exogenous divisions of the form

$\frac{\color{darkred}x}{\color{darkblue}a}$ where

$\color{darkblue}a$ is a constant, are not an issue. This is just really a linear coefficient

$1/\color{darkblue}a$ . If you have

$\frac{\color{darkred}x}{\sum_i \color{darkblue}a_i}$ in the constraints, I would advice to calculate

$\color{darkblue}\alpha :=\sum_i \color{darkblue}a_i$ in advance, so we can simplify things to

$\frac{\color{darkred}x}{\color{darkblue}\alpha}$ It is a good habit to keep constraints as simple as possible, as they are more difficult to debug than parameter assignments.

If we have something like

$\frac{\color{darkred}x}{\color{darkred}y}$ (endogenous division) we need to be careful and worry about division by zero (or, more generally, that the expression can assume very large values if

$\color{darkred}y \approx 0$ ). If

$\color{darkred}y$ is a positive variable, we can protect things a bit by using a lower bound, say

$\color{darkred}y\ge 0.0001$ . This is difficult to do if

$\color{darkred}y$ is a free variable (we want a hole in the middle). If we have

$\frac{\color{darkred}x}{\sum_i\color{darkred}y_i}$ it may be better to write this as:

$\begin{align}&\frac{\color{darkred}x}{\color{darkred}z}\\ & \color{darkred}z= \sum_i \color{darkred}y_i \\ &\color{darkred}z\ge 0.0001 \end{align}$ at the expense of an extra variable and constraint. It has the additional advantage of making the model less non-linear (fewer non-linear variables, smaller non-linear part of the Jacobian). Note that we assumed here that

$\sum_i\color{darkred}y_i \ge 0$ . If this expression can assume both negative and positive values, this will not not work.

If the division is not embedded in other non-linear expressions, we often can multiply things out. E.g. if we have the constraint:

$\frac{\color{darkred}x}{\sum_i\color{darkred}y_i} \le 0.015$ then we can write:

$\color{darkred}x \le 0.015 \cdot \sum_i\color{darkred}y_i$ This is now linear. This is what can apply to our original constraint:

$\sum_t \max\left\{\sum_i CF_{i,t}\cdot q_i -L_t, 0 \right\} \le 0.015\cdot \sum_t L_t$

Max function

We can feed

$\max\{\color{darkred}x,0\}$ to a general-purpose NLP solver. However, this is dangerous. Although this function is continuous, it is non-differentiable at

$\color{darkred}=0$ .

In the special case

$\max\{\color{darkred}x,0\} \le \color{darkred}y$ we can write:

$\begin{align} \color{darkred}x &\le \color{darkred}y \\ 0 & \le \color{darkred}y\end{align}$ If

$\color{darkred}y$ represents an expression, you may want to use an extra variable to prevent duplication.

If we have

$\sum_i \max\{\color{darkred}x_i,0\} \le \color{darkred}y$ we can do:

$\begin{align} & \color{darkred}z_i \ge 0 \\ & \color{darkred}z_i \ge \color{darkred}x_i \\ &\sum_i \color{darkred}z_i \le \color{darkred}y \end{align}$ Note that the variables

$\color{darkred}z_i$ are a bit difficult to interpret. They can be larger than

$\max\{\color{darkred}x_i,0\}$ if the inequality is not tight. The reason I use

$\color{darkred}z_i \ge \max\{\color{darkred}x_i,0\}$ is that it is sufficient for our purpose and that

$\color{darkred}z_i = \max\{\color{darkred}x_i,0\}$ is just way more difficult to represent.

This is the reformulation we can apply to our original problem:

$\begin{align}&z_t \ge \sum_i CF_{i,t}\cdot q_i -L_t \\ & z_t \ge 0 \\ & \sum_t z_t \le 0.015\cdot \sum_t L_t \end{align}$ This is now completely linear: we have removed the division and the

$\max(.,0)$ function.