I compute the subdifferential of the convex function $f(x)= \displaystyle\max_{1\le i \le N} \{f_{i} + <v_{i},x-z_{i}> \} $.
The result is: $conv(\{v_{i}, i \in I(x)\})$ where $I(x) = \{i \in \{1,\ldots, N\} ; f(x) = f_{i} + <v_{i},x-z_{i}>\}$.
Now, I would like to compute the subdifferential of $f^{*}$, the Legendre transform of $f$.
But I can't see how I can do it, I'm stuck, is there a trick? Can anyone help me please?
Thank you so much!
On
Thank you, I'm going to try. So let $ f(y) = max_{1 \le i \le N} \{ <y, x_{i}> - u_{i} \}$
Let $v \in \partial{f(x)} = \{ x_{i} ; i \in I(x) \}$ so $v = \sum_{i\in I(x)} \lambda_{i} x_{i}$ with $\lambda$ as you said.
Now our goal is to discrib $x$ because it is equivalent to say : $x \in \partial{f^{*}}(v)$
So if I look at your answer let's prouve it is equivalent to $f(x) = <x,x_{j}> - u_{j}$ with $j \in J(v) = \{ j ; v = \sum_{i\in I(x)} \lambda_{i} x_{i}, \lambda \in \Delta \}$
Let's begin by if $f(x) = <x,x_{j}> - u_{j}$ with $j \in J(v) = \{ j ; v = \sum_{i\in I(x)} \lambda_{i} x_{i}, \lambda \in \Delta \}$ and I'm going to show that $ v \in \partial{f(x)}$
Okay it's not obious for me, and the controverse neither.
Oh I have a idea ! We know $ v \in \partial{f(x)}$ iff for all $d\in R^{d}$ we have $<v,d> \le f'(x,d)$ with $f'(x,d)$ the partial derivate of $f$ at the point $x$ in the direction of $d$. And I know how to compute that, it's $max_{i \in I(x)}\{<d,x_{i}>\}$ so it works because : $<v,d> = \sum_{i \in I(x)} \lambda_{i} <x_{i},d> \le max_{i \in I(x)}\{<d,x_{i}>\}$
Now the controverse : Suppose that $v \in \partial{f(x)}$ and I want to show that $f(x)$ is as we said.
Can you help me please ?
Let $v\in\partial f$. Call $J(v)=\{j: v=\sum \lambda_jv_j$ for some $\lambda_j\in(0,1]$, $\sum \lambda_j=1\}$ $$ \partial f^*(v)=\{x:\,f(x)=f_j+\langle v_j,x-z_j\rangle\,\,\textrm{for all}\,\,j\in J\} $$ where we have used the fact that $y\in\partial f(x)$ iff $x\in\partial f^*(y)$.
The above notation is cumbersome. Let me give you a concrete example. Take the function (in one dimension): $f(x)=-2x-1$ for $x\le -1$, $f(x)=-x$ for $-1\le x\le 0$, $f(x)=x$ for $0\le x \le 1$ and $f(x)=3x-2$ for $x\ge 1$. This function is the max of four affine functions, which is what you have, the only difference being that the "slopes" $-2,-1,1,3$ are replaced by your "gradients" $v_i$. I recommend you draw the graph of this convex function.
The domain of $f^*$ is $\partial f$, that is all possible "slopes" of tangents to the graph of $f$ at some point $x\in\mathbb{R}$. In our example, $\partial f=[-2,3]$. I will describe next $\partial f^*(v)$ for some of those $v$, using the fact that $v\in\partial f(x)$ iff $x\in\partial f^*(v)$.
Take $v=3$. The only points $x$ where $v=3$ is a possible slope of the tangent are the points $x\in[1,\infty)$. Hence $\partial f^*(3)=[0,\infty)$.
Take $v=2$. $2$ is a convex combination of $1$ and $3$, and is a possible slope at $x=1$ only. Therefore, $\partial f^*(2)=\{1\}$.For the same reason, $\partial f^*(v)=\{1\}$ for any $v\in(1,3)$.
Take $v=1$. This is the slope (or one of the possible slopes) at any $x\in[0,1]$. Therefore, $\partial f^*(1)=[0,1]$.
Take now $v\in(-1,1)$. It should be clear by now that $\partial f^*(v)=\{0\}$ for such $v$.
If $v=-1$, we get a multivalued $\partial f^*$ again, $\partial f^*(-1)=[-1,1]$. If $v\in(-2,-1)$, then $\partial f^*(v)=-1$. Finally, $\partial f^*(-2)=(-\infty,-1]$.
Back to the notation in my original answer: observe that, for example, $1$ is a convex combination of $-2$ and $3$ but there is no x where $f$ is given by both lines $y=-2x-1$ and $y=3x-2$ at the same time. This is why we need "for all $j\in J(v)$".
In higher dimensions everything is the same. Instead of slopes you have gradients of supporting hyperplanes to the (epi)graph of $f$, etc. Instead of just a few "corners" you have all sorts of lower-dimensional intersections between your hyperplanes, etc.