# How to prove the conjugate of the conjugate function is itself?

Suppose $f$ is closed and convex. $f^*$ is the conjugate of $f$. $$f^*(y)=\sup_{x\in\mathbb{R}^n} \{y^Tx−f(x)\}$$ How to prove that $f=f^{**}$?

My thought: I can write the conjugate by substitute terms into the definition as $$\sup_a\{z^T a-\sup_x\{a^Tx-f(x)\}\}$$ But it seems cannot get any more simplification.

• You've been a user here for five years and posted dozens of questions. Please edit your question to actually show your own thoughts and efforts. Voting to close. – user296602 Oct 12 '17 at 1:59
• @vadim123 Thanks, The definition is added. – maple Oct 12 '17 at 2:13
• @user296602 Thanks, I have added my thought, though it seems a wrong direction. – maple Oct 12 '17 at 2:17

This problem will be made simpler by translating to the language of convex sets.

Consider $$\operatorname{epi} f$$ and $$\operatorname{epi} f^{**}$$, the epigraphs of $$f$$ and $$f^{**}$$.

To start, we have that both epigraphs are convex because $$f$$ and $$f^{**}$$ are closed and convex. To show that $$f^{**}$$ is closed and convex, consider that its epigaph is the intersection of (closed, convex) halfspaces of the form $$\{z^{T} y - f^{*}(y): z \in \mathbb{R}^n\}$$, because supremum of functions results in the intersections of epigraphs.

We have that $$f^{**} \leq f$$. From its definition, $$f^{**}(x) = \sup_{y} x^{T} y - f^{*}(y)$$ $$= \sup_{y} \{ x^{T} y - \sup_{z} \{ y^{T} z - f(z) \} \}$$ $$= \sup_{y} \, \inf_{z} \,y^{T}(z-x) + f(z) \leq \inf_{z} \, \sup_{y} \,y^{T}(z-x) + f(z) = f(x)$$ where the inequality comes from exchanging the infimum and supremum (you may also recall this maneuver from the proof of weak duality).

Now assume for contradiction that $$f \neq f^{**}$$. From our just-derived inequality, this means that $$\exists x$$ with $$f^{**}(x) < f(x)$$. By the closed/compact version of the hyperplane separation theorem, there must be hyperplane in $$\mathbb{R}^{n+1}$$ that strictly separates $$\operatorname{epi} f$$ from $$(x, f^{**}(x))$$.

This hyperplane cannot be vertical and strictly separate $$\operatorname{epi} f$$ from $$(x, f^{**}(x))$$, so we can normalize the normal vector of the hyperplane to be $$1$$ in the vertical component. This strict separation gives, for some $$\epsilon > 0$$ and non-vertical component $$y \in \mathbb{R}^n$$ of our hyperplane, $$f(z) - \epsilon \geq y^T(z-x) + f^{**}(x) \quad \forall z \in \mathbb{R}^{n}.$$ Some manipulations give $$y^{T}x - f^{**}(x) - \epsilon \geq y^{T} z - f(z) \quad \forall z$$ and taking the supremum in $$z$$ yields $$y^{T} x - f^{**}(x) - \epsilon \geq f^{*}(y).$$ Another manipulation gives $$y^{T} x - f^{*}(y) - \epsilon \geq f^{**}(x).$$

Expanding the definition of $$f^{**}$$, we have just shown that $$y^{T} x - f^{*}(y) - \epsilon \geq \sup_{v}\, v^{T} x - f^{*}(v).$$ Obviously the choice of $$y$$ on the LHS cannot exceed the supremum on the right, so we have our contradiction.