# Non-linear optimization local or global solution

In an NLP, I have a constraint that I would like to formulate in a convex manner preferably without introducing binary variables and/or big M formulations if possible. The actual problem is non-convex and I am happy with a local solution but I want to avoid any integer variables as there is not a good choice of open-source solvers for nonlinear problems. But of course, if it is not possible to avoid binary variables then it should be fine. The issue is to reformulate IF-THEN-ELSE condition of the type below to determine the appropriate parameter to use: $$IF \hspace{0.5mm}\ \sum_{i=1}^{n}\left(x_i{\ c}_i^t\ \ -{\ L}_t\right)\ <0$$ Then $$\hspace{0.5mm}\ r_t\ =\ s_t \hspace{0.5mm}\ Else \hspace{0.5mm}\ r_t\ =\ g_t$$

where

• r, s , g and L are constant parameters (time dependent)
• $$x_i$$ is a vector of optimisation variables (continuous)
• $${\ c}_i^t$$ are coefficients of $$x_i$$

The actual constraint is given by: $$\sum_{t=1}^{T}{EP}_t=0\$$

where $${EP}_0\ =\ 0$$

$${EP}_1\ =\ \sum_{i=1}^{n}{x_ic_i^1} - L_1$$

$${EP}_2\ =\ \sum_{i=1}^{n}{x_ic_i^2} - L_2\ +\ {EP}_1\ r_1\$$

$${EP}_3\ =\ \sum_{i=1}^{n}{x_ic_i^3} - L_3\ +\ {EP}_2\ r_2\$$

$${EP}_t\ =\ \sum_{i=1}^{n}{x_ic_i^t} - L_t\ +\ {EP}_{t-1}\ r_t\$$

$$If\ {EP}_{t-1}\ <0\ then \hspace{0.5mm}\ r_t\ =\ s_t \hspace{0.5mm}\ Else \hspace{0.5mm}\ r_t\ =\ g_t$$

where

• $$r_t, \hspace{0.5mm}\ s_t , \hspace{0.5mm}\ g_t and \hspace{0.5mm}\ L_t$$ are constants
• $$0\leq x_i \leq 1$$ $$\hspace{5mm}\ i \in {1,2...n}$$
• $${\ c}_i^t$$ are coefficients of $$x_i$$
• Only $$x_i$$ are the optimisation variables

How can this constraint be reformulated either using Big M /binary variables or using some other formulation? I don't want to use IF in the constraint as it will make the problem hard to solve. Please note that there are a number of other nonlinear constraints in the model. I was thinking that we may be able to write it using min and max, e.g., $${EP}_t\ =\ \sum_{i=1}^{n}{x_ic_i^t}\ +\ min\left\{0,{EP}_{t-1}\ \right\}\ s_t\ \ +\ max\left\{0,{EP}_{t-1}\ \right\}\ g_t$$ and then introduce some auxiliary variables but I am not sure where to go next.

I have given a numerical example in the attached image which explains how this constraint is constructed and where we have determined value of x.

$$c = \begin{pmatrix} 1 & 20 & 30 & 40\\ 1 & 2 & 60 & 2\\ 5 & 3 & 2 & 1\\ 10 & 8 & 5 & 40\\ 3 & 6 & 2 & 3 \end{pmatrix} , \hspace{0.5mm}\ L = \begin{pmatrix} 30\\ 60\\ 30\\ 20\\ 1 \end{pmatrix} , \hspace{0.5mm}\ x = \begin{pmatrix} x_1\\ x_2\\ x_3\\ x_4 \end{pmatrix}, s = \begin{pmatrix} 0.001\\ 0.002\\ 0.003\\ 0.004\\ 0.005 \end{pmatrix} , g = \begin{pmatrix} 0.006\\ 0.050\\ 0.009\\ 0.010\\ 0.020 \end{pmatrix}$$

The above constraint will be satisfied for the following values of $$x = \begin{pmatrix} 0.363034965\\ 0.514820246\\ 0.539183467\\ 0.856864726\\ \end{pmatrix}$$

• As far as I can see the model is linear (besides the logical constraint) so adding the formulation with min and max in your proposal is going to end up being a big-M based MILP representation anyway (since you have to represent those operators somehow, and if you use MILP it will be a big-M method). Probably better to go for the obvious big-M model instead of hiding it in the min/max models. A convex reformulation is not possible. Apr 2 at 10:33
• Thank you @JohanLöfberg I have a number of other non-linear constraints in the model. I have just shown this constraint as it is causing me a problem. I don't know how to use Big M method in this case either. I have added more explanation in the question. Apr 2 at 10:54
• I came across this post on stackoverflow which uses something similar to min max: stackoverflow.com/questions/58756084/… Apr 2 at 10:56

Introduce a binary variable $$\delta_t$$ to represent which case it is and $$z_t$$ to represent the modelled product, and your MILP model of the piecewise-affine dynamics would be

$${EP}_t\ =\ \sum_{i=1}^{n}{x_ic_i^t}\ -L_t + z_t\\ {EP}_{t-1}\leq (1-\delta_t)M, -(1-\delta_t)M \leq z_t - s_t{EP}_{t-1}\leq (1-\delta_t)M\\ ~{EP}_{t-1}\geq -\delta_t M, -\delta_tM \leq z_t - g_t{EP}_{t-1}\leq \delta_t M$$

• Thank you @JohanLöfberg. I was wondering whether the last inequality should be written as: $-\delta_tM \leq z_t - g_t{EP}_{t-1}\leq \delta_t M$ and also the first equation should be: ${EP}_t\ =\ \sum_{i=1}^{n}{x_ic_i^t}\ -L_t + z_t$ Apr 5 at 11:44
• Yes, fixed typos Apr 5 at 12:00