0

For convex functions $f_i: \mathbb{R}^n \to \mathbb{R}$, $1 \le i \le m$, let $f:\mathbb{R}^n \to \mathbb{R}$ be defined via $f(x) = \max_{i \in [m]} f_i(x)$.

I want to prove that the directional derivative of $f$ satisfies $f'(x,s) = \max_{i \in \mathcal{A}(x)} f_i'(x,s)$, with the set of active indices $\mathcal{A}(x) = \{i \in [m]: f_i(x)=f(x)\}$

We can obtain (by using the fact that convex functions are continuous on open domains), $$ \frac{f(x+ts)-f(x)}{t} = \max_{i \in \mathcal{A}(x)} \frac{f_i(x+ts) - f(x)}{t} = \max_{i \in \mathcal{A}} \frac{f_i(x+ts) - f_i(x)}{t}. $$

Now in order to get to the desired result, one needs to apply $\lim_{t\to 0^+}$ to both sides of the equation and needs to argue, that the interchange of limit and maximum is possible.

But why can we interchange it? Why is it not possible to interchange the limit and maximum when maximizing over $[m]$ (the equation above would still be valid in this case)?

Azgen
  • 39

1 Answers1

0

You need to show that the function $\max_{i \in I}$ is continuos for any $I$ finite.

as $I$ is finite than yo can rewrite it as $I=\{1, \cdots n\}$. By induction over $n$

If $n=1$ we have nothing to prove.

If $n=2$ you can write

$$ \max(f_1,f_2)= \frac{1}2 \left(f_1(x)+f_2(x)+ |f_1(x)-f_2(x)|\right) $$ see e.g. this.

By induction suppose $\max_{i \in \{1, \cdots n-1\}}$ is continuos, than $$ \max_I (f_i)= \max \left( \max_{ I / \{n\}} \left(f_i\right), f_n \right) $$ and the continuity follows from the case $n=2$

As the maximum is continuos you have

$$ \lim_{t \to 0} \max_{i \in I} f(t)=\max_{i \in I} \lim_{t \to 0} f(t) $$

For your last question:

If $i \notin A(x)$ than $f_i(x)< f(x)$ as such

$$ \max_{ i \in [m]} (f_i(x))= \max_{A(x)} (f_i(x)) $$

Marco
  • 2,357