# Removing an unwanted constraint in proof of Fenchel-Rockafellar theorem

I am trying to prove the Fenchel-Rockafellar theorem, that $$\inf_x \left[ f(x) + g(Ax) \right] = - \inf_\beta \left[ f^\star(A^T \beta) + g^\star(-\beta) \right]$$

under the usual regularity assumptions. The general outline of my proof should work, but I run into problems at the last step:

1. Argue from Fenchel-Young inequality that $$\inf_x \left( f(x) + g(Ax) \right) = -(f + g\circ A)^\star(0)$$.
2. Compute $$(f + g \circ A)^\star$$ as the infimal convolution of $$f^\star$$ and $$(g \circ A)^\star$$, which gives $$\inf_x \left( f(x) + g(Ax) \right) = - \inf_{\beta} \left( f^\star(\beta) + (g \circ A)^\star(-\beta) \right)$$
3. Plug in the expression for $$(g \circ A)^\star(\beta)$$ and simplify.

The problem is that I get $$(g \circ A)^\star(\beta) = \begin{cases} \infty & \beta \not\in \mathcal{R}(A^T) \\ ( g + I_{\mathcal{R}(A)} )^\star(u) & \beta = A^T u \end{cases},$$ and computing the infimal convolution this can be written as $$(g \circ A)^\star(\beta) = \begin{cases} \infty & \beta \not\in \mathcal{R}(A^T) \\ \inf_{\substack{u=u_1 + u_2 \\ u_2 \in \mathcal{R}(A)^\perp}} g^\star(u_1) & \beta = A^T u \end{cases}.$$

When I plug this back in step 3, I get $$\inf_x \left( f(x) + g(Ax) \right) = - \inf_{\beta \in \mathcal{R}(A)} \left( f^\star(A^T \beta) + g^\star(-\beta) \right),$$ so I have an unwanted constraint on the right-hand side of the equality.

It may be that my calculations are wrong, but I've spent hours on them now, so I wonder if the issue is that the constraint is redundant?

• Start by expressing $g(Ax)$ as $\sup_\beta -\langle \beta,Ax\rangle - g^*(-\beta)$ and move $f(x)$ inside the sup. Exchanging the sup and the inf will need the regularity assumption. – Dirk Mar 14 at 21:24
• Thanks, that's embarrassingly straightforward. I still wonder why my approach fails, though. – AatG Mar 15 at 18:28
• The point of Fenchel(-Rockafellar) duality is to use the additive decomposition. You start by trying to conjugate the full function which is inherently different. And, by the way, your step 3 is wrong - there is no simple expression for the conjugate of $g\circ A$ (and even the simple case where A is invertible, the conjugate involves the inverse (if I remember correctly). – Dirk Mar 15 at 18:42