共轭函数与凸优化：理论、实例与性质

1.共轭函数

设函数f:Rn→Rf:\mathrm{R}^{n}\rightarrow \mathrm{R}f:Rn→R，定义函数f∗:Rn→Rf^{*}:\mathrm{R}^{n}\rightarrow\mathrm{R}f∗:Rn→R为f∗(y)=sup⁡x∈dom(y⊤x−f(x))，f^{*}(y)=\underset{x \in \mathrm{dom}}{\operatorname{sup}}(y^{\top}x-f(x))，f∗(y)=x∈domsup​(y⊤x−f(x))，此函数称为函数fff的共轭函数。使上述上确界有限，即差值y⊤x−f(x)y^{\top}x-f(x)y⊤x−f(x)在domf\mathrm{dom}fdomf有上界的所有y∈Rny \in \mathrm{R}^{n}y∈Rn构成共轭函数的定义域。

如上图所示，函数f:R→Rf:\mathrm{R}\rightarrow\mathrm{R}f:R→R以及某一y∈Ry \in \mathrm{R}y∈R。共轭函数f∗(y)f^{*}(y)f∗(y)是线性函数yxyxyx和f(x)f(x)f(x)之间的最大差值，见红色虚线所示。如果fff可微，在满足f′(x)=yf^{\prime}(x)=yf′(x)=y的点xxx处差值最大。显而易见，f∗f^{*}f∗是凸函数，这是因为它是一系列yyy的凸函数（实质上是仿射函数）的逐点上确界。无论fff是否是凸函数，f∗f^{*}f∗都是凸函数（注意到这里当fff是凸函数时，下标x∈domfx \in \mathrm{dom}fx∈domf可以去掉，这里是因为根据之前关于扩展延伸的定义，对于x∉domf,y⊤x−f(x)=−∞x \notin \mathrm{dom}f,y^{\top}x-f(x)=-\inftyx∈/​domf,y⊤x−f(x)=−∞）

2.具体实例

2.1 凸函数的共轭函数

仿射函数 f(x)=ax+bf(x)=ax+bf(x)=ax+b：作为xxx的函数，当且仅当y=ay=ay=a，即为常数时，yx−ax−byx-ax-byx−ax−b有界。因此共轭函数f∗f^{*}f∗的定义域为单点集{a}\{a\}{a}，且f∗(a)=−bf^{*}(a)=-bf∗(a)=−b。 负对数函数f(x)=−log⁡xf(x)=-\log xf(x)=−logx：定义域为domf=R++\mathrm{dom}f=\mathrm{R}^{++}domf=R++。当y≥0y \geq 0y≥0时，函数xy+log⁡xxy+\log xxy+logx无上界，当y<0y < 0y<0时，在x=−1/yx=-1/yx=−1/y处函数达到最大值。因此，定义域domf∗={y∣y<0}=−R++\mathrm{dom}f^{*}=\{y|y<0\}=-\mathrm{R}_{++}domf∗={y∣y<0}=−R++​，共轭函数为f∗(y)=−log⁡(−y)−1(y<0)f^{*}(y)=-\log(-y)-1(y<0)f∗(y)=−log(−y)−1(y<0)。指数函数f(x)=exf(x)=e^{x}f(x)=ex：当y<0y<0y<0时，函数xy−exxy-e^{x}xy−ex无界。当y>0y>0y>0时，函数xy−exxy-e^{x}xy−ex在x=log⁡yx=\log yx=logy处达到最大值。因此，f∗(y)=ylog⁡y−yf^{*}(y)=y\log y-yf∗(y)=ylogy−y。当y=0y=0y=0s时，f∗(y)=supx−ex=0f^{*}(y)=\underset{x}{\mathrm{sup}}-e^{x}=0f∗(y)=xsup​−ex=0。综合起来，domf∗=R+\mathrm{dom}f^{*}=\mathrm{R}_{+}domf∗=R+​，f∗(y)=ylog⁡y−yf^{*}(y)=y\log y-yf∗(y)=ylogy−y（其中规定0log⁡0=00\log 0=00log0=0）。负熵函数f(x)=xlogxf(x)=xlogxf(x)=xlogx：定义域为domf=R+\mathrm{dom}f=\mathrm{R}_{+}domf=R+​。对所有yyy，函数xy−xlog⁡xxy-x\log xxy−xlogx关于xxx在R+\mathrm{R}_{+}R+​上有界，因此domf∗=R\mathrm{dom}f^{*}=\mathrm{R}domf∗=R。在x=ey−1x=e^{y-1}x=ey−1处，函数达到最大值。因此f∗(y)=ey−1f^{*}(y)=e^{y-1}f∗(y)=ey−1。 反函数f(x)=1/xf(x)=1/xf(x)=1/x：当y>0y>0y>0时，yx−1/xyx-1/xyx−1/x无上界。当y=0y=0y=0时，函数有上确界0；当y<0y<0y<0时，在x=(−y)−1/2x=(-y)^{-1/2}x=(−y)−1/2处达到上确界。因此，f∗(y)=−2(−y)1/2f^{*}(y)=-2(-y)^{1/2}f∗(y)=−2(−y)1/2且domf∗=−R+\mathrm{dom}f^{*}=-\mathrm{R}_{+}domf∗=−R+​。

