1

The definition of a convex set is the following:

A set $\Omega \subset \mathbb R^n$ is convex if $\alpha x + (1 − \alpha) y \in \Omega, \forall x, y \in \Omega$ and $\forall \alpha \in [0, 1]$.

With this it should be easy enough to prove that a set is not convex: just find a counterexample. But how do you prove that it is convex? How do I do it for the unit disk?

$$\Omega = \{(x, y) \in \mathbb R^2 \mid x^2 + y^2 \leq 1\}$$

Also what exactly does it mean for a set to be convex?

glS
  • 6,818
Shiroyasha
  • 23
  • 1
    Just use the definition? Note that the Euclidean norm is positive homogeneous and subadditive. If $|x| \le 1, |y| \le 1$ then $|t x + (1-t)y| \le t |x| + (1-t) |y| \le 1$. – copper.hat Mar 08 '18 at 15:56
  • It means that for any two points in the set, all points on the line segment joining those points are in the set. Also, unless specified otherwise, you're certainly allowed to use results from elementary geometry. So for the set in question, note that it's a disk. – quasi Mar 08 '18 at 15:57
  • quasi thanks that made it a lot clearer. But I'm still not sure how to use the definition to prove it mathematically. – Shiroyasha Mar 08 '18 at 16:02

2 Answers2

2

Hint:

If the two points $P=(x_P,y_P)$ and $Q=(x_Q,y_Q)$ are in the set than we have $x_P^2+y_P^2=x_Q^2+y_Q^2\leq1$ and to prove that the set is convex we use the definition, that gives: $$ \alpha(x_P,y_P)+(1-\alpha)(x_Q,y_Q) \in \Omega $$ that is: $$ \left[\alpha x_P+(1-\alpha)x_Q \right]^2+\left[\alpha y_P+(1-\alpha)y_Q \right]^2\leq 1 $$

Can you prove that this is true for all $P,Q$ such that $x_P^2+y_P^2=x_Q^2+y_Q^2\leq1$ and for $\alpha \in [0,1]$?

Note that $x_P^2+y_P^2$ is the square of the norm of the vector $\overrightarrow {OP}$ and use the triangle inequality for the vector $\alpha \overrightarrow {OP}+(1-\alpha)\overrightarrow {OQ}$.

Note that this set is a circle of radius $r=1$ center at the origin, that contains the segments joining any two of its points. This is the meaning of the definition of a convex set.

Emilio Novati
  • 62,675
  • I managed to prove it but I'm still having trouble writing math expressions on this website. Thanks for the help though – Shiroyasha Mar 08 '18 at 16:40
  • You can also see a similar question here: https://math.stackexchange.com/questions/135481/showing-unit-sphere-is-convex – Emilio Novati Mar 08 '18 at 16:45
1

If one can prove that a given set is a spectrahedron, then one can conclude that given set is convex.

For example, the unit disk can be represented by the following linear matrix inequality (LMI)

$$\begin{bmatrix} 1 & x & 0\\ x & 1 & y\\ 0 & y & 1\end{bmatrix} \succeq \mathrm O_3$$

and, thus, is a (convex) spectrahedron. Note, however, that not all convex sets are spectrahedra.

Rodrigo de Azevedo
  • 1