Proof of "if $f$ is closed and convex then $f^{**}=f$ for all $x$"

Question

I am studying this proof on the topic, and the proof is following: ($f^*$ is the conjugate function of $f$)

The key points of this proof is

1. Separating hyperplane theorem.
2. Fenchel inequality: $f^*(y)=\text{sup}[y^Tx-f(x)]\Rightarrow f^*(y)\geq y^Tx-f(x)$

My question is only the part in the blue box; how to obtain the term:

$$\epsilon \big(f^*(\hat{y} )-x^T\hat{y}+f^{**}(x) \big)$$

Answer 1

you can decompose the left hand side of the blue box to

$$ \left(\begin{array}{c}a\\0\end{array}\right)^T\left(\begin{array}{c}z-x\\ s-f^{\star\star}(x)\end{array}\right) + \left(\begin{array}{c}\epsilon \hat y\\-\epsilon\end{array}\right)^T\left(\begin{array}{c}z-x\\ s-f^{\star\star}(x)\end{array}\right) $$

you know that the term on the left is $\le c$. Let's look at the other term, expanding leads to

$$ \epsilon\left( \hat y^T z - s - \hat y^T x + f^{\star\star}(x)\right) $$

two steps now:

1. use the fact that $(z,s)$ is in the epigraph, so that $s\ge f(z)$
2. bound using fenchel conjugate

$$ \hat y^T z -s \le \hat y^T z - f(z) \le \sup_w\,\, [ \hat y^T w -f(w)] = f^\star(\hat y) $$

assembling the pieces gives your blue box.