【优化】共轭函数(Conjugate Function)超简说明

共轭函数是最优化问题中非常重要的概念，常用来在原问题和对偶问题之间进行转换。

本文从便于理解的角度对其进行介绍，并推导常见例子。

本文主要参考S. Boyd and L. Vandenberghe, Convex Optimization中3.3节。

定义

对于原函数f(x),x∈Df(x),x\in Df(x),x∈D，其共轭函数为：

f∗(y)=sup⁡x∈D(−f(x))f^*(y)=\sup_{x\in D} (-f(x))f∗(y)=x∈Dsup​(−f(x))

其中，表示两个变量的内积

对于标量：=y⋅x=y\cdot x=y⋅x对于向量：=yTx=y^Tx=yTx对于n×nn\times nn×n对称矩阵：=tr(yx)=\textbf{tr} (yx)=tr(yx)

特别注意，共轭函数的定义域要求对x∈Dx\in Dx∈D，−f(x)-f(x)−f(x)有上界。即，f∗(y)f^*(y)f∗(y)不能为无穷大。

物理意义

对于共轭函数的每一个自变量y=yˉy=\bar{y}y=yˉ​，其取值相当于一条直线与原函数之差的最大值：

f∗(yˉ)=sup⁡x∈D(l(x)−f(x))f^*(\bar y)=\sup_{x\in D}(l(x)-f(x))f∗(yˉ​)=x∈Dsup​(l(x)−f(x))

这条直线l(x)=l(x)=<\bar y,x>l(x)=，其斜率由yˉ\bar yyˉ​决定。

两条曲线之差随着xxx变化，其最大值可以对xxx求导得到：

∂(−f(x))∂x=0⇒f′(x)=y\frac{\partial(-f(x))}{\partial x}=0 \Rightarrow f'(x)=y∂x∂(−f(x))​=0⇒f′(x)=y

即：曲线斜率与直线斜率相同处的xxx，能够得到最大值。

f∗(yˉ)=−f(xˉ),subject to f(xˉ)=yˉf^*(\bar y)=<\bar y, \bar x>-f(\bar x), subject\ to\ f(\bar x)=\bar yf∗(yˉ​)=−f(xˉ),subject to f(xˉ)=yˉ​

举例

Negative entropy

原函数：f(x)=xlog⁡x,x>0f(x)=x\log x, x>0f(x)=xlogx,x>0

原函数为增函数。

对于y<0y<0y<0，l(x)l(x)l(x)为减函数。则l(x)−f(x)l(x)-f(x)l(x)−f(x)为减函数，不超过其在零点取值。

对于y≥0y\geq 0y≥0，l(x)l(x)l(x)也是增函数

lim⁡x→∞l(x)/f(x)=lim⁡x→∞l′(x)/f′(x)=lim⁡x→∞y/(log⁡x+x)=0\lim_{x\to \infty} l(x)/f(x)=\lim_{x \to \infty} l'(x)/f'(x)=\lim_{x\to \infty} y/(\log x + x)=0x→∞lim​l(x)/f(x)=x→∞lim​l′(x)/f′(x)=x→∞lim​y/(logx+x)=0

l(x)l(x)l(x)增速小于f(x)f(x)f(x)增速，故其差有界。

故，f∗(y)f^*(y)f∗(y)的定义域为y∈Ry\in Ry∈R。

找到最大值处xxx的表达式：

xy−xlog⁡x∂x=0⇒x=ey−1\frac{xy - x\log x}{\partial x}=0 \Rightarrow x=e^{y-1}∂xxy−xlogx​=0⇒x=ey−1

代入共轭函数：

f∗(y)=y⋅ey−1−ey−1(y−1)=ey−1f^*(y)=y\cdot e^{y-1}-e^{y-1}(y-1)=e^{y-1}f∗(y)=y⋅ey−1−ey−1(y−1)=ey−1