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$
1
  • $\begingroup$ I also have the same doubt for past few days. Thanks for asking this question. $\endgroup$
    – Rajat
    Sep 9, 2015 at 12:00

2 Answers 2

11
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ Why do we have equality with the supremum on the 3-rd line ? $\endgroup$
    – Svetoslav
    Sep 9, 2015 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$
    – f10w
    Sep 9, 2015 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, 2015 at 12:51
  • $\begingroup$ So your answer looks much better than mine ! +1 from me $\endgroup$
    – Svetoslav
    Sep 9, 2015 at 12:55
  • $\begingroup$ @Svetoslav: Thanks! :D $\endgroup$
    – f10w
    Sep 9, 2015 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.

$\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.