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?

  • $\begingroup$ 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. $\endgroup$ – Dirk Mar 14 at 21:24
  • $\begingroup$ Thanks, that's embarrassingly straightforward. I still wonder why my approach fails, though. $\endgroup$ – AatG Mar 15 at 18:28
  • $\begingroup$ 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). $\endgroup$ – Dirk Mar 15 at 18:42

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.