Fenchel-Rockafellar duality problem: Show that weak duality holds, i.e., p≥−d . 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
 A: 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}
A: 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
A: 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}
