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.

| cite | improve this question | | | | |
  • $\begingroup$ You should start with the definition of *. $\endgroup$ – vadim123 Oct 12 '17 at 1:58
  • $\begingroup$ 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. $\endgroup$ – user296602 Oct 12 '17 at 1:59
  • $\begingroup$ @vadim123 Thanks, The definition is added. $\endgroup$ – maple Oct 12 '17 at 2:13
  • $\begingroup$ @user296602 Thanks, I have added my thought, though it seems a wrong direction. $\endgroup$ – 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.

| cite | improve this answer | | | | |

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.