共轭函数

定义

设函数 $f:{\mathbf{R}}^n\to \mathbf{R}$，其共轭函数 $f^{\ast }:{\mathbf{R}}^n\to \mathbf{R}$ 为

$$f^{\ast }(y)=\underset{x\in \mathrm{dom}f}{sup}(y^{\mathrm{\top }}x-f(x))$$

几何意义

共轭函数的几何意义如图所示。教材当中仅仅只是简略说明了这张图，但实际上这张图并不是特别容易理解。下面详细说明如何将这张图和共轭函数的定义结合起来理解。

首先，我们要明确的一点是，在共轭函数的定义中，自变量是 $y$，而不是 $x$，$x$ 应该当成常数或者参数。而在上面的函数图像中，自变量是 $x$，而不是 $y$，$y$ 应该当成常数或者参数。

因此，一元函数 $f(x)$ 的图像就可以画在平面直角坐标系中（图中蓝色曲线）。这里为了方便并且直观地说明，假设 $f:\mathbf{R}\to \mathbf{R}$。由于 $y$ 被当成常数，$yx$ 就是正比例函数，其图像是过原点的倾斜直线（图中上方虚线）。

因此，共轭函数的定义可以用自然语言描述为：直线（超平面）$y^{\mathrm{\top }}x$ 与 $f(x)$ 函数值的最大差值，并且该差值的取值与 $y^{\mathrm{\top }}$ 的取值一一对应——任意改变直线的斜率（超平面的方向向量），都有唯一确定的一个值与之对应。

显然，$f^{\ast }$ 是凸函数，这是因为它是在求一系列值的逐点上确界。而且，无论 $f$ 是否为凸函数，$f^{\ast }$ 都是凸函数。如果 $f$ 是凸函数，那么就没必要限制 $x\in \mathrm{dom}f$ 了。这是因为根据之前关于扩展值延伸的定义，对于 $x\notin \mathrm{dom}f$，$y^{\mathrm{\top }}x-f(x)=-\mathrm{\infty }$。

举例

仿射函数

$$f(x)=ax+b$$

当且仅当 $y=a$ 时，$yx-ax-b=-b$ 有界。因此，仿射函数的共轭函数为

$$f^{\ast }(y)=-b,\mathrm{dom}{f}^{\ast }=\{a\}$$

负对数函数

$$f(x)=-\log x,\mathrm{dom}f={\mathbf{R}}_{++}$$

当 $y>0$ 时，函数 $xy+\log x$ 无上界；当 $y<0$ 时，在 $x=-{\displaystyle \frac{1}{y}}$ 处取最大值。因此，负对数函数的共轭函数为

$$f^{\ast }(y)=-\log (-y)-1,\mathrm{dom}{f}^{\ast }=-{\mathbf{R}}_{++}$$

指数函数

$$f(x)=e^x$$

当 $y<0$ 时，函数 $xy-e^x$ 无界；当 $y>0$ 时，函数 $xy-e^x$ 在 $x=\ln y$ 处取最大值；当 $y=0$ 时，$f^{\ast }(y)=sup\{-e^x\}=0$。因此，指数函数的共轭函数为

$$f^{\ast }(y)=y\log y-y,\mathrm{dom}{f}^{\ast }={\mathbf{R}}_{+}$$

负熵函数

$$f(x)=x\log x,\mathrm{dom}f={\mathbf{R}}_{+}$$

对所有 $y$，函数 $xy-x\log x$ 关于 $x$ 在 ${\mathbf{R}}_{+}$ 上有上界，且在 $x=e^{y-1}$ 处取最大值。因此，负熵函数的共轭函数为

$$f^{\ast }(y)=e^{y-1}$$

反比例函数

$$f(x)={\displaystyle \frac{1}{x}},\mathrm{dom}f={\mathbf{R}}_{++}$$

当 $y>0$ 时，$yx-1/x$ 无上界；当 $y=0$ 时，函数有上确界 0；当 $y<0$ 时，在 $x=(-y{)}^{1/2}$ 处达到上确界。因此，反比例函数的共轭函数为

$$f^{\ast }(y)=-2(-y{)}^{1/2},\mathrm{dom}{f}^{\ast }={\mathbf{R}}_{+}$$

严格凸的二次函数

$$f(x)={\displaystyle \frac{1}{2}}{x}^{\mathrm{\top }}Qx,Q\in {\mathbf{S}}_{++}^n$$

对所有的 $y$，关于 $x$ 的函数 $y^{\mathrm{\top }}x-{\displaystyle \frac{1}{2}}{x}^{\mathrm{\top }}Qx$ 都有上界并在 $x=Q^{-1}y$ 处达到上确界。因此

$$f^{\ast }(y)={\displaystyle \frac{1}{2}}{y}^{\mathrm{\top }}{Q}^{-1}y$$

这是一个很好的性质，严格凸的二次函数求共轭函数只需要求其二次型矩阵的逆矩阵即可。

对数-行列式

$$f(X)=\log det{X}^{-1},X\in {\mathbf{S}}_{++}^n$$

