## 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.