Application of Fenchel Young- Inequality

Question

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?

Answer 1

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$.

Answer 2

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*}