其共轭函数定义为

$$\begin{array}{rl}{f}^{\ast }(Y)& =\underset{X\succ 0}{sup}\{\mathrm{tr}(YX)+\log detX\}\\ & =\log det(-Y{)}^{-1}-n,\mathrm{dom}{f}^{\ast }=-{\mathbf{S}}_{++}^n\end{array}$$

指数和的对数函数

$$f(x)=\log (\sum _{i=1}^n{e}^{x_i})$$

其共轭函数的推到稍微有些复杂，这里直接给出结果。

$$f^{\ast }(y)=\{\begin{array}{ll}\sum _{i=1}^n{y}_i\log y_i& y⪰0\wedge {\mathbf{1}}^{\mathrm{\top }}y=1\\ \mathrm{\infty }& \text{ otherwise }\end{array}$$

也就是说，指数和的对数函数的共轭函数是概率单纯形内的负熵函数。

范数

我们知道，${\mathbf{R}}^n$ 上的范数 $\parallel \cdot \parallel$ 的对偶范数为 $\parallel \cdot {\parallel }_{\ast }$。$f(x)=\parallel x\parallel$ 的共轭函数为

$$f^{\ast }(y)=\{\begin{array}{ll}0& \parallel y{\parallel }_{\ast }⩽1\\ \mathrm{\infty }& \text{ otherwise }\end{array}$$

基本性质

Fenchel 不等式

$$f(x)+f^{\ast }(y)⩾x^{\mathrm{\top }}y$$

如果 $f$ 可微，上式亦可称为 Young 不等式。

令 $f(x)={\displaystyle \frac{1}{2}}{x}^{\mathrm{\top }}Qx$，其中 $Q\in {\mathbf{S}}_{++}$，利用 Fenchel 不等式，我们可以如下结论：

$$x^{\mathrm{\top }}y⩽{\displaystyle \frac{1}{2}}{x}^{\mathrm{\top }}Qx+{\displaystyle \frac{1}{2}}{y}^{\mathrm{\top }}{Q}^{-1}y$$

共轭的共轭

我们学过的很多概念当中都包含“共轭”，例如共轭根式、共轭复数等。实际上“共轭”包含了“成对出现”这么一层意思。因此，共轭函数也有类似的性质。

$$f^{\ast \ast }=f$$

上述等式要求函数 $f$ 是凸的而且闭的。

Legendre 变换

可微函数 $f$ 的共轭函数亦称为函数 $f$ 的 Legendre 变换。

设函数 $f$ 是凸函数且可微，其定义域为 $\mathrm{dom}f={\mathbf{R}}^n$，使 $y^{\mathrm{\top }}x-f(x)$ 取最大的 $x^{\ast }$ 满足 $y=\mathrm{\nabla }f(x^{\ast })$，并且若 $x^{\ast }$ 满足 $y=\mathrm{\nabla }f(x^{\ast })$，$y^{\mathrm{\top }}x-f(x)$ 在 $x^{\ast }$ 处取最大值（二者等价）。因此，我们可以得到

$$f^{\ast }(y)=x^{\ast \mathrm{\top }}\mathrm{\nabla }f\left(x^{\ast }\right)-f\left(x^{\ast }\right)$$

有了这个结论，给定任意 $y$，我们可以求解梯度方程 $y=\mathrm{\nabla }f(z)$，从而得到 $y$ 处的共轭函数 $f^{\ast }(y)$。

我们也可以换一个角度理解。$\mathrm{\forall }z\in {\mathbf{R}}^n$，令 $y=\mathrm{\nabla }f(z)$，则

$$f^{\ast }(y)=z^{\mathrm{\top }}\mathrm{\nabla }f\left(z\right)-f\left(z\right)$$

伸缩变换和复合仿射变换

设 $a>0$，$b\in \mathbf{R}$，则伸缩变换及其共轭函数为

$$\begin{array}{rl}g(x)& =af(x)+b\\ g^{\ast }(y)& =a{f}^{\ast }(y/a)-b\end{array}$$

设 $A\in {\mathbf{R}}^{n\times n}$ 非奇异，$b\in {\mathbf{R}}^n$，则复合仿射变换及其共轭函数为

$$\begin{array}{rl}g(x)& =f(Ax+b)\\ g^{\ast }(y)& =f^{\ast }\left(A^{-\mathrm{\top }}y\right)-b^{\mathrm{\top }}{A}^{-\mathrm{\top }}y\end{array}$$

其定义域为 $\mathrm{dom}{g}^{\ast }=A^{\mathrm{\top }}\mathrm{dom}{f}^{\ast }$。

独立函数的和

设函数 $f_1$ 和 $f_2$ 都是凸函数，它们的独立函数

$$f(u,v)=f_1(u)+f_2(v)$$

的共轭函数为

$$f^{\ast }(w,z)=f_1^{\ast }(w)+f_2^{\ast }(z)$$

也就是说，独立凸函数的和的共轭函数是各个凸函数的共轭函数的和。