Convexity check sub- / superlevel sets

Question

I'm doing a convex optimization course at my university and struggling with proving quasi convexity and - concavity. I know that this is done by proving convexity of the sub- and super level sets of the function, though I can't really wrap my mind around this.

I know that by definition a function is quasi convex if for an arbitrary α

$$ {S_\alpha } = \{ x \in domf | f(x) \le \alpha \} $$ And is quasi concave if the super level set is convex for -f(x) <= a. Which intuitively means that whenever you can draw a straight line through the function, the sub- or super level set has to be convex. However I don't understand how to prove this analytically. Unfortunately my textbook skips this part, and google hasn't been my friend on this problem (as everything I find is too technical for me to understand). An example problem might be the following: $$% \begin{array}{l} minimize \,\, \frac{{{f_0}(x)}}{{({c^T}x + d)}}\\ Subject\,\,to \,\,{f_i}(x) \le 0,i = 1,...,m\\ Ax = b \end{array} $$ Where all $f_i$ are convex, and the domain of the objective function is defined as $\{ x \in dom \ f_0 | {({c^T}x + d)} \ > 0 \} $

With solution: The sublevel sets are convex because $f_0(x)/(c^T x + d)\ \le \alpha$ if and only if $c^T x + d > 0$ and $f_0(x) \ \le \alpha(c^T x + d)$.

Any help will be greatly appreciated.

Ko.

Answer 1

Your answer is straightforward up to the part where you have to show that $\{x \; : \; f_0(x)/(c^T x + d)\ \le \alpha \}$ is a convex set. You could use the definition of convexity for that (as gerw does), but that is quite involved. Instead, you could rewrite the set as $\{x \; : \; f_0(x)\ \le \alpha (c^T x + d) \}$. Now it is immediate that this set is convex. To do the rewriting, you need $c^T x + d > 0$, as otherwise the inequality may flip.

Answer 2

In order to show the convexity of $S_\alpha$, we take $x,y \in S_\alpha$ and some $\lambda \in [0,1]$. Our goal is to prove $$ \lambda \, x + (1-\lambda)\,y \in S_\alpha.$$

Hence, we know \begin{align*} c^\top x &> 0, & f_0(x) &\le \alpha \, (c^\top x + d), \\ c^\top y &> 0, & f_0(y) &\le \alpha \, (c^\top y + d), \end{align*} and we have to show \begin{align*} c^\top [\lambda \, x + (1-\lambda\,y)] &> 0, & f_0(\lambda \, x + (1-\lambda\,y)) &\le \alpha \, [c^\top (\lambda \, x + (1-\lambda\,y)) + d]. \end{align*} This can be shown by using the convexity of $f_0$ and the linearity of $z \mapsto c^\top z$.