凸优化学习笔记 6：共轭函数

个人博客地址 Glooow，欢迎光临~~~

1. 共轭函数

1.1 定义

一个函数 $f$f 的共轭函数(conjugate function) 定义为
$f^*(y)=\sup_{x\in\text{dom}f}(y^Tx-f(x))$f∗(y)=x∈domfsup​(yTx−f(x))

$f^*$f∗ 是凸函数，证明也很简单，可以看成是一系列关于 $y$y 的凸函数取上确界。

Remarks：实际上共轭函数与前面讲的一系列支撑超平面包围 $f$f 很类似，通过 $y$y 取不同的值，也就获得了不同斜率的支撑超平面，最后把 $f$f 包围起来，就好像是得到了 $\text{epi }f$epi f 的一个闭包，如下图所示

1.2 性质

关于共轭函数有以下性质

1. 若 $f$f 为凸的且是闭的($\text{epi }f$epi f 为闭集)，则 $f^{**}=f$f∗∗=f (可以联系上面提到一系列支撑超平面)
2. (Fenchel’s inequality) $f(x)+f^*(y)\ge x^Ty$f(x)+f∗(y)≥xTy，这可以类比均值不等式
3. (Legendre transform)如果 $f\in C^1$f∈C1，且为凸的、闭的，设 $x^*=\arg\max\{y^Tx-f(x)\}$x∗=argmax{yTx−f(x)}，那么有 $x^*=\nabla f^*(y)\iff y=\nabla f(x^*)$x∗=∇f∗(y)⟺y=∇f(x∗)。这可以用来求极值，比如 $\min f(x)\Longrightarrow 0=\nabla f(x)\iff x=\nabla f^*(0)$minf(x)⟹0=∇f(x)⟺x=∇f∗(0)

1.3 例子

常用的共轭函数的例子有

负对数函数 $f(x)=-\log x$f(x)=−logx
$\begin{aligned} f^{*}(y) &=\sup _{x>0}(x y+\log x) \\ &=\left\{\begin{array}{ll} -1-\log (-y) & y<0 \\ \infty & \text { otherwise } \end{array}\right. \end{aligned}$f∗(y)​=x>0sup​(xy+logx)={−1−log(−y)∞​y<0 otherwise ​​
凸二次函数 $f(x)=(1 / 2) x^{T} Q x$f(x)=(1/2)xTQx with $Q \in \mathbf{S}_{++}^{n}$Q∈S++n​
$\begin{aligned} f^{*}(y) &=\sup _{x}\left(y^{T} x-(1 / 2) x^{T} Q x\right) \\ &=\frac{1}{2} y^{T} Q^{-1} y \end{aligned}$f∗(y)​=xsup​(yTx−(1/2)xTQx)=21​yTQ−1y​
指示函数 $I_S^*(y)=\sup\{y^Tx|x\in S\},I_S(x)=0$IS∗​(y)=sup{yTx∣x∈S},IS​(x)=0 on $\text{dom}I_S=S$domIS​=S

log-sum-exp 函数 $f(x)=\log\sum\exp x_i$f(x)=log∑expxi​
$f^{*}(y)=\left\{\begin{array}{ll} \sum_{i=1}^{n} y_{i} \log y_{i} & \text { if } y \succeq 0 \text { and } \mathbf{1}^{T} y=1 \\ \infty & \text { otherwise. } \end{array}\right.$f∗(y)={∑i=1n​yi​logyi​∞​ if y⪰0 and 1Ty=1 otherwise. ​
范数 $f(x)=\Vert x\Vert$f(x)=∥x∥
$f^{*}(y)=\left\{\begin{array}{ll} 0 & \|y\|_{*} \leq 1 \\ \infty & \text { otherwise } \end{array}\right.$f∗(y)={0∞​∥y∥∗​≤1 otherwise ​
范数平方 $f(x)=(1/2)\Vert x\Vert^2$f(x)=(1/2)∥x∥2
$f^*(y)=(1/2)\Vert y\Vert_*^2$f∗(y)=(1/2)∥y∥∗2​