<p>The constraint $x_i x_j = y_{ij}$ isn't convex. Indeed, even the simpler constraint $ab = 8$ isn't convex. Let $C = \{(a,b) : ab = 8\}$. Then $(4,2),(2,4) \in C$ but $(3,3) \notin C$.</p>

CC BY-SA 3.0
2017-08-30T07:25:38.420Z
so the problem is with the equality? if I had an inequality there would that be ok?
Turbo
CC BY-SA 3.0
2017-08-30T07:27:10.013Z
The usual rule is one question per post. I suggest approaching this in the following way: these ideas don't work (otherwise someone else would have considered them already), and it just remains to find out why. Usually the answer is within reach, and we expect you to make some effort figuring it out on your own. We don't owe you anything.
Yuval Filmus
CC BY-SA 3.0
2017-08-30T07:27:59.290Z
sorry I think you answered everything in your post. the issue is with equality right (if I had inequality then that would be ok correct?)?
Turbo
CC BY-SA 3.0
2017-08-30T13:24:07.627Z
@777 Inequality  $ab \leq 0$: $(2,0)$ and $(0,2)$ satisfy it, not $(1,1)$.
Clement C.
CC BY-SA 3.0
2017-08-30T13:33:40.593Z
@ClementC. 0 is degenerate case.
Turbo
CC BY-SA 3.0
2017-08-30T13:40:44.573Z
@777 Are you serious? Are you going to argue on a case-by-case basis, ruling out things one at a time? You make a general statement, there is a counterexample... But sure, in that case: if inequalities were convex, combine two to get an equality; hence, equalities must be convex constraints too. Except they aren't.
Clement C.
CC BY-SA 3.0
2017-08-30T20:12:13.413Z
I just felt Yuval's answer is good enough. but yours is ok too.
Turbo
CC BY-SA 3.0
2017-08-30T07:12:15.110Z
2017-08-30T07:12:15.110Z
Yuval Filmus
<p>Consider the feasibility quadratic program with constraint
$$\sum_{i=1}^nc_{i1}x_{i}\leq \ell_1$$
$$\vdots$$
$$\sum_{i=1}^nc_{it}x_{i}\leq \ell_t$$
$$\sum_{i,j=1}^na_{ij}x_{i}x_{j}+\sum_{i=1}^nb_{i}x_{i}&lt;=m$$
$$0\leq x_i\leq m_i$$ where $x_i$ are unknown.</p>

<p>The constraint may not be convex and solving this is not in $P$.</p>

<p>Now say I convert to following program.
$$\sum_{i=1}^nc_{i1}x_{i}\leq \ell_1$$
$$\vdots$$
$$\sum_{i=1}^nc_{it}x_{i}\leq \ell_t$$
$$\sum_{i,j=1}^na_{ij}y_{ij}+\sum_{i=1}^nb_{i}x_{i}&lt;=m$$
$$y_{ij}=x_ix_j$$
$$0\leq x_i\leq m_i$$ where $x_i,y_{ij}$ are unknown.</p>

<ol>
<li><p>Each of the constraint is convex and so is solving this in $P$?</p></li>
<li><p>At least when $a_{ij}=0$ if $|a_{ii}|+|a_{jj}|&gt;0$ (and so each quadratic constraint is independent and is either a parabola or a hyperbola) is it in $P$?</p></li>
<li><p>If 1. and 2. fail at least if $n=1$ and $a_1b_1\neq0$ or $n=2$ and $b_1=b_2=0$ is it in $P$?</p></li>
</ol>

<p>In general when can I use these tricks? Why cannot I use it here?</p>

CC BY-SA 3.0
2017-08-30T07:06:25.907Z
Do you actually have a proof that your new constraints are convex?
Gamow
<ds.algorithms><linear-programming><p-vs-np><convex-optimization><semidefinite-programming>
What is wrong with this procedure to convert quadratic programming to convex quadratic programming?
Turbo
# What is wrong with this procedure to convert quadratic programming to convex quadratic programming?

(Asked by: username_0 on 2017-08-30)

Consider the feasibility quadratic program with constraint
$$\sum\_{i=1}^nc\_{i1}x\_{i}\leq \ell\_1$$
$$\vdots$$
$$\sum\_{i=1}^nc\_{it}x\_{i}\leq \ell\_t$$
$$\sum\_{i,j=1}^na\_{ij}x\_{i}x\_{j}+\sum\_{i=1}^nb\_{i}x\_{i}<=m$$
$$0\leq x\_i\leq m\_i$$ where $x\_i$ are unknown.

The constraint may not be convex and solving this is not in $P$.

Now say I convert to following program.
$$\sum\_{i=1}^nc\_{i1}x\_{i}\leq \ell\_1$$
$$\vdots$$
$$\sum\_{i=1}^nc\_{it}x\_{i}\leq \ell\_t$$
$$\sum\_{i,j=1}^na\_{ij}y\_{ij}+\sum\_{i=1}^nb\_{i}x\_{i}<=m$$
$$y\_{ij}=x\_ix\_j$$
$$0\leq x\_i\leq m\_i$$ where $x\_i,y\_{ij}$ are unknown.

1. Each of the constraint is convex and so is solving this in $P$?
2. At least when $a\_{ij}=0$ if $|a\_{ii}|+|a\_{jj}|>0$ (and so each quadratic constraint is independent and is either a parabola or a hyperbola) is it in $P$?
3. If 1. and 2. fail at least if $n=1$ and $a\_1b\_1\neq0$ or $n=2$ and $b\_1=b\_2=0$ is it in $P$?

In general when can I use these tricks? Why cannot I use it here?

**Tags:** ds.algorithms, linear-programming, p-vs-np, convex-optimization, semidefinite-programming

> **Comments:**
> **username_1**: Do you actually have a proof that your new constraints are convex?  

---

## 1 answers

### Answer by username_2 on 2017-08-30. Score: 3 | Accepted answer

The constraint $x\_i x\_j = y\_{ij}$ isn't convex. Indeed, even the simpler constraint $ab = 8$ isn't convex. Let $C = \{(a,b) : ab = 8\}$. Then $(4,2),(2,4) \in C$ but $(3,3) \notin C$.

> **Comments:**
> **username_0**: so the problem is with the equality? if I had an inequality there would that be ok?  
> **username_2**: The usual rule is one question per post. I suggest approaching this in the following way: these ideas don't work (otherwise someone else would have considered them already), and it just remains to find out why. Usually the answer is within reach, and we expect you to make some effort figuring it out on your own. We don't owe you anything.  
> **username_0**: sorry I think you answered everything in your post. the issue is with equality right (if I had inequality then that would be ok correct?)?  
> **username_3**: @777 Inequality  $ab \leq 0$: $(2,0)$ and $(0,2)$ satisfy it, not $(1,1)$.  
> **username_0**: @ClementC. 0 is degenerate case.  
> **username_3**: @777 Are you serious? Are you going to argue on a case-by-case basis, ruling out things one at a time? You make a general statement, there is a counterexample... But sure, in that case: if inequalities were convex, combine two to get an equality; hence, equalities must be convex constraints too. Except they aren't.  
> **username_0**: I just felt Yuval's answer is good enough. but yours is ok too.  

---

