# 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.

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}

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.

• This would not be a feasible option since the problem is likely to scale up to 100+ variables so the number of constraints will also grow and solving multiple lps in that case would not make sense.What i have given above is just a scaled down version of the problem. Commented Nov 16, 2015 at 11:07

## 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.

• Your $i$ and $k$ should be the same (you don't need both), and then it matches the formulation I gave. Commented Jan 14, 2022 at 4:27