Linear programming with quadratic constraints

Question

I have a given set of variables: $x_1,y_1,x_2,y_2,x_3,y_3$

The objective function is to minimize the sum of these with quadratic equality constraints:

$y_1(x_1+x_2+x_3)$=0

$y_2(x_2+x_3)$=0

$y_3(x_3)$=0

There are other inequality constraints which are linear so I wont mention them hear. I want to know how these equality constraints can be converted into linear constraints. If they cant be converted what other method can I use such that I can guarantee optimality of the solution.

All variables are real variables between 0 and 1.

Answer 1

This would be too long for a comment, I think. I am not sure, whether there is some kind of standard method for doing what you want, but I guess you could possibly convert your problem into a list of linear programs:

1. $y_1 = 0$, $y_2 = 0$, $y_3 = 0$
2. $x_1+x_2+x_3 = 0$, $y_2 = 0$, $y_3 = 0$
3. $y_1 = 0$, $x_2 + x_3 = 0$, $y_3 = 0$
4. $y_1 = 0$, $y_2 = 0$, $x_3 = 0$
5. $x_1+x_2+x_3 = 0$, $x_2 + x_3 = 0$, $y_3 = 0$
6. $x_1+x_2+x_3 = 0$, $y_2 = 0$, $x_3 = 0$
7. $y_1 = 0$, $x_2 + x_3 = 0$, $x_3 = 0$
8. $x_1+x_2+x_3 = 0$, $x_2 + x_3 = 0$, $x_3 = 0$

and the pick the minimum of all the solutions.

Answer 2

Each of your quadratic constraints is a product of linear expressions equal to zero, and you can think of these as disjunctions: \begin{align} y1 = 0 &\lor x1+x2+x3 =0\\ y2 = 0 &\lor x2+x3=0\\ y3 = 0 &\lor x3=0 \end{align} Now introduce binary variables $z1,z2,z3$ (one for each disjunction) and the following linear constraints: \begin{align} y1 &\le z1 \\ x1+x2+x3 &\le 3(1-z1)\\ y2 &\le z2\\ x2+x3 &\le 2(1-z2)\\ y3 &\le z3\\ x3 &\le 1-z3 \end{align} These constraints, together with the variable bounds, enforce the following implications: \begin{align} z1=0&\implies y1 =0 \\ z1=1&\implies x1+x2+x3 =0\\ z2=0&\implies y2 =0\\ z2=1&\implies x2+x3 =0\\ z3=0&\implies y3 =0\\ z3=1&\implies x3 =0 \end{align}

Answer 3

Yes, you can convert them into equivalent linear equations.

For every equation you have of the form: $$y_i(x_1+\ldots+x_n) = 0$$

introduce a brand new variable $z_k$. Replace your quadratic equation with the following equations:

$$z_k \in\{0,1\}\\ y_i \leq z_k\\ (x_1+\ldots+x_n) \leq n(1-z_k)$$

Together, these three equations are equivalent to your original equation, so if your objective is optimized with respect to these constraints, you will have a solution to your original problem. The only issue might be if you can't smoothly optimize over boolean variables like $z_k$.

Why are they equivalent? Note that all of your variables are in $[0,1]$. The equation variables $z_k$ are binary-valued: 0 or 1. When $z_k=0$, it forces $y_i=0$ and puts no constraint at all on $(x_1+\ldots+x_n)\leq n$, because the sum of $n$ $[0,1]$ variables is already less than or equal to $n$. In contrast, when $z_k=1$, it puts no constraint on $y_i\leq 1$, but forces $x_1=x_2=\ldots=x_n=0$ because it forces the sum of $n$ variables in $[0,1]$ to be less than or equal to zero.