I need to show that $S = \{(x,y) \in \mathbb{R}^2 : y \geqslant x^2\}$ is a convex set, but I'm having a bit of trouble. Simply applying the definition of convexity has got me nowhere.
Convexity of certain set
3 Answers
If you are allowed to use the fact that $f(x)=x^2$ is a convex function, the proof would be utterly simple: for any $(x_1,y_1), (x_2,y_2)\in S$ and $t\in[0,1]$, we have \begin{align} [tx_1 + (1-t)x_2]^2 &= f(tx_1 + (1-t)x_2)\\ &\le tf(x_1) + (1-t)f(x_2)\\ &\le ty_1 + (1-t)y_2. \end{align} Therefore $\left(tx_1 + (1-t)x_2,\ ty_1 + (1-t)y_2\right)$ also lies in $S$ and hence $S$ is convex.
The above argument actually shows that if $\varphi(x)$ is a convex function defined on $\mathbb{R}$, $\{(x,y)\in\mathbb{R}^2: y\ge\varphi(x)\}$ is automatically a convex set, but I guess the point of the exercise is to show that the square function is convex ... :-D
-
0@dineshdileep Yes. As the question was set around a particular function rather than a general convex function, I thought the point of the exercise is *not* really showing that the epigraph of a convex function is convex. – 2012-12-11
Let $(a,b),(c,d)\in S$, we need to show that for all $\lambda\in (0,1)$ $(\lambda a+(1-\lambda)c,\lambda b+(1-\lambda)d)\in S$.
Proof: Firstly, we note that $a^2\leq b$ and $c^2 \leq d$
Since $ac\leq \sqrt {bd}\leq \frac {b+d}{2}$, therefore $2\lambda (1-\lambda) ac\leq (\lambda-\lambda^2)b+(\lambda-\lambda^2)d$. Since $\lambda^2a^2\leq\lambda^2b$ and $\lambda^2c^2\leq\lambda^2d$. By adding the last three inequlities we get: $(\lambda a+(1-\lambda)c)^2=\lambda^2a^2+2\lambda (1-\lambda) ac+\lambda^2c^2\leq \lambda b+(1-\lambda d) $
Here is the solution, suppose that $x=(a,b)$ and $y=(c,d) \in A=\{ (x,y) / x^2 \leq y\}$, we are going to show that $[x,y] = \{(1-t)x - ty / 0 \leq t \leq 1 \} \subset A$. Let $w \in [x,y]$, then \begin{align*} w= (1-t)x + ty &= (1-t)(a,b) + t(c,d) \\ &= ((1-t)a + tc, (1-t)b + td) \end{align*} We affirm that $(1-t)^2a^2 + t^2c^2 + 2t(1-t)cd \leq (1-t)b + td$ which its equivalent to show that $(1-t)^2a^2 + t^2c^2 + 2t(1-t)cd \leq (1-t)a^2 + tc^2$ (since $a^2 \leq b$ and $c^2 \leq d$ implies $(1-t)a^2 + tc^2 \leq (1-t)b + td )$. \begin{align*} (1-t)^2a^2 + t^2c^2 + 2t(1-t)cd \leq (1-t)a^2 + tc^2 \\ \Leftrightarrow & 2t(1-t)cd \leq (1-t)a^2+tc^2 - (1-t)^2a^2 - t^2c^2 \\ &= a^2[(1-t)-(1-t)^2] + c^2t(1-t)\\ &= a^2t(1-t)+c^2t(1-t)\\ &= t(1-t)(a^2+c^2) \end{align*}
i.e $2t(1-t)cd \leq t(1-t)(a^2+c^2) \Rightarrow 2ac \leq a^2 + c^2$, which its true. Then $w \in A$. Note that $t(1-t) = 1-t - (1-t)^2$, and the definition to convext set is: X is a convext set if $x,y \in X \Rightarrow [x,y] \subset X$, where for $x,y \in \mathbb{R}^n$ we define the segment between x and y as $[x,y] = \{ (1-t)x + ty / 0 \leq t \leq 1 \}$