Proof about Conjugate and subgradient

2.3k Views Asked by At

I am reading the proof on the 15th slides of this link regarding the conjugate and subgradient. $$y \in \partial f(x) \iff x \in \partial f^*(y)$$ http://www.seas.ucla.edu/~vandenbe/236C/lectures/conj.pdf

However, I can't really understand the first line of the proof, that is

$$\text{If } y \in \partial f(x)\\ f^*(x)=\sup_u(y^Tu-f(u))=y^Tx-f(x)$$

Also, at end the slide mentions that the proof follows from $f^{**}=f$, where did they plug in that property in the proof?

1

There are 1 best solutions below

0
On BEST ANSWER

The omitted details of the first part are as follows: $$ \begin{aligned} y \in \partial f(x) &\implies f(u) \ge f(x) + y^T(u-x),\;\forall u\\ & \implies y^Tu - f(u) \le y^Tx - f(x),\;\forall u\\ & \implies f^*(y) := \sup_{u}y^Tu - f(u) = y^Tx-f(x)\\ & \implies \ldots \\ & \implies x \in \partial f^*(y). \end{aligned} $$

Conversely, suppose $x \in \partial f^*(y)$. By the first part of the proof, it follows that $y \in \partial f^{**}(x)$. But $f^{**} = f$ since $f$ is closed and convex. Thus $y \in \partial f^*(x)$.