2.2 严格凸的二次函数

考虑函数f(x)=12x⊤Qx,Q∈S++nf(x)=\frac{1}{2}x^{\top}Qx,Q \in S^{n}_{++}f(x)=21​x⊤Qx,Q∈S++n​。对所有的yyy，xxx的函数y⊤x−12x⊤Qxy^{\top}x-\frac{1}{2}x^{\top}Qxy⊤x−21​x⊤Qx都有上界并在x=Q−1yx=Q^{-1}yx=Q−1y处达到上确界，因此f∗(y)=12y⊤Q−1y.f^{*}(y)=\frac{1}{2}y^{\top}Q^{-1}y.f∗(y)=21​y⊤Q−1y.

2.3 对数行列式

考虑S++n\mathrm{S}_{++}^{n}S++n​上定义的函数f(X)=log⁡det⁡X−1f(X)=\log \det X^{-1}f(X)=logdetX−1。其共轭函数定义为f∗(Y)=supX≻0(tr(YX)+log⁡det⁡X),f^{*}(Y)=\underset{X \succ 0}{\mathrm{sup}}(\mathrm{tr}(YX)+\log \det X),f∗(Y)=X≻0sup​(tr(YX)+logdetX),其中，tr(YX)\mathrm{tr}(YX)tr(YX)是Sn\mathrm{S}^{n}Sn上的标准内积。首先说明当只有Y≺0Y\prec 0Y≺0时，tr(YX)+log⁡det⁡X\mathrm{tr}(YX)+\log \det Xtr(YX)+logdetX才有上界。如果Y⊀0Y \nprec 0Y⊀0，则有YYY有特征向量vvv，∥v∥2=1\|v\|_2=1∥v∥2​=1且对应的特征值λ≥0\lambda \geq 0λ≥0。令X=I+tvv⊤X=I+tvv^{\top}X=I+tvv⊤，则有tr(YX)+log⁡det⁡X=trY+tλ+log⁡det⁡(I+tvv⊤)=trY+tλ+log⁡(1+t),\mathrm{tr}(YX)+\log \det X =\mathrm{tr} Y +t\lambda+\log \det(I+tvv^{\top})=\mathrm{tr} Y+t\lambda+\log(1+t),tr(YX)+logdetX=trY+tλ+logdet(I+tvv⊤)=trY+tλ+log(1+t),当t→∞t \rightarrow \inftyt→∞时，上式无界。接下来考虑Y≺0Y \prec 0Y≺0的情形，为了求最大值，令对XXX的偏导为零，则∇X(tr(YX)+log⁡det⁡X)=Y+X−1=0\nabla_X(\mathrm{tr}(YX)+\log \det X)=Y+X^{-1}=0∇X​(tr(YX)+logdetX)=Y+X−1=0得X=−Y−1X=-Y^{-1}X=−Y−1（XXX是正定的）。因此f∗(Y)=log⁡det⁡(−Y)−1−n,f^{*}(Y)=\log \det(-Y)^{-1}-n,f∗(Y)=logdet(−Y)−1−n,其定义域为domf∗=−S++n\mathrm{dom}f^{*}=-\mathrm{S}_{++}^{n}domf∗=−S++n​。

2.4 示性函数

