I am tasked to prove by the definition of convex sets that $S=\{\vec{x} : x_2 \geq e^{-x_1}\}$ is convex. It is simple to show this by considering the function $f(x) = e^{-x_2}-x_1$ and utilizing lower-level sets, but I would like to prove this directly by the definition of convex sets (i.e. the line segment between two points in $S$ is also in $S$).

So far, I've let $\vec{u}, \vec{v} \in S$, where $u=(u_1, u_2)$ and $v=(v_1, v_2)$ and established that our goal is to show that $\lambda u_2 + (1-\lambda)v_2 \geq e^{-(\lambda u_1 + (1-\lambda) v_1)}$.

From there, I've claimed that since $u_2 \geq e^{-u_1}$ and $v_2 \geq e^{-v_1}$, then $$\lambda u_2 + (1-\lambda)v_2 \geq \lambda e^{-u_1}+(1-\lambda)e^{-v_1}.$$ However, I don't know how to show that $\lambda e^{-u_1}+(1-\lambda)e^{-v_1} \geq e^{-(\lambda u_1 + (1-\lambda) v_2)}$ to conclude. So, how does one show that inequality?

  • 1
    $\begingroup$ A good start to a tasteful argument. Do you know if $x\mapsto \exp(-x)$ is convex? $\endgroup$ Sep 21 '18 at 2:13
  • $\begingroup$ Visually speaking, I would guess that graph($f$) is nonconvex but epi($f$) is convex, if $f(x) = e^{-x}$. $\endgroup$ Sep 21 '18 at 2:17
  • $\begingroup$ The epigraph of $\exp(x)$ and the epigraph of $\exp(-x)$ ought to be similar, I'd think: one is the mirror image of the other. $\endgroup$ Sep 21 '18 at 2:19
  • $\begingroup$ Is this a hint on showing that the inequality above is true? Or that I should consider the convex function $f(x) = e^{-x}$ and show that $S$ is a lower level set of a convex function? $\endgroup$ Sep 21 '18 at 2:24
  • $\begingroup$ Your $S$ is the epigraph of $f:x\mapsto\exp(-x)$. I don't know how your definitions are arranged, that is, what your precise basic definition of "convex" is. But at some stage you must know that the epigraph of a convex function is convex, and conversely. So. If you can prove $f$ is convex, you are done. $\endgroup$ Sep 21 '18 at 2:29

The statement of your problem and discussion in comments has confused me a bit.

As I understand your question, you want to prove your 2-dimensional subset $S$ is convex by verifying that for any two points in $S$ the line segment connecting them is contained in $S$. Let $f:x\mapsto\exp(-x)$. You have reduced your problem to showing that for all $u,v\in S$, and $\lambda\in[0,1]$ you have $$ \lambda f(u_1)+(1−\lambda)f(v_1)≥f(\lambda u_1+(1−\lambda)v_1).$$ This is precisely the defining condition for $f$ to be a convex function of a single variable. So to complete your proof you need to show that $f$ is convex.

You seem to think that this argument is the same as showing that $S$ is a lower level set of the convex function $g(x,y)=\exp(-x)-y$ of two variables. Granted, they are close, but in my opinion they are not identical. To me the "$f$" proof is simpler than the "$g$" proof because I cannot see how you can possibly show $g$ is convex without also showing (or knowing) that $f$ is convex. The $f$ proof is, I think, more elegant, and contains more of the ideas about convexity you should keep in your head forever.


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.