How to determine if a set is convex?

Question

I understand what is a convex set and also know the definition of convex set (all connecting lines lie inside the set) but when i am asked to determine if a following set is convex I am not able to apply the convex rule on that set .Can someone explain how you will find out which of the following are convex sets?

(a) Ω = {x ∈ Rn | x'x ≤ 10}
(b) Ω = {x ∈ Rn | ||x||2 ≤ 10}
(c) Ω = {x ∈ Rn | ||x||2 ≥ 10}
(d) Ω = {x ∈ Rn | a'x ≥ 10}
(e) Ω = {(x, y) ∈ Rn × Rn | ||y||2 ≤ 10 + x'y − ||x||22}

Image: Question in image format

Answer 1

Note: This is a partial answer, motivated more towards hints, but is also incomplete since I'm not sure how to get a good grasp on the final one.

---

$ \newcommand{\R}{\mathbb{R}} \newcommand{\setb}[2]{\left\{ #1 \, \middle| \, #2 \right\}} \newcommand{\t}{\textsf{T}} \newcommand{\n}[1]{\|#1\|_2} $ It will help to visualize these in lower-dimensional space for your $n$ values.

• For part (a):

  • If $n=1$ then $\Omega = \{x \in \Bbb R \mid -\sqrt{10} \le x \le \sqrt{10} \}$, clearly a convex set.

  • If $n=2$, let $x := (\xi_1,\xi_2) \in \R^2$. Then $$ x^\t x = x \cdot x = \xi_1^2 + \xi_2^2 $$ and $x \in \Omega \iff \xi_1^2 + \xi_2^2 \le 10$. This should seem familiar (think of the equation of a circle).

  • In general, for $x := (\xi_1,\cdots,\xi_n) \in \R^n$, $$ x \in \Omega \iff \sum_{i=1}^n \xi_i^2 \le 10 $$

• For part (b): Consider the result of part (a), and how it relates to a norm. You can, for instance, recall that the dot product is an inner product, and in $\R^n$, $$ \| x \|_2 = \sqrt{ x \cdot x } $$

• For part (c): What you have in this part is (almost) the complement of the $\Omega$ in part (b). Visualize what the $\Omega$ in part (b) looks like (some sort of circle); would space (with a hole deleted) be convex?

• For part (d): Here I assume we fix some $a := (a_1,\cdots, a_n) \in \R^n$.

  • If $n=1$, then you get lines when you solve the inequality $a_1 x \le 10$.

  • If $n=2$, then you get half-planes, regardless of what $a_1,a_2$ are (unless they are both zero). (Try some values of them in this Desmos demo.)

  • In general you should be able to conjecture you (almost) always get half-spaces.

• For part (e):

  • Try the $n=1$ case; with some simplification, you have $$ \Omega = \setb{ (x,y) \in \R^2 }{ y^2 \le 10 + xy - x^2} $$ This curiously is a filled-in ellipse.

  • Obviously, we can't visualize well anything in higher dimensional spaces though, so I'm a bit lost... The standard equation for an ellipse in $n$ dimensions would be (for $x := (x_1,\cdots,x_n) \in \R^n$ the points of the ellipse, and $a_i$ the semi-axes) $$ \sum_{i=1}^n \frac{x_i^2}{a_i} = 1 $$ but I'm not sure how to extract that easily out of what is given.