I'm getting confused on how to prove this. I was thinking 2 points $x$ and $y$ that satisfy the definition of convex function $f((1-\lambda)x+\lambda y \le (1-\lambda)f(x)+\lambda f(y)$ where $\lambda \subset [0,1]$ and $x$ and $y$ are real numbers, but can't really plug them in cause the values you get back are outputs from a function the function output depends on which function outputs a larger value.


The definition of convexity of $f$ is that $$f((1-t)x+ty)\le (1-t)f(x)+tf(y)\tag{1}$$ for all vectors $x$, $y$ in $\Bbb R^n$ and all $t\in[0,1]$.

In our case, take $f=\max(f_1,f_2)$ where $f_1$, $f_2$ are convex. Two prove an inequality $$\max(a,b)\le c$$ it suffices to prove both $$a\le c\quad \text{and}\quad b\le c.$$ So to prove $(1)$ we only need to prove both $$f_1((1-t)x+ty)\le (1-t)f(x)+tf(y)\tag{2}$$ and $$f_2((1-t)x+ty)\le (1-t)f(x)+tf(y).\tag{3}$$

The proofs of $(2)$ and $(3)$ are clearly going to be similar, so I'll only consider $(2)$. By the convexity of $f_1$ I know that $$f_1((1-t)x+ty)\le (1-t)f_1(x)+tf_1(y)\tag{4}.$$ But as $1-t\ge0$ and $t\ge0$, and $f_1(x)\le f(x)$ and $f_1(y)\le f(y)$, we have $(1-t)f_1(x)\le (1-t)f(x)$ and $tf_1(y)\le tf(y)$. Thus $$(1-t)f_1(x)+tf_1(y)\le (1-t)f(x)+tf(y).\tag{5}$$ Putting $(4)$ and $(5)$ together gives $(2)$.

  • $\begingroup$ Brilliant thanks so much! except for the $\le c$ everything else makes perfect sense $\endgroup$ – Dylan Y Sep 26 '19 at 5:26

Note that $\operatorname{epi} \max(f_1,f_2) = \operatorname{epi} f_1 \cap \operatorname{epi} f_2$. The intersection of convex sets is convex.

  • $\begingroup$ what is epi? I actually like this proof except that I don't get how $epi max(f_1,f_2)$ is equal to their intersect $\endgroup$ – Dylan Y Sep 26 '19 at 6:25
  • $\begingroup$ $\operatorname{epi} f = \{ (x,\alpha) | \alpha \ge f(x) \}$. A function is convex iff its epigraph is convex. It is the points 'above' the graph of $f$. $\endgroup$ – copper.hat Sep 26 '19 at 6:28
  • $\begingroup$ That makes sense, but how does the epigraph of the max of 2 functions gives a intersection of the 2 functions? I'd imagine it'd just be the epigraph of whichever is larger no? $\endgroup$ – Dylan Y Sep 26 '19 at 6:48
  • 1
    $\begingroup$ O wait I just imagined it in my head and now I see it $\endgroup$ – Dylan Y Sep 26 '19 at 6:49

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.