-3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Do you actually have a proof that your new constraints are convex? $\endgroup$ – Gamow Aug 30 '17 at 7:06
3
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ so the problem is with the equality? if I had an inequality there would that be ok? $\endgroup$ – 1.. Aug 30 '17 at 7:25
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Aug 30 '17 at 7:27
  • $\begingroup$ 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?)? $\endgroup$ – 1.. Aug 30 '17 at 7:27
  • $\begingroup$ @777 Inequality $ab \leq 0$: $(2,0)$ and $(0,2)$ satisfy it, not $(1,1)$. $\endgroup$ – Clement C. Aug 30 '17 at 13:24
  • 1
    $\begingroup$ @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. $\endgroup$ – Clement C. Aug 30 '17 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.