2
$\begingroup$

Could someone assist me in proving that the maximum of a convex function is also convex using the below definition? I cannot figure out how this proof would work and would appreciate some help!

$$ f(\lambda x +(1-\lambda)y) \le \lambda f(x)+(1-\lambda)f(y) $$

$$ \lambda \in[1,0] $$

Thank you!

$\endgroup$
1
1
$\begingroup$

Step 1: Take only two convex functions $f(x)$ and $g(x)$.

Step 2: Let $\lambda\in[0,1]$. Show that: \begin{align} \max\{ f(\lambda x +(1-\lambda) y),g(\lambda x + (1-\lambda )y)\} \leq \max\{ \lambda f(x) +(1-\lambda) f(y),\lambda g(x) + (1-\lambda)g(y)\} \end{align} Step 3: Show that $\max\{A+B,C+D\}\leq \max\{A,C\} + \max\{B,D\}$, for $A,B,C,D\in\mathbb{R}$

Step 4: Show that for $\alpha\geq 0$ we have: $\max\{\alpha A,\alpha B\}=\alpha\max\{A,B\}$, for $A,B\in\mathbb{R}$.

Step 5: Finish the proof. Repeat for more functions (induction).

$\endgroup$
5
  • $\begingroup$ For the induction, the base case is k=2, the induction hypothesis is that we have the result for k and the induction step is k+1. I'm not sure what to do when this appears in the induction step: Suppose $x^*=\lambda x+(1-\lambda)y.$ Then $ f(x)\le max\{\lambda f_1(x)+(1-\lambda)f(y),\dots ,f_{k+1}(x^*)\}$ because I think I can apply convexity on $f_{k+1}.$ What should I do? $\endgroup$ – user441848 Dec 31 '17 at 23:52
  • 1
    $\begingroup$ @Anneliset. I don't understand what you mean exactly with the last words. However what will help you much is to note the following $$\max\{A, B, C\} =\max\{\max\{A, B\}, C\} $$This makes the induction easy. $\endgroup$ – Shashi Jan 1 '18 at 0:25
  • $\begingroup$ There is a typo, I meant can't instead of can. $\endgroup$ – user441848 Jan 1 '18 at 2:02
  • $\begingroup$ @Anneliset. Okay, did the hint I gave you help? You can use it like this $$\max\{f_1,...,f_{k+1}\} =\max\{\max\{f_1,...,f_{k}\},f_{k+1}\}$$ you know that the maximum of two convex function is convex and you are done. $\endgroup$ – Shashi Jan 1 '18 at 9:59
  • 1
    $\begingroup$ Yes I think I got it, I'd have to associate the functions in pairs and then apply the base case which is that the maximum of 2 convex functions is convex. $\endgroup$ – user441848 Jan 1 '18 at 19:03
0
$\begingroup$

Let $f_{1}$ and $f_{2}$ be convex, and let $f=\max(f_{1},f_{2})$. $f(\lambda x+(1-\lambda)y)=\max({f_{1}(\lambda x+(1-\lambda)y),f_{2}(\lambda x+(1-\lambda)y)}) \leq \max(\lambda f_{1}(x)+(1-\lambda)f_{1}(y)); \lambda f_{2}(x)+(1-\lambda)f_{2}(y))=\lambda \max(f_{1}(x),f_{2}(x))+(1-\lambda) \max(f_{1}(y),f_{2}(y))=\lambda f(x)+(1-\lambda)f(y)$$

$\endgroup$
0
$\begingroup$

I assume you have two convex functions $g$ and $h$ on some interval $I$, and you want to prove that $f$, defined as $f(x)=\max(g(x),h(x)), x\in I$ is convex too.

For $x,y \in I$, and $\lambda \in [0, 1] $, one of the functions $g$, $h$ is going to be the 'bigger' one at $(1-\lambda)x+\lambda y$, without loss of generality let's assume that it is $g$. Thus, $f((1-\lambda)x+\lambda y)=g((1-\lambda)x+\lambda y) \ge (1-\lambda)g(x)+\lambda g(y) \ge (1-\lambda)f(x)+\lambda f(y)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.