Application of Fenchel Young- Inequality i'm stuck on the weak duality ineqiality.
For $X,Y$ euclidean spaces: $f: X\rightarrow (-\infty,\infty]$, $g: Y\rightarrow (-\infty,\infty]$ and $A:X\rightarrow Y$ linear bounded mapping.
I want to show that $\inf_{x\in X}\{f(x)+g(Ax)\}\geq \sup_{y \in Y}\{-f^{*}(A^{*}y)-g^{*}(-y)\}  $
I use the Fenchel Young inequality to do so: for $u \in X$ and $x \in dom(f)$ it holds $f(x)+f^{*}(u)\geq <u,x>$, where $f^{*}$ is the fenchel conjugate.
Starting now:
$\inf_{x\in X}\{f(x)+g(Ax)\}\geq \inf_{x\in X}\{-f^{*}(x^{*})+<x^{*},x>+g(Ax)\},x^{*}\in X$ arbitary $\geq \inf_{x\in X}\{-f^{*}(x^{*})+<x^{*},x>+<-y,Ax>+g^{*}(-y)\}$, $x^{*}\in X,y\in Y$ arbitary
Since they are arbitary i would choose such that  $x^{*}=A^{*}y$ holds. But how i get the supremum, to finish the proof?
 A: One approach is to reformulate the primal problem as 
\begin{align*}
\operatorname*{minimize}_{x,y} & \quad f(x) + g(y) \\
\text{subject to} & \quad y = Ax.
\end{align*}
Now formulate the dual problem.  The Lagrangian is
\begin{equation*}
L(x,y,z) = f(x) + g(y) + \langle z, y - Ax \rangle
\end{equation*}
and the dual function is
\begin{align*}
G(z) &= \inf_{x,y} L(x,y,z) \\
&= -f^*(A^Tz) - g^*(-z).
\end{align*}
The dual problem is
\begin{align*}
\operatorname*{maximize}_z & \quad -f^*(A^Tz) - g^*(-z).
\end{align*}
The standard weak duality result from convex optimization now tells us that $p^\star \geq d^\star$, where $p^\star$ and $d^\star$ are the primal and dual optimal values.
In other words,
\begin{equation*}
\inf_x f(x) + g(Ax) \geq \sup_z -f^*(A^T z) - g^*(-z).
\end{equation*}
A: Proving that $\inf_x \dots\ge \sup_y \dots$ means proving that the inequality holds for every $x$ and every $y$. 
Thus, you want to show that for every $x\in X$ and for every $y\in Y$
$$f(x)+g(Ax) \ge -f^*(A^*y) - g^*(-y)$$
or, equivalently, 
$$f(x)+f^*(A^*y) + g(Ax) + g^*(-y)\ge 0$$
By the Fenchel-Young inequality, the left hand side is at least 
$$\langle x, A^*y\rangle  + \langle   Ax, -y\rangle  $$
which is evidently $0$.