设ISI_SIS​是某个集合S⊆RnS \subseteq \mathrm{R}^nS⊆Rn（不一定是凸集）的示性函数，即当xxx在domIS=S\mathrm{dom}I_S=SdomIS​=S内时，IS(x)=0I_S(x)=0IS​(x)=0。示性函数的共轭函数为IS∗(y)=supx∈Sy⊤x,I^{*}_S(y)=\underset{x \in S}{\mathrm{sup}}y^{\top}x,IS∗​(y)=x∈Ssup​y⊤x,它是集合SSS的支撑函数。

2.5 指数和的对数函数

为了得到指数和的对数函数f(x)=log⁡(∑i=1nexi)f(x)=\log (\sum\limits_{i=1}^{n}e^{x_i})f(x)=log(i=1∑n​exi​)的共轭函数，首先考察yyy取何值时y⊤x−f(x)y^{\top}x-f(x)y⊤x−f(x)的最大值可以得到。对xxx求导，令其为零，得到如下条件：yi=exi∑j=1nexj,i=1,⋯ ,n.y_i=\frac{e^{x_i}}{\sum\limits_{j=1}^{n}e^{x_j}},i=1,\cdots,n.yi​=j=1∑n​exj​exi​​,i=1,⋯,n.当且仅当y≻0y \succ 0y≻0以及1⊤y=1\boldsymbol{1}^{\top}y=11⊤y=1时上述方程有解。将yiy_iyi​的表达式代入y⊤x−f(x)y^{\top}x-f(x)y⊤x−f(x)可得f∗(y)=∑i=1nyilog⁡yif^{*}(y)=\sum\limits_{i=1}^{n}y_i\log y_if∗(y)=i=1∑n​yi​logyi​。根据前面的约定，0log⁡00 \log 00log0等于0，因此只要满足y⪰0y \succeq 0y⪰0以及1⊤y=1\boldsymbol{1}^{\top}y=11⊤y=1，即使当yyy的某些分量为零时，f∗f^{*}f∗的表达式仍然正确。

