0

I have a quadratic constraint which I want to linearise.

$x_1x_2=0$ where $0\leqslant x_1,x_2\leqslant1$.

What is the best way to do this?

José Carlos Santos
  • 427,504
MKC
  • 1

1 Answers1

-1

The region described by $0\le x_1,x_2\le 1$ is a square and the condition $x_1x_2=0$ is equivalent to "$x_1=0$ or $x_2=0$" which restricts the solution space to the left and lower edges of the square. The smallest convex set containing these two edges is the triangle described by $x_1+x_2\le 1$.

Depending on your optimization problem (which you didn't tell us) it may be a good or a horrible idea to linearize the condition by $x_1+x_2\le 1$.

If this doesn't answer your question, please edit your post to clarify what you are asking for and include the full description of the optimization problem you are trying to solve or linearize.

Christoph
  • 24,912
  • $x_1=x_2=\frac{1}{2}$ is feasible for ${ 0 \leq x_1,x_2 \leq 1, x_1+x_2 \leq 1}$ but violates the original constraint $x_1 x_2 =0$. Even though you somewhat strengthen the formulation, your method does not model the intial constraint. – YukiJ Sep 21 '18 at 09:24
  • I didn't claim it would. Of course a triangle contains more than just two of its edges. If you want a convex set contained in $x_1x_2=0$, you are left with the origin. – Christoph Sep 21 '18 at 09:26
  • I want the solution to be either of the three solutions $(x_1,x_2)={(1,0),(0,1),(0,0)}$ without using binary constraints on $x_1$ and $x_2$. – MKC Sep 21 '18 at 09:45
  • You can not enforce this using linear conditions. The convex hull of those three points is the triangle I described and you can't do any better using linear constraints. – Christoph Sep 21 '18 at 09:47