0

If $S = \{(x,y) : y = e^x\}$ was convex, the following relation holds
\begin{align} &t y_1 + (1-t) y_2 = e^{t x_1 + (1-t) x_2} \tag{1}\\[2mm] \Longleftrightarrow \quad & t e^{x_1} + (1-t) e^{x_2} - e^{t x_1 + (1-t) x_2} = 0 \tag{2} \end{align} for any $x_1, x_2 \in \mathbb{R}$, $x_1 \neq x_2$ and $t \in (0,1)$.

  • Is my definition of convexity correct?

For $t=0.5$ (2) becomes \begin{align} &0.5(e^{x_1} + e^{x_2}) - e^{0.5(x_1 + x_2)} = 0 \tag{3}\\ \Longleftrightarrow \quad &e^{x_1} + e^{x_2} - 2e^{0.5(x_1 + x_2)} = 0 \tag{4}\\ \Longleftrightarrow \quad &(e^{0.5 x_1} - e^{0.5 x_2})^2 = 0 \tag{5} \end{align}

where (5) is a contradiction (do you guys use any symbols for that matter?) and thus $S$ is not convex.

  • Can we verify the statement in a general manner with $t$ being free?

Now show that $S' = \{(x,y) : y \geq e^x\}$ is convex. (5) then becomes \begin{align} (e^{0.5 x_1} - e^{0.5 x_2})^2 \geq 0 \tag{6} \end{align}

which is true and thus $S'$ is convex. Again, I'd like to show this in a rather general way.

Edit

I added 'If it is not convex, give a counterexample.' to the title. I was just wondering if we can construct a general counterexample without specifying some values for $x_1,x_2,y_1,y_2$ and $t$.

Andrés E. Caicedo
  • 79,201
clueless
  • 771
  • No, I thought that this is the definition for convexity here, i.e. any linear combination of two points $x_1$ and $x_2$ must be a linear combination of $y_1$ and $y_2$, if ${(x,y) : y=e^x}$ was convex which is apparently not the case, thus the equation is not true or extremly wrong for that matter. – clueless Dec 08 '15 at 08:06
  • If we have the two points: $(x_1, e^{x_1})$ and $(x_2, e^{x_2})$, the convex combination, for some scalar $t \in (0,1)$ is $(tx_1+(1-t)x_2, te^{x_1} + (1-t)e^{x_2})$. This can't be simplified further... – Matthew Gunn Dec 08 '15 at 08:14
  • yes, ok, your application of the def. of convexity at the top is fine. – Matthew Gunn Dec 08 '15 at 08:16
  • Not at all, this is a definition of linearity ! Convexity is when inequality $\ge$ holds. –  Dec 08 '15 at 08:18
  • What about ${(x,y) : x = y}$? This is a convex set, isn't it? – clueless Dec 08 '15 at 08:20
  • @YvesDaoust He's talking about convexity of a set, not convexity of a function. – Matthew Gunn Dec 08 '15 at 08:20
  • For a counterexample, if we're really just talking about the graph of $y=e^x$, I don't see why you couldn't just mention something about secant lines. – pjs36 Dec 08 '15 at 08:20
  • @MatthewGunn: oooops, right. Then the answer's easy. –  Dec 08 '15 at 08:28

5 Answers5

3

It is not convex. $(-1,{1 \over e}), (1,e) \in S$, but ${1 \over 2} ((-1,{1 \over e})+ (1,e)) = (0, {1 \over 2}(e+{1 \over e})) \notin S$.

Suppose $(x_1,y_1),(x_2,y_2) \in S'$ and $\lambda \in [0,1]$. If $f(x) = e^x$ we see that $f''(x) >0$, hence $f$ is convex function. Then $e^{\lambda x_1+(1-\lambda) x_2} \le \lambda e^{x_1} + (1-\lambda) e^{x_2}$ and so we have $e^{\lambda x_1+(1-\lambda) x_2} \le \lambda e^{x_1} + (1-\lambda) e^{x_2} \le \lambda y_1+(1-\lambda) y_2$ and so we see that $({\lambda x_1+(1-\lambda) x_2}, (\lambda y_1+(1-\lambda) y_2)) \in S'$ and so $S'$ is convex.

copper.hat
  • 172,524
1

For "Show that $S' = \left\{(x,y) : y \geq e^x\right\}$ is a convex set"

You can argue:

  1. $e^x$ is a convex function.
  2. The epigraph of a convex function is a convex set.

Note that $S = \left\{(x,y) : y = e^x\right\}$ is not a convex set. It trivially fails the def. of convexity. You can use any two points and any scalar $t \in (0,1)$ to generate a point that should be in $S$ (if it were convex) but isn't.

Matthew Gunn
  • 416
1

Take $t=\frac12$.

$$e^{(x_1+x_2)/2}=\sqrt{e^{x_1}e^{x_2}}\ne\frac{e^{x_1}+e^{x_2}}2.$$

Indeed, the converse would imply, by squaring

$$\left(\frac{e^{x_1}-e^{x_2}}2\right)^2=0$$which is false.

0

The set $S'$ is actually known as the epigraph of the function $f(x) = e^x$. The epigraph of $f$ (denoted as $\mathrm{epi}(f)$) is convex if and only if the function $f$ is convex, which is true since $f''(x) = e^x > 0$.

GNUSupporter 8964民主女神 地下教會
  • 17,627
0

"Can we verify the statement in a general manner with $t$ being free?"

Your set $S$ equals the graph of a function, and this graph is convex iff the function is affine:

If $f : X \to Y$ is a function between linear spaces and $S = \{(x,y) : y = f(x)\}$ is convex, we have $$f( \lambda \, x_1 + (1-\lambda) \, x_2 ) = \lambda \, f(x_1) + (1-\lambda) \, f(x_2)$$ for all $x_1, x_2 \in X$ and $\lambda \in [0,1]$. Now, we show that $g(x) = f(x) - f(0)$ is linear. Indeed, the above equation with $x_1 = x$ and $x_2 = 0$ shows $$g( \lambda \, x ) = \lambda \, g(x)$$ for $\lambda \in (0,1]$. Using $x_1 = x/\lambda$, $x_2 = 0$ shows $$g( x) = \lambda \, g(x/\lambda)$$ for $\lambda \in (0,1]$. Hence, $g$ is positively homogeneous and it remains to show the additivity. To this end, we take $\lambda = 1/2$ in the above equation and get $$\frac12 \, g(x_1 + x_2) = g(\frac12 \, x_1 + \frac12 \, x_2) = \frac12 \, g(x_1) + \frac12 \, g(x_2).$$ This shows the additivity. Hence, $g$ is linear and $f$ is affine.

To apply to your situation, you simply have to note that $x \mapsto \mathrm{e}^x$ is not affine.

gerw
  • 31,359