0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Devashish Kaushik Sep 29 '18 at 15:19
  • 1
    $\begingroup$ Where does your domain live in? $\Bbb{R}$ , $\Bbb{R^n}$, $n=$ ? $\endgroup$ – dmtri Sep 29 '18 at 15:23
  • $\begingroup$ The question I'm answering only states $\mathbb{R}$. I'm not sure if it was perhaps intended otherwise. $\endgroup$ – Yes Sep 29 '18 at 15:26
  • 1
    $\begingroup$ @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" $\endgroup$ – Hagen von Eitzen Sep 29 '18 at 15:31
  • $\begingroup$ @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. $\endgroup$ – Yes Sep 29 '18 at 16:05
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much for fixing my mistake. This method makes sense now. $\endgroup$ – Yes Sep 29 '18 at 20:20

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.