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

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.