2

I want to check if $(0,1,2)$ is the solution to a following problem: $$x_3\to \min,$$ $$x_1^2+2x_1x_2+2x^2_2-2x_1-x_2-x_3+1\geq 0,$$ $$x_1^2+x_2^2-x_1+x_2-x_3\leq 0,$$ $$x_1^2+x_1-4x_2-x_3+6\leq 0,$$ $$x_1,x_2,x_3\geq 0.$$ Any ideas on how to approach this problem?

user408281
  • 103
  • 5
  • I don't really understand the question. 1) By "$x_3 \rightarrow \mathrm{min}$" you mean that you are looking for the triple with minimal $x_3$? 2) How do you know there is exactly one solution? 3) Are you looking for integer solutions of your problem? 4) There is an index missing in the second displayed formula. – Giovanni De Gaetano Jan 19 '17 at 07:54
  • I want to minimize function $f(x_1,x_2,x_3)=x_3$. I'm looking for solutions over $\mathbb{R}^3$ – user408281 Jan 19 '17 at 07:55
  • You could start by checking the KKT conditions (which are necessary but not sufficient). However, proving optimality requires ad-hoc reasoning for nonconvex problems like these. – LinAlg Jan 19 '17 at 09:48
  • The accepted solution assumes integrality while this is not part of this question. If integrality is not assumed, the accepted answer is at least incomplete. Please clarify. – LinAlg Jan 19 '17 at 20:09

1 Answers1

0

I assume that you are only looking for integer solutions. Then it is enough to show that no solution with $x_3\in \{0,1\}$ is possible.

Assume $x_3=1$, then the third and fourth displayed formulae become $$x_1 \geq x_1^2 +x_2^2 +x_2 -1,$$ and $$4x_2 \geq x_1^2 + x_1 +5.$$

Put together they imply $$4x_2 \geq x_1^2 +x_2^2+x_2+4,$$ therefore $$3x_2 \geq 4 +x_2^2.$$

And it is easy to see that the latter inequality has not integer solution. The case $x_3=0$ proceeds along the same lines.\

If you are not only looking at integer solutions, this method implies $$x_3 \geq \frac{15}{8}.$$

Giovanni De Gaetano
  • 3,889