Lifting a 3rd order polynomial into a higher dimensional space

Question

An MINLP from a paper I am reading has the following expression in its constraints:

Where from left to right:

$p_{l,s}$: continuous variable

$z_l$: binary variable

$b_l$: constant

$\Delta \theta_{l,s}$: continuous variable

$\lambda_l$: binary variable

$u_l$: binary variable

The authors of this paper replaces the second term with a continuous variable $\zeta$ as shown here:

The authors then mention:

By substituting this new variable for the third order polynomial, we are lifting the third order polynomial equation into a higher dimensional space and overcoming its nonlinearity.

What does that mean? what does overcoming the nonlinearity mean in this context?

Answer 1

Products of binary variables can be expressed as the logical and operation. The MILP formulation of that introduces a new binary variable. We overcome "non linearity" by having more dimensions and formulating a linear constraint in those higher dimension that when projected onto the original variables captures the non-linearity. Here is an example involving a product of {-1,0,1} originally we had 2 variables in {-1,0,1}. We introduced another variable so we had 3 variables in {-1,0,1}. Then we expressed those variables in {-1,0,1} as the difference of two booleans. So we went from the $\mathbb{Z}^2$ to the $\mathbb{Z}^6$ but got rid of all the non-linearity.