Convert multiplying two continuous variables to linear form

Question

I am working on an optimization model. I encountered a problem, and I don't know how I can solve it. I will deeply appreciate any help. Suppose $x_1$ and $x_2$ are two non-negative continuous variables, and I have a constraint like $x_1 \cdot x_2 = 0$, do you know how can I convert this constraint to a linear constraint? It is simple if both variables are integers.

Thanks.

Answer 1

Admittedly, $x_1x_2=0$ is a poor example, but in general you can convert $x_1x_2=c$ to a linear constraint, namely $\ln(x_1)+\ln(x_2)=\ln(c)$.

Hope that helped!

Answer 2

This was a type of problem I found a couple of years back when I was getting into exploring Non-Linear Programming, it can be made solvable by doing the following:

Substitute $x_1x_2=y_1^2-y_2^2$ to get the following constraint: $y_1^2-y_2^2=0$

Then, add these two additional constraints:

$$y_1=\frac{x_1+x_2}{2}$$ $$y_2=\frac{x_1-x_2}{2}$$

With $x_1$ and $x_2$ being unrestricted

Or, we can do the following:

Substitute $x_1x_2=y_1$ such that we get the following constraint $y_1=0$, and then add the following constraint: $$\ln(y_1)=\ln(x_1)+\ln(x_2)$$ with $x_1,x_2>0$.

However, since we’re trying to make $y_1=0$, then the latter substitution is not possible for this specific problem as there exists no value that would make that true. (However, it is good to keep that substitution handy for when it could be applicable for another problem).

Answer 3

The fact that $x_1, x_2 \ge 0$ and that $x_1 x_2 = 0$ shows that your point $(x_1, x_2)$ lives on the boundary of the first quadrant, which is the union of the two half-lines $\{ (x_1, 0) \mid x_1 \ge 0\}$ and $\{ (0, x_2) \mid x_2 \ge 0\}$. This means that you should split your optimization problem into two subproblems corresponding to the two half-lines seen above, find the optima for each of these, and then finally study these two families of optima to find the global ones.

The mistake in your approach comes from jumping straight at linearizing the constraint instead of looking at it geometrically and decomposing it into its natural underlying connected components.