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

凸优化学习笔记 6:共轭函数个人博客地址 Glooow 欢迎光临 文章目录 1 共轭函数 1 1 定义 1 2 性质 1 3 例子 1 共轭函数 1 1 定义一个函数 fff 的共轭函数 conjugatefun 定义为 f y s

大家好,欢迎来到IT知识分享网。

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

1. 共轭函数

1.1 定义

一个函数 f f f共轭函数(conjugate function) 定义为
f ∗ ( y ) = sup ⁡ x ∈ dom f ( y T x − f ( x ) ) f^*(y)=\sup_{x\in\text{dom}f}(y^Tx-f(x)) f(y)=xdomfsup(yTxf(x))
在这里插入图片描述

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

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

在这里插入图片描述

1.2 性质

关于共轭函数有以下性质

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

凸二次函数 f ( x ) = ( 1 / 2 ) x T Q x f(x)=(1 / 2) x^{T} Q x f(x)=(1/2)xTQx with Q ∈ S + + n Q \in \mathbf{S}_{++}^{n} QS++n
f ∗ ( y ) = sup ⁡ x ( y T x − ( 1 / 2 ) x T Q x ) = 1 2 y T Q − 1 y \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)=21yTQ1y
指示函数 I S ∗ ( y ) = sup ⁡ { y T x ∣ x ∈ S } , I S ( x ) = 0 I_S^*(y)=\sup\{y^Tx|x\in S\},I_S(x)=0 IS(y)=sup{
yTxx
S},IS(x)=0
on dom I S = S \text{dom}I_S=S domIS=S

log-sum-exp 函数 f ( x ) = log ⁡ ∑ exp ⁡ x i f(x)=\log\sum\exp x_i f(x)=logexpxi
f ∗ ( y ) = { ∑ i = 1 n y i log ⁡ y i  if  y ⪰ 0  and  1 T y = 1 ∞  otherwise.  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=1nyilogyi if y0 and 1Ty=1 otherwise. 

范数 f ( x ) = ∥ x ∥ f(x)=\Vert x\Vert f(x)=x
f ∗ ( y ) = { 0 ∥ y ∥ ∗ ≤ 1 ∞  otherwise  f^{*}(y)=\left\{\begin{array}{ll} 0 & \|y\|_{*} \leq 1 \\ \infty & \text { otherwise } \end{array}\right. f(y)={
0y1 otherwise 

范数平方 f ( x ) = ( 1 / 2 ) ∥ x ∥ 2 f(x)=(1/2)\Vert x\Vert^2 f(x)=(1/2)x2
f ∗ ( y ) = ( 1 / 2 ) ∥ y ∥ ∗ 2 f^*(y)=(1/2)\Vert y\Vert_*^2 f(y)=(1/2)y2

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/158024.html

(0)
上一篇 2025-01-26 19:25
下一篇 2025-01-26 19:26

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信