I am not able to see why equality in the Fenchel-Young inequality
characterizes subgradients.
As per Fenchel-Young inequality:
\begin{equation}
f(x)+f^*(u) \geq \langle x,u \rangle
\end{equation}
while the definition of subdifferential set says:
\begin{equation}
\partial f(x) = \{u: f(z) \geq f(x) + \langle u, z-x\rangle \}
\end{equation}
Now it holds that $u \in \partial f(x)$ at equality of Fenchel-Young inequality.
Assume whatever is necessary for defining functions involved above.
Thanks.
Best Answer
We will show that $$f(x)+f^*(u) = \langle x,u \rangle \Longleftrightarrow u \in \partial f(x).$$
Indeed, we have \begin{align*} u \in \partial f(x) &\Longleftrightarrow f(z) \geq f(x) + \langle u, z-x\rangle \quad\forall z \\ &\Longleftrightarrow \langle u, x\rangle - f(x) \ge \langle u, z\rangle - f(z) \quad\forall z \\ &\Longleftrightarrow \langle u, x\rangle - f(x) = \sup_z\left\{ \langle u, z\rangle - f(z)\right\} \\ &\Longleftrightarrow \langle u, x\rangle - f(x) = f^*(u) \\ &\Longleftrightarrow f(x)+f^*(u) = \langle x,u \rangle, \text{QED}. \end{align*}