Let $X \subseteq \mathbb R^n$ be a convex set and $g\colon X\to\mathbb R$ a concave function. Prove that the set $\{(x,z)\in X \times \mathbb R \mid g(x) \geq z\}$ is a convex set.

How do I go about proving this?

If I take 2 elements in $X \times \mathbb R$, e.g. $(x_1,z)$ and $(x_2,z)$ I will end up with an $g(z)$ and can't prove the inequality.


  • $\begingroup$ Take $0\leq \alpha\leq 1$, put $x':=\alpha x_1+(1-\alpha)x_2$ and show that $g(x')\geq z$, using the concavity of $g$. $\endgroup$ – Davide Giraudo Oct 6 '11 at 20:04

Since $g$ is concave, for any $a,b\in X$ and any $t\in[0,1]$ we have $$g\bigl(ta + (1-t)b\bigr) \geq tg(a) + (1-t)g(b).$$

If $(x,z), (y,w)\in X\times\mathbb{R}$, then given $t\in[0,1]$ we have $$t(x,z) + (1-t)(y,w) = \bigl( tx + (1-t)y, tz+(1-t)w\bigr).$$

In order for this to be in $X\times \mathbb{R}$, we need $tx+(1-t)y\in X$ (convexity of $X$ should come into play here); $tz+(1-t)w\in \mathbb{R}$ (trivial); and $$g\bigl( tx+(1-t)y\bigr) \geq tz + (1-t)w.$$ We know $g(x)\geq z$, $g(y)\geq w$. And we know $g$ is concave, which gives us a lower bound for $g\bigl(tx + (1-t)y\bigr)$. Does that lower bound and the rest of the information suffice?


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.