Saturday, October 1, 2022

Fenchel-Rockafellar duality: From Banach space to Hilbert space

Fenchel-Rockafellar duality theorem

Fenchel-Rockafellar duality: From Banach space to Hilbert space

Let B\mathbb{B}, H\mathbb{H} be respectively a Banach, Hilbert space. Let f:HRf: \mathbb{H} \longrightarrow \mathbb{R}, g:BRg: \mathbb{B} \longrightarrow \mathbb{R} and A:BHA: \mathbb{B} \longrightarrow \mathbb{H}. Consider the following ubiquitous primal problem
minxBf(Ax)+g(x)\min_{x\in \mathbb{B}} \hspace{0.5cm} f(Ax)+g(x)
It is well-known that the Fenchel-Rockafellar dual problem is
maxuHf(u)g(Au)\max_{u\in \mathbb{H}} \hspace{0.5cm} -f^*(-u)-g^*(A^*u)
where f:HRf^*: \mathbb{H} \longrightarrow \mathbb{R}, g:BRg^*: \mathbb{B^*} \longrightarrow \mathbb{R} and A:HBA^*: \mathbb{H} \longrightarrow \mathbb{B^*}. Here f,gf^*, g^* are convex conjugate of ff and gg, respectively, and AA^* is the adjoint operator of AA.

In this post, we would like to show this result by using the change of variable.
Let v=Axv=Ax, the primal problem can be rewritten, assuming that AA is surjective, i.e. ImA=H\text{Im}A=\mathbb{H},
minvHf(v)+g^(v)\min_{v\in \mathbb{H}} \hspace{0.5cm} f(v)+\hat{g}(v)
where g^(v):=inf{g(x):Ax=v}\hat{g}(v):= \inf \{g(x): Ax=v\}
By applying Fenchel duality problem, we obtain the following dual problem
maxxBf(u)g^(u)\max_{x\in \mathbb{B}} \hspace{0.5cm} -f^*(-u)-\hat{g}^*(u)
The rest is to show that
g^(u)=g(Au)\hat{g}^*(u)=g^*(A^*u)

Indeed,
g^(u)=supvu,vg^(u)=supxu,Axg(x)=g(Au)\hat{g}^*(u)=\sup_{v} \langle u, v\rangle - \hat{g}(u)= \sup_{x} \langle u, Ax\rangle - g(x)= g^*(A^*u)
We obtained desired result.

With this observation, we see that the second primal problem only involves the Hilbert space, which is more easier for theoretical analysis, for example, the optimality conditions.

Popular Posts