# What is wrong with this procedure to convert quadratic programming to convex quadratic programming?

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?

• Do you actually have a proof that your new constraints are convex? – Gamow Aug 30 '17 at 7:06

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$.
• @777 Inequality $ab \leq 0$: $(2,0)$ and $(0,2)$ satisfy it, not $(1,1)$. – Clement C. Aug 30 '17 at 13:24