Linear programming with quadratic constraints 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. 
 A: 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}
A: 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: 


*

*$y_1 = 0$, $y_2 = 0$, $y_3 = 0$

*$x_1+x_2+x_3 = 0$, $y_2 = 0$, $y_3 = 0$

*$y_1 = 0$, $x_2 + x_3 = 0$, $y_3 = 0$

*$y_1 = 0$, $y_2 = 0$, $x_3 = 0$

*$x_1+x_2+x_3 = 0$, $x_2 + x_3 = 0$, $y_3 = 0$

*$x_1+x_2+x_3 = 0$, $y_2 = 0$, $x_3 = 0$

*$y_1 = 0$, $x_2 + x_3 = 0$, $x_3 = 0$

*$x_1+x_2+x_3 = 0$, $x_2 + x_3 = 0$, $x_3 = 0$


and the pick the minimum of all the solutions.
A: 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.
