# How equality in Fenchel-Young inequality characterizes subdifferential?

I am not able to see why equality in the Fenchel-Young inequality characterizes subgradients.

As per Fenchel-Young inequality: $$f(x)+f^*(u) \geq \langle x,u \rangle$$ while the definition of subdifferential set says: $$\partial f(x) = \{u: f(z) \geq f(x) + \langle u, z-x\rangle \}$$ 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.

• I also have the same doubt for past few days. Thanks for asking this question. – Rajat Sep 9 '15 at 12:00

We will show that $$f(x)+f^*(u) = \langle x,u \rangle \Longleftrightarrow u \in \partial f(x).$$

Indeed, for any proper, lsc, convex function f, 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*}

See Rockafellar et al 2009, Variational analysis, proposition 11.3 for details.

• Why do we have equality with the supremum on the 3-rd line ? – Svetoslav Sep 9 '15 at 12:31
• @Svetoslav: if $x\in X$ and $f(x) \ge f(y) \quad\forall y\in X$ then obviously $f(x) = \sup_{y\in X} f(y)$, by definition (of $\sup$). – Khue Sep 9 '15 at 12:34
• you are right. I just looked at $\langle u,x\rangle -f(x)$ as some sumber-an upper bound for $\langle u,z\rangle -f(z)$, without realizing that it is the same function. – Svetoslav Sep 9 '15 at 12:51
• So your answer looks much better than mine ! +1 from me – Svetoslav Sep 9 '15 at 12:55
• @Svetoslav: Thanks! :D – Khue Sep 9 '15 at 13:01

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.