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