Proving that a given set is convex using the definition

Question

Using the definition, prove that the following set is convex $$S := \{ (x_1,x_2) \in \mathbb R^2 \mid x_2 \geq x_1^2 \}$$

I know that the definition of convex function is

$$ f \left( \lambda x_1+(1-\lambda)x_2 \right) \leq \lambda f(x_1) + (1-\lambda) f(x_2) $$

We have to take two points from the set and place them in the definition and conclude that the inequality is true,however I get stuck at a point at the very end — Monica, May 05 '19 at 20:05
You need to identify what $f$ is, prove that it is convex, then show that $S$ is the epigraph if $f$. — Rodrigo de Azevedo, May 05 '19 at 20:32

score 1 · Answer 1 · answered May 05 '19 at 20:52

Here is a variant (not using $f$ epigraph).

You have to prove that for two points $x$ and $y$ in $S$ then the segment $[xy]$ belongs to $S$

Or similarly that $\forall z\in[xy]$ then $z\in S$.

$\begin{cases} x=(x_1,x_2) & x_2\ge {x_1}^2\\ y=(y_1,y_2) & y_2\ge {y_1}^2\\ z=(z_1,z_2)\end{cases}\quad$ and we are interested in $z=tx+(1-t)y$ with $t\in[0,1]$.

Can you show $z_2\ge {z_1}^2$ ?

$\begin{align}{z_1}^2 &=\bigg(tx_1+(1-t)y_1\bigg)^2\\&=t^2{x_1}^2+(1-t)^2{y_1}^2+t(1-t)\overbrace{(2x_1y_1)}^{\le\ {x_1}^2+{y_1}^2}\\\\&\le \big(t^2+t(1-t)\big){x_1}^2+\big((1-t)^2+t(1-t)\big){y_1}^2\\\\&\le t{x_1}^2+(1-t){y_1}^2\\\\&\le tx_2+(1-t)y_2 = z_2\end{align}$

Rodrigo de Azevedo · Answer 2 · 2020-07-11T01:42:49.547

_{Here's one way of proving that the set is convex without using the definition of convexity.}

Using the Schur complement and Sylvester's criterion, we conclude that the given set is defined by the following linear matrix inequality (LMI)

$$\begin{bmatrix} 1 & x_1\\ x_1 & x_2\end{bmatrix} \succeq \mathrm O_2$$

and, thus, is a spectrahedron. All spectrahedra are convex.

convex-analysis schur-complement linear-matrix-inequality spectrahedra

Proving that a given set is convex using the definition

2 Answers2