# Do you agree that the following domain is not convex?

The domain is given as $$x_1,x_2,y_1,y_2 \in \mathbb{R}$$ with: $$x_1-y_1^2-4 \geq0,\quad x_2-y_2^2-4 \geq 0, \quad x_1\leq 10 ,\quad x_2 \leq 10$$ We must prove this is convex. This is my approach:

I have $$x_3 = \theta x_1 + (1-\theta)x_2$$ and $$y = \theta y_1 + (1-\theta)y_2$$. Then we have

$$f = x_3-y_3^2-4 = \theta x_{1} + x_{2} \left(- \theta + 1\right) - \left(\theta y_{1} + y_{2} \left(- \theta + 1\right)\right)^{2} - 4 \geq 0 , \quad \theta \in [0,1]$$

Then we evaluate the Hessian to be:

$$H =\left[\begin{matrix}0 & 0 & 0 & 0\\0 & 0 & 0 & 0\\0 & 0 & - 2 \theta^{2} & 2 \theta \left(\theta - 1\right)\\0 & 0 & 2 \theta \left(\theta - 1\right) & - 2 \left(\theta - 1\right)^{2}\end{matrix}\right]$$ The eigenvalues are $$\lambda_{1,2,3} = 0$$ and $$\lambda_4 = - 2 \left(2 \theta^{2} - 2 \theta + 1\right)$$ But for $$\theta = 0$$ we have $$\lambda_4 = -2$$ such that the Hessian is not positive semidefinite for all $$\theta \in [0,1]$$.

I am pretty certain that the domain is thus not convex. Would you agree? Have I perhaps missed something? The reason I ask, is that the task asks us to prove that the domain is convex yet I prove it not to be. Thank you very much for your time.

• To the Downvoters, the OP cannot correct a problem of he/she is not made aware of it. Please try to leave a comment explaining whatever issues you see, if you downvote a post. – Devashish Kaushik Sep 29 '18 at 15:19
• Where does your domain live in? $\Bbb{R}$ , $\Bbb{R^n}$, $n=$ ? – dmtri Sep 29 '18 at 15:23
• The question I'm answering only states $\mathbb{R}$. I'm not sure if it was perhaps intended otherwise. – Yes Sep 29 '18 at 15:26
• @Yes I suppose you are rather expected to consider the set $A:=\{\,(x,y)\in\Bbb R^2\mid x-y^2-4\ge 0\land x\le 10\,\}$ and show that $A$ is convex. But that is rather a mere guess based on what might have happened to the formulation "during transport" – Hagen von Eitzen Sep 29 '18 at 15:31
• @HagenvonEitzen I think this is probably the original question. $x_1,x_2$ are probably just points in $x$. So the question is in $\mathbb{R}^2$ instead of $\mathbb{R}^4$ as I currently have. – Yes Sep 29 '18 at 16:05

What you missed is that the function to check the hessian of has to correspond to an inequality of the form $$f(x,y) \leq 0$$. The hessian to check is that of $$f$$ itself, not of some modification with $$\theta$$. You can check each inequality separately, since the intersection of convex sets is convex. As an example, for the constraint $$f(x,y) = -x + y^2 + 4$$ you get $$\begin{pmatrix}0 & 0 \\ 0 & 2 \end{pmatrix},$$ which is positive semidefinite. The set is therefore convex.