共轭函数（Legendre变换与Fenchel变换）

#! https://zhuanlan.zhihu.com/p/597399183 # 共轭函数（Legendre变换与Fenchel变换）

Legendre变换是物理（力学，热力学），数学中常用的一种变换。它把可微凸函数从关于原自变量x的函数变为关于点导数（梯度）的函数。也就是如果记\(k=\dfrac{df}{dx}\)，那么把原函数\((x,f(x))\)变换为\((k,f^*(k))\)。

但是Legendre变换要求函数可微，Fenchel变换可以理解为对Legendre变换的推广，作用类似而不需要函数是可微的。

Legendre变换（勒让德变换）

取原函数\(f(x)\)，我们现在来导出它的Legendre共轭函数\(f^*(x)\)。这里的\(x\in R^n\)。

设\(u(x) = \nabla f(x)\)。那么考虑\(f(x)\)的全微分形式， \[df(x) = dx\nabla f(x) = dxu(x)\]

注意到\(d(u^T(x)x ) = d(x)u(x) + d(u(x))x\)，即

\[ dxu(x) = d(u^T(x)x ) - d(u(x))x \]

带入上式就得到

\[ x d(u(x)) = d ( u^T(x)x - f(x) ) \]

记\(g(u) = u^Tx - f(x)\)，那么\(dg(u) = du \nabla g(u)\)，因为\(du\nabla g(u) = d(u) x\)，这就得到\(x = \nabla g(u)\)。

我们发现此时\(u(x) = \nabla f(x)\)，\(x = \nabla g(u)\)。因此这个\(g\)实际上就是我们所求的\(f^*\)。

我们得到\(f^*(u) = u^Tx - f(x)\)。

考虑它的几何意义，当\(x\in R\)，设它在x处的斜率为\(k(x)\)，那么\(f^*(k) = kx-f(x)\)。其值为\(f(x)\)在x处切线在y轴上的截距。所以几何意义上，\(f^*\)是在用一族切线来描述原曲线，把切线的斜率作为自变量，而截距作为因变量。

Fenchel变换

现在我们正式的给出共轭函数的定义，对于函数\(f:R^n \rightarrow R\)，定义函数\(f^* : R^n \rightarrow R\)为

\[ f^*(y) = \sup_{x\in dom \ f} (y^Tx-f(x)) \]

它具有这样一些性质

与Legendre变换的相容性

在f是凸的，且可微的情况下，Legendre变换与Fenchel变换是等价的。

证明并不困难。由于f是凸且可微的，\(h(x) = y^Tx-f(x)\)是凹的，因此它的最值点一定是梯度为0的点。

这一点满足\(\nabla h(x_0)=0\)，即\(\nabla f(x_0) = y\)。那么\(f^*(y) = \nabla f^T(x_0)x_0 - f(x_0)\)。这与Legendre变换是相容的。

Fenchel不等式

由定义，有

\[ f(x) + f^*(x) \ge x^Ty \]

共轭的共轭

“共轭”这个名称似乎暗示了共轭的共轭就是原函数，在Legendre变换的推导中也能看见这一点。实际上，如果f是凸函数且f是闭的，那么\(f^{**}=f\)。下面进行证明

取\(f^*(y) = \sup_x (y^Tx-f(x)) = \nabla f^T(x_0)x_0 - f(x_0)\)，那么

\[ f^{**}(x) = \sup_y (x^Ty-f^*(y))\\ = \sup_y (x^Ty-(\nabla f^T(x_0)x_0 - f(x_0)))\\ = \sup_y (\nabla f^T(x_0)(x-x_0) + f(x_0))\\ = \sup_{x_0} (f(x_0) + \nabla f^T(x_0)(x-x_0)) \]

由凸函数的性质，\(\sup_{x_0} (f(x_0) + \nabla f^T(x_0)(x-x_0)) = f(x)\)，这就证明了原结论。

独立函数的和

如果\(f(u,v) = f_1(u) + f_2(v)\)，其中\(f_1\)和\(f_2\)是凸函数，共轭函数为\(f_1^*\)和\(f_2^*\)，那么

\[ f^*(w,z) = f_1^*(w)+f_2^*(z) \]

仿射变换

对\(g(x)=af(x)+b\)有

\[ g^*(y) = af^*(y/a)-b \]

对\(g(x) = f(Ax+b)\)有

\[ g^*(y) = f^*(A^{-T}y) - b^TA^{-T}y \]