Fenchel-Rockafellar duality problem: Show that weak duality holds, i.e., p≥−d .

Question

I am looking for help with motivation for the Fenchel-Rockafellar duality problem. Specifically the following:

Let $\;f : X \rightarrow ]-\infty, +\infty]$ be convex and lower semicontinuous, let $A : X \rightarrow Y$ be linear, and let $g: Y \rightarrow ]-\infty, +\infty]$ be convex and lower semicontinuous. Recall that in the context of Fenchel–Rockafellar duality, the primal problem is defined by:

(P) $$ p := \inf_{x\in X} \;f(x) + g(Ax)\;\;\; $$

and the dual problem is

(D) $$ d := \sup_{y\in Y} \;-f^*(A^*y) - g^*(-y) = -\inf_{y\in Y} \;f^*(A^*y) + g^*(-y) \;\;\; $$

where $A^*$ denote the conjugate/transpose of $A$. Show that weak duality holds, i.e., $ \;p \geq d$.

I suspect I should use the Fenchel-Young inequality, which is $$f(x) + f^*(v) \geq \langle x,v \rangle$$ or some variation thereof. However, I am having trouble getting from the definitions of (P) and (D) to $p\geq d$ via F-Y. Please pass some hints, suggestions or help my way. Thank you

Answer 1

You can do it from "first principles". First note that because $f$ and $g$ are convex lcm, $f = f^{**}$ and $g = g^{**}$. Now, for any $x \in X$, we have \begin{equation} \begin{split} f(x) = f^{**}(x) := \sup_{z \in Y}\langle x, z \rangle - f^*(z) \ge \sup_{z \in \text{Im }A^*}\langle x, z \rangle - f^*(z) &= \sup_{y \in Y}\langle x, A^*y\rangle - f^*(A^*y)\\ &= \sup_{y \in Y}\langle Ax, y\rangle - f^*(A^*y) \end{split} \end{equation} Thus, \begin{equation} \begin{split} p &\ge \inf_{x \in X}\sup_{y \in Y}\langle Ax, y\rangle - f^*(A^*y) + g(Ax) \ge \sup_{y \in Y}- f^*(A^*y) + \inf_{x \in X}\langle Ax, y\rangle + g(Ax)\\ &= \sup_{y \in Y}- f^*(A^*y) -\sup_{x \in X}\langle Ax, -y\rangle - g(Ax) = \sup_{y \in Y}- f^*(A^*y) -\sup_{x \in \text{Im A}}\langle x, -y\rangle - g(x)\\ &= \sup_{y \in Y}- f^*(A^*y) -\sup_{z \in Y}\langle z, -y\rangle - g(z) \ge \sup_{y \in Y}- f^*(A^*y) - g^*(-y) = d. \end{split} \end{equation}

Answer 2

if you want to use the fenchel young inequality , you may use it as follows :

• f(x)+f*(A*y) ≥ $< x, A^* y>$ = < Ax,y> as $A*$ is the adjoint of A .

• g(Ax)+g*(-y) ≥ <-Ax,y>

As < -Ax,y > + < Ax,y > =0 (not the hardest part)

then $\forall x \in X ,\forall y \in Y :$ f(x)+g(Ax) + f*(Ay)+g(-y) ≥ 0

Hence p= $inf_{x\in X }$(f(x)+g(Ax)) ≥ $sup_{y\in Y}$(-f*(Ay)-g(-y)) = d

Answer 3

I think the simplest way to prove the weak duality of the Fenchel dual problem is via the optimality: \begin{align} p&:=\inf_x\{f(x)+g(Ax)\} = \inf_x\{f(x)+g(Ax)-x^\top A^*y + x^\top A^*y\} \\ & = \inf_x\{f(x)+g(Ax)-\langle x, A^*y\rangle - \langle Ax,-y\rangle\} \end{align} By the basic property of the infimum (optimality), for any $y$, we have \begin{align} p&\geq \inf_x\{f(x)-\langle x, A^*y\rangle\} + \inf_x\{g(Ax) - \langle Ax,-y\rangle\} \\ &=-f^*(A^*y) - g^*(-y)\\ \end{align} Hence, \begin{equation} p\geq \sup_y\{-f^*(A^*y) - g^*(-y)\} = d \end{equation}