&esmsp; 事实上f∗f^{*}f∗的定义域即为1⊤y=1,y⪰0\boldsymbol{1}^{\top}y=1,y \succeq01⊤y=1,y⪰0。为了说明这一点，假设yyy的某个分量是负的，比如说yk<0y_k < 0yk​<0，令xk=−tx_k=-txk​=−t，xi=0x_i=0xi​=0，i≠ki \neq ki​=k，令ttt趋向于无穷，y⊤x−f(x)y^{\top}x-f(x)y⊤x−f(x)无上界。如果y⪰0y \succeq 0y⪰0但是1⊤y≠1\boldsymbol{1}^{\top}y \neq11⊤y​=1，令x=t1x=t_1x=t1​，可得y⊤x−f(x)=t1⊤y−t−log⁡n.y^{\top}x-f(x)=t_1^{\top}y-t-\log n.y⊤x−f(x)=t1⊤​y−t−logn.若1⊤y>1\boldsymbol{1}^{\top}y>11⊤y>1，当t→∞t \rightarrow \inftyt→∞时上述表达式无界；当1⊤y<1\boldsymbol{1}^{\top}y < 11⊤y<1时，若t→t \rightarrowt→时其无界。总之f∗(y)={∑i=1nyilog⁡yiy⪰0and1⊤y=1∞otherwisef^{*}(y)=\left\{\begin{array}{ll}\sum\limits_{i=1}^{n}y_i \log y_i & y \succeq 0 \text{and} \boldsymbol{1}^{\top}y=1 \\ \infty &\mathrm{otherwise}\end{array}\right.f∗(y)=⎩⎨⎧​i=1∑n​yi​logyi​∞​y⪰0and1⊤y=1otherwise​换言之，指数和的对数函数的共轭函数是概率单纯形内的负熵函数。

2.6 范数

令∥⋅∥\|\cdot\|∥⋅∥表示Rn\mathrm{R}^{n}Rn上的范数，其对偶范数为∥⋅∥∗\|\cdot\|_{*}∥⋅∥∗​。则其共轭函数为f∗(y)={0∥y∥∗≤1∞otherwisef^{*}(y)=\left\{\begin{array}{ll}0 & \|y\|_{*}\leq 1\\\infty&\mathrm{otherwise}\end{array}\right.f∗(y)={0∞​∥y∥∗​≤1otherwise​即范数的共轭函数是对偶范数单位球的示性范数。如果∥y∥∗>1\|y\|_{*}>1∥y∥∗​>1，根据对偶范数的定义，存在z∈Rnz \in \mathrm{R}^{n}z∈Rn，∥z∥≤1\|z\|\leq1∥z∥≤1使得y⊤z>1y^{\top}z>1y⊤z>1。取x=tzx=tzx=tz，令t→∞t \rightarrow\inftyt→∞可得y⊤x−∥x∥=t(y⊤z−∥z∣∣)→∞,y^{\top}x-\|x\|=t(y^{\top}z-\|z||)\rightarrow \infty,y⊤x−∥x∥=t(y⊤z−∥z∣∣)→∞,即f∗(y)=∞f^{*}(y)=\inftyf∗(y)=∞，没有上界。反之，若∥y∥∗≤1\|y\|_{*}\leq 1∥y∥∗​≤1，对任意xxx，有y⊤x≤∥x∥∥y∥∗y^{\top}x \leq \|x\|\|y\|_{*}y⊤x≤∥x∥∥y∥∗​，即对任意xxx，y⊤x−∥x∥≤0y^{\top}x-\|x\|\leq 0y⊤x−∥x∥≤0。因此，在x=0x=0x=0处，y⊤x−∥x∥y^{\top}x-\|x\|y⊤x−∥x∥达到最大值0。

2.7 范数的平方

考虑函数f(x)=12∥x∥2f(x)=\frac{1}{2}\|x\|^{2}f(x)=21​∥x∥2，其中∥⋅∥\|\cdot\|∥⋅∥是范数，对偶范数为∥⋅∥∗\|\cdot\|_{*}∥⋅∥∗​。此函数的共轭函数为f∗(y)=12∥y∥∗2f^{*}(y)=\frac{1}{2}\|y\|_{*}^{2}f∗(y)=21​∥y∥∗2​。由y⊤x≤∥y∥∗∥x∥y^{\top}x \leq\|y\|_{*}\|x\|y⊤x≤∥y∥∗​∥x∥可知，对任意xxx下式成立y⊤x−12∥x∥2≤∥y∥∗∥x∥−12∥x∥2.y^{\top}x-\frac{1}{2}\|x\|^2\leq \|y\|_{*}\|x\|-\frac{1}{2}\|x\|^2.y⊤x−21​∥x∥2≤∥y∥∗​∥x∥−21​∥x∥2.上式右端是∥x∥\|x\|∥x∥的二次函数，其最大值为(1/2)∥y∥∗2(1/2)\|y\|^2_{*}(1/2)∥y∥∗2​。因此对任意xxx，则有y⊤x−(1/2)∥x∥2≤(1/2)∥y∥∗2,y^{\top}x-(1/2)\|x\|^{2}\leq(1/2)\|y\|_{*}^{2},y⊤x−(1/2)∥x∥2≤(1/2)∥y∥∗2​,即f∗(y)≤(1/2)∥y∥∗2f^{*}(y)\leq(1/2)\|y\|^{2}_{*}f∗(y)≤(1/2)∥y∥∗2​。为了说明f∗(y)≥(1/2)∥y∥∗f^{*}(y)\geq(1/2)\|y\|_{*}f∗(y)≥(1/2)∥y∥∗​，任取满足y⊤x=∥y∥∗∥x∥y^{\top}x=\|y\|_{*}\|x\|y⊤x=∥y∥∗​∥x∥的向量xxx，对其进行伸缩使得∥x∥=∥y∥∗\|x\|=\|y\|_{*}∥x∥=∥y∥∗​。对于此xxx有y⊤x−(1/2)∥x∥2=(1/2)∥y∥∗2,y^{\top}x-(1/2)\|x\|^{2}=(1/2)\|y\|^{2}_{*},y⊤x−(1/2)∥x∥2=(1/2)∥y∥∗2​,因此f∗(y)≥(1/2)∥y∥∗2f^{*}(y)\geq (1/2)\|y\|_{*}^{2}f∗(y)≥(1/2)∥y∥∗2​。

3.基本性质

3.1 Fenchel 不等式

从共轭函数的定义可以得到，对任意xxx和yyy，如下不等式成立f(x)+f(y)≥x⊤y,f(x)+f(y)\geq x^{\top}y,f(x)+f(y)≥x⊤y,上述不等式为Fenchel不等式（当fff可微的时候亦称Young不等式）。

以函数f(x)=(1/2)x⊤Qxf(x)=(1/2)x^{\top}Qxf(x)=(1/2)x⊤Qx为例，其中Q∈S++nQ \in \mathrm{S}^{n}_{++}Q∈S++n​，可以得到如下不等式 x⊤y≤(1/2)x⊤Qx+(1/2)y⊤Q−1y.x^{\top}y \leq (1/2)x^{\top}Qx+(1/2)y^{\top}Q^{-1}y.x⊤y≤(1/2)x⊤Qx+(1/2)y⊤Q−1y.

3.2 共轭的共轭

凸函数的共轭函数的共轭函数是原函数。也即：如果函数fff是凸函数且fff是闭的（即epif\mathrm{epi} fepif是闭集），则f∗∗=ff^{**}=ff∗∗=f。

3.3 可微函数

可微函数fff的共轭函数亦称为函数fff的Legendre变换。（为了区分一般情况和可微情况下所定义的共轭，一般函数的共轭有时称为Fenchel共轭。）

设函数fff是凸函数且可微，其定义域为domf=Rn\mathrm{dom}f=\mathrm{R}^{n}domf=Rn，使y⊤x−f(x)y^{\top}x-f(x)y⊤x−f(x)取最大的x∗x^{*}x∗满足y=∇f(x∗)y=\nabla f(x^{*})y=∇f(x∗)，反之，若x∗x^{*}x∗满足KaTeX parse error: Expected '}', got 'EOF' at end of input: …\nabla f(x^{*])，y^{\top}x-f(x)在x∗x^{*}x∗处取最大值。因此如果y=∇f(x∗)y=\nabla f(x^{*})y=∇f(x∗)，则有f∗(y)=x∗∇f(x∗)−f(x∗).f^{*}(y)=x^{*}\nabla f(x^{*})-f(x^{*}).f∗(y)=x∗∇f(x∗)−f(x∗).所以，给定任意yyy，我们可以求解梯度方程y=∇f(z)y=\nabla f(z)y=∇f(z)，从而得到yyy处的共轭函数f∗(y)f^{*}(y)f∗(y)。亦可以换个角度理解，任选z∈Rnz \in \mathrm{R}^{n}z∈Rn，令y=∇f(z)y=\nabla f(z)y=∇f(z)，则f∗(y)=z⊤∇f(z)−f(z).f^{*}(y)=z^{\top}\nabla f(z)-f(z).f∗(y)=z⊤∇f(z)−f(z).

3.4 伸缩变换和复合仿射变换

若a>0a>0a>0以及b∈Rb \in \mathrm{R}b∈R，g(x)=af(x)+bg(x)=af(x)+bg(x)=af(x)+b的共轭函数为g∗(y)=af∗(y/a)−bg^{*}(y)=af^{*}(y/a)-bg∗(y)=af∗(y/a)−b。设A∈Rn×nA \in \mathrm{R}^{n \times n}A∈Rn×n非奇异，b∈Rnb\in \mathrm{R}^{n}b∈Rn，则函数g(x)=f(Ax+b)g(x)=f(Ax+b)g(x)=f(Ax+b)的共轭函数为g∗(y)=f∗(A−⊤y)−b⊤A−⊤y,g^{*}(y)=f^{*}(A^{-\top}y)-b^{\top}A^{-\top}y,g∗(y)=f∗(A−⊤y)−b⊤A−⊤y,其定义域为domg∗=A⊤domf∗\mathrm{dom}g^{*}=A^{\top}\mathrm{dom}f^{*}domg∗=A⊤domf∗。

3.5 独立函数的和

如果函数f(u,v)=f1(u)+f1(v)f(u,v)=f_1(u)+f_1(v)f(u,v)=f1​(u)+f1​(v)，其中f1f_1f1​和f2f_2f2​是凸函数，且共轭函数分别为f1∗f^{*}_1f1∗​和f2∗f^{*}_2f2∗​，则f∗(w,z)=f1∗(w)+f2∗(z)f^{*}(w,z)=f^{*}_1(w)+f^{*}_2(z)f∗(w,z)=f1∗​(w)+f2∗​(z)换言之，独立函数的和的共轭函数是各个凸函数的共轭函数的和。（“独立”的含义是各个函数具有不同的变量。）