0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is precisely your question? Do you want to have some further explanation for the example problem? $\endgroup$ – gerw Oct 14 '16 at 12:50
  • $\begingroup$ 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 $\endgroup$ – K. Mon Oct 14 '16 at 12:59
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – K. Mon Oct 15 '16 at 3:01
  • $\begingroup$ The right hand side needs to be concave. Fortunately, $\alpha(c^T x + d)$ is linear, and hence, both convex and concave. $\endgroup$ – LinAlg Oct 15 '16 at 13:01
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks gerw for showing me how to use the definition of convexity properly. $\endgroup$ – K. Mon Oct 15 '16 at 3:02

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.