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) $$

  • 1
    $\begingroup$ And, what is $f$? $\endgroup$ – kimchi lover May 5 at 20:00
  • $\begingroup$ Sorry I meant a set not a function $\endgroup$ – Adawood May 5 at 20:03
  • $\begingroup$ 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 $\endgroup$ – Adawood May 5 at 20:05
  • $\begingroup$ You need to identify what $f$ is, prove that it is convex, then show that $S$ is the epigraph if $f$. $\endgroup$ – Rodrigo de Azevedo May 5 at 20:32

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}$


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.


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.