7
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Why do we have equality with the supremum on the 3-rd line ? $\endgroup$ – Svetoslav Sep 9 '15 at 12:31
  • $\begingroup$ @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$). $\endgroup$ – Khue Sep 9 '15 at 12:34
  • $\begingroup$ 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. $\endgroup$ – Svetoslav Sep 9 '15 at 12:51
  • $\begingroup$ So your answer looks much better than mine ! +1 from me $\endgroup$ – Svetoslav Sep 9 '15 at 12:55
  • $\begingroup$ @Svetoslav: Thanks! :D $\endgroup$ – Khue Sep 9 '15 at 13:01
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.