How equality in Fenchel-Young inequality characterizes subdifferential?

Question

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.

Answer 1

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*}

Answer 2

Let $f:X\rightarrow \mathbb R$ and $X^*$ is the dual of $X$. First recall the definition of $f^*: X^*\rightarrow \mathbb R$

$f^*(u^*)=\sup\limits_{x\in X}{\{\langle u^*,x\rangle - f(x)\}}$, where $u^*\in X^*$ and $\langle .,.\rangle$ is the duality pairing in $X^*\times X$.

Then the definition for subdifferential set is:

$\partial f (x)=\{u^*\in X^*: f(z)\ge f(x)+\langle u^*,z-x\rangle\}$.

Proposition:

$f(x)+f^*(u^*)-\langle u^*,x\rangle =0\Leftrightarrow u^*\in\partial f(x)$.

Proof:

1) Let $f(x)+f^*(u^*)-\langle u^*,x\rangle =0$. From the definition $f^*(u^*)=\sup\limits_{x\in X}{\{\langle u^*,x\rangle - f(x)\}}\Rightarrow$

$0=f(x)+f^*(u^*)-\langle u^*,x\rangle \ge f(x)+\langle u^*,z\rangle -f(z)-\langle u^*,x\rangle\quad \forall z\in X$ which is $f(z)\ge f(x)+\langle u^*,z-x\rangle \quad \forall z\in X$

2) Let $u^*\in \partial f(x)$. By definition $f(z)\ge f(x)+\langle u^*,z-x\rangle\quad \forall z\in X$. Consequently $\langle u^*,x\rangle-f(x)\ge \langle u^*,z\rangle - f(z)\quad\forall z\in X$

$\Rightarrow \langle u^*,x\rangle-f(x)\ge \sup\limits_{z\in X}{\{\langle u^*,z\rangle - f(z)\}}=f^*(u^*)\quad\quad (1)$.

But from the definition of $f^*(u^*)\Rightarrow f^*(u^*)\ge \langle u^*,x\rangle-f(x)\quad\quad (2)$.

From $(1)$ and $(2)$ follows the equality.