0

Show that the following set is convex. $$M = \left\{ (x,y) : y \geq x^2 \right\}$$

First I take two arbitrary points $(x_1,y_1)$ and $(x_2,y_2) \in M$. Then I need to show that

$$\lambda(x_1,y_1)+[1-\lambda](x_2,y_2)= (\lambda x_1 + (1 − \lambda) x_2, \lambda y_1 + (1 − \lambda) y_2 ) \in M$$

After that I have no clue what I have to do. Thanks for your support.

Rodrigo de Azevedo
  • 1
Juan Sebastian
  • 33

3 Answers3

1

Take two points in $M$, say, $(x_1,y_1)$ and $(x_2,y_2)$. You need to prove that $$(\lambda x_1 + (1-\lambda)x_2, \lambda y_1 + (1-\lambda)y_2) \in M \Leftrightarrow \lambda y_1 + (1-\lambda)y_2 \geq \left( \lambda x_1 + (1-\lambda)x_2\right)^2$$ For every $\lambda \in (0,1)$. The right side is $$\left( \lambda x_1 + (1-\lambda)x_2\right)^2 \leq \lambda x_1^2 + (1-\lambda)x_2^2 \leq \lambda y_1+(1-\lambda) y_2$$ Here i used the convexity of $x^2$ on the first inequality, since $(x^2)'' = 2$ and the fact that $\lambda \in (0,1)$.

One more general result is that the epigraph of a function is convex iff the function is convex.

thewatcher
  • 859
1

As I feel OP needs technical details, so, meanwhile usually it is shown using derivative let me show everything directly here, for which divide question in 2 parts:

  1. Directly prove convexity of $f(x)=x^2 $: lets take $0 \leqslant \lambda_1,\lambda_2\leqslant 1$ and $\lambda_1 +\lambda_2 =1$ numbers. $$\lambda_1 x_1^2 + \lambda_2 x_2^2 \geqslant \left( \lambda_1 x_1 + \lambda_2 x_2\right)^2 \Leftrightarrow \\ \lambda_1 x_1^2 + \lambda_2 x_2^2 \geqslant \lambda_1^2 x_1^2 + \lambda_2^2 x_2^2 +2\lambda_1 \lambda_2 x_1 x_2 \Leftrightarrow \\ \lambda_1 \lambda_2 x_1^2 + \lambda_1 \lambda_2 x_2 ^2 \geqslant 2\lambda_1 \lambda_2 x_1 x_2 $$

  2. Prove, that for convex function set $\text{epi}(f) =\{(x,y):y \geqslant f(x) \}$ is convex (it's your $M$). For this lets take again $\lambda_1,\lambda_2$ such as above and $(x_1,y_1),(x_2,y_2) \in \text{epi}(f)$, where $f(x)=x^2 $. Then we have $$ y=\lambda_1 y_1 + \lambda_2 y_2 \geqslant \lambda_1 f(x_1) + \lambda_2 f(x_1) \geqslant f\left(\lambda_1 x_1 + \lambda_2 x_2\right)=f(x) $$ So $(x,y) \in \text{epi}(f)$.

zkutch
  • 13,410
0

$$\begin{bmatrix} 1 & x\\ x & y\end{bmatrix} \succeq \mathrm O_{2}$$

Using Sylvester's criterion, we get $y \geq 0$ and $y \geq x^2$, Note that the former is redundant. Hence, the epigraph of function $x \mapsto x^2$ is a spectrahedron and, thus, convex.

Rodrigo de Azevedo
  • 1