10
$\begingroup$

Here's a homework question I'm struggling with:

Let $f,g$ two convex functions. Prove that $h(x)=\max\{f(x),g(x)\}$ is also convex

I don't know where to begin. The only thing I had in mind was was to try proving that if a function is convex on two sets $A$ and $B$, it is also convex on their union. That does not seem right though, for example if I glue together $f(x)=x^2, g(x)=\frac{x^2}{1000}$ where $f$ is defined on $[0,1]$ and $g$ on $(1,2]$.

Anyway, that was the only thing I thought about. Any better ideas? thanks!

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ @yotamoo: While typesetting, use \max instead of max (similarly use \sin instead of sin etc) $\endgroup$ – user17762 May 20 '12 at 17:54
  • $\begingroup$ @Didier Can you add that as an answer adding, probably another line or two, so that this question gets an answer? $\endgroup$ – user17762 May 20 '12 at 18:04
9
$\begingroup$

Hint: Use the characterization that $h$ is convex if and only if, for every $t$ in $[0,1]$ and every $(x,y)$, $h(tx+(1-t)y)\leqslant th(x)+(1-t)h(y)$.

Second hint: One wants to prove that $h(z)\leqslant th(x)+(1-t)h(y)$ where $z=tx+(1-t)y$. Since $h=\max\{f,g\}$, this is equivalent to the two inequalities $$ f(z)\leqslant th(x)+(1-t)h(y),\qquad g(z)\leqslant th(x)+(1-t)h(y). $$ Consider the first inequality. By convexity of $f$, one knows that $f(z)\leqslant tf(x)+(1-t)f(y)$. Furthermore, $f(x)\leqslant$ $____$ and $f(y)\leqslant$ $____$, hence...

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Okay I can assume that $h=g$ at $tx_1+(1-t)x_2$, but the behavior of $h$ at $x_1$ and $x_2$ has four different options, depending on what function is greater at these points. How can I come to a conclusion? $\endgroup$ – yotamoo May 21 '12 at 7:08
  • $\begingroup$ Nevermind I saw it, thanks! $\endgroup$ – yotamoo May 21 '12 at 7:31
  • $\begingroup$ What about the case $ \max_{i} {x}_{i} - \min_{i} {x}_{i} $? $\endgroup$ – Royi May 30 '17 at 14:33
  • $\begingroup$ @Royi If you have a new problem (which frankly I did not get), please post a new question. $\endgroup$ – Did May 30 '17 at 14:34
  • $\begingroup$ @Did, I fixed an error I had there. $\endgroup$ – Royi May 30 '17 at 14:38
24
$\begingroup$

The hint of @Did solves the problem, but there is another proof, which is more intuitive I think.

A function is convex if and only if the area above its graph is convex. But then, the region above $h(x) = \max\{f(x),g(x)\}$ is the intersection of the area above $f$ and the region above $g$. Moreover, intersection of convex sets is convex, and that concludes the proof.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Does this apply similarly for the maximum of two concave functions? $\endgroup$ – bright-star Apr 18 '14 at 5:02
  • 1
    $\begingroup$ @TrevorAlexander Not really, take for example $f(x) = -(x-2)(x-4)$ and $g(x) = -(x+2)(x+4)$, then $h(-4) = h(-2) = h(2) = h(4) = 0$, but $h(-3) = h(3) = 1$, hence $h$ is not concave. $\endgroup$ – dtldarek Apr 18 '14 at 7:27
  • $\begingroup$ @dtldarek is it equivalent to saying that minimum of two concave sets is concave? $\endgroup$ – kaka Oct 9 '16 at 2:45
  • 1
    $\begingroup$ @kaka Yes, you can just use $h(x) = -\max\{-f(x),-g(x)\}$. $\endgroup$ – dtldarek Oct 9 '16 at 6:34
  • 1
    $\begingroup$ @kaka If $f$ is concave, then $-f$ is convex. $\endgroup$ – dtldarek Oct 9 '16 at 18:44

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.