# Convexity check sub- / superlevel sets

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.

• What is precisely your question? Do you want to have some further explanation for the example problem? – gerw Oct 14 '16 at 12:50
• Yes Gerw, I really do not understand how they derive this convexity proof of the sublevel sets from the given definition. Thanks for your answer and sorry for not being clear – K. Mon Oct 14 '16 at 12:59

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.
• Perfectly clear thanks for this insight. Since $α(cTx+d)$ is a combination of a nonnegative multiple and an affine function this is convex. Thanks a lot. – K. Mon Oct 15 '16 at 3:01
• The right hand side needs to be concave. Fortunately, $\alpha(c^T x + d)$ is linear, and hence, both convex and concave. – LinAlg Oct 15 '16 at 13:01
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$.