精华内容
下载资源
问答
  • 共轭函数

    千次阅读 2021-03-31 19:45:05
    共轭函数   设函数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 \...

    1.共轭函数

      设函数 f : R n → R f:\mathrm{R}^{n}\rightarrow \mathrm{R} f:RnR,定义函数 f ∗ : R n → R f^{*}:\mathrm{R}^{n}\rightarrow\mathrm{R} f:RnR f ∗ ( y ) = sup ⁡ x ∈ d o m ( y ⊤ x − f ( x ) ) , f^{*}(y)=\underset{x \in \mathrm{dom}}{\operatorname{sup}}(y^{\top}x-f(x)), f(y)=xdomsup(yxf(x))此函数称为函数 f f f的共轭函数。使上述上确界有限,即差值 y ⊤ x − f ( x ) y^{\top}x-f(x) yxf(x) d o m f \mathrm{dom}f domf有上界的所有 y ∈ R n y \in \mathrm{R}^{n} yRn构成共轭函数的定义域。

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

    2.具体实例

    2.1 凸函数的共轭函数

    • 仿射函数 f ( x ) = a x + b f(x)=ax+b f(x)=ax+b:作为 x x x的函数,当且仅当 y = a y=a y=a,即为常数时, y x − a x − b yx-ax-b yxaxb有界。因此共轭函数 f ∗ f^{*} f的定义域为单点集 { a } \{a\} {a},且 f ∗ ( a ) = − b f^{*}(a)=-b f(a)=b
    • 负对数函数 f ( x ) = − log ⁡ x f(x)=-\log x f(x)=logx:定义域为 d o m f = R + + \mathrm{dom}f=\mathrm{R}^{++} domf=R++。当 y ≥ 0 y \geq 0 y0时,函数 x y + log ⁡ x xy+\log x xy+logx无上界,当 y < 0 y < 0 y<0时,在 x = − 1 / y x=-1/y x=1/y处函数达到最大值。因此,定义域 d o m f ∗ = { y ∣ y < 0 } = − R + + \mathrm{dom}f^{*}=\{y|y<0\}=-\mathrm{R}_{++} domf={yy<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 ) = e x f(x)=e^{x} f(x)=ex:当 y < 0 y<0 y<0时,函数 x y − e x xy-e^{x} xyex无界。当 y > 0 y>0 y>0时,函数 x y − e x xy-e^{x} xyex x = log ⁡ y x=\log y x=logy处达到最大值。因此, f ∗ ( y ) = y log ⁡ y − y f^{*}(y)=y\log y-y f(y)=ylogyy。当 y = 0 y=0 y=0s时, f ∗ ( y ) = s u p x − e x = 0 f^{*}(y)=\underset{x}{\mathrm{sup}}-e^{x}=0 f(y)=xsupex=0。综合起来, d o m f ∗ = R + \mathrm{dom}f^{*}=\mathrm{R}_{+} domf=R+ f ∗ ( y ) = y log ⁡ y − y f^{*}(y)=y\log y-y f(y)=ylogyy(其中规定 0 log ⁡ 0 = 0 0\log 0=0 0log0=0)。
    • 负熵函数 f ( x ) = x l o g x f(x)=xlogx f(x)=xlogx:定义域为 d o m f = R + \mathrm{dom}f=\mathrm{R}_{+} domf=R+。对所有 y y y,函数 x y − x log ⁡ x xy-x\log x xyxlogx关于 x x x R + \mathrm{R}_{+} R+上有界,因此 d o m f ∗ = R \mathrm{dom}f^{*}=\mathrm{R} domf=R。在 x = e y − 1 x=e^{y-1} x=ey1处,函数达到最大值。因此 f ∗ ( y ) = e y − 1 f^{*}(y)=e^{y-1} f(y)=ey1
    • 反函数 f ( x ) = 1 / x f(x)=1/x f(x)=1/x:当 y > 0 y>0 y>0时, y x − 1 / x yx-1/x yx1/x无上界。当 y = 0 y=0 y=0时,函数有上确界0;当 y < 0 y<0 y<0时,在 x = ( − y ) − 1 / 2 x=(-y)^{-1/2} x=(y)1/2处达到上确界。因此, f ∗ ( y ) = − 2 ( − y ) 1 / 2 f^{*}(y)=-2(-y)^{1/2} f(y)=2(y)1/2 d o m f ∗ = − R + \mathrm{dom}f^{*}=-\mathrm{R}_{+} domf=R+

    2.2 严格凸的二次函数

      考虑函数 f ( x ) = 1 2 x ⊤ Q x , Q ∈ S + + n f(x)=\frac{1}{2}x^{\top}Qx,Q \in S^{n}_{++} f(x)=21xQx,QS++n。对所有的 y y y x x x的函数 y ⊤ x − 1 2 x ⊤ Q x y^{\top}x-\frac{1}{2}x^{\top}Qx yx21xQx都有上界并在 x = Q − 1 y x=Q^{-1}y x=Q1y处达到上确界,因此 f ∗ ( y ) = 1 2 y ⊤ Q − 1 y . f^{*}(y)=\frac{1}{2}y^{\top}Q^{-1}y. f(y)=21yQ1y.

    2.3 对数行列式

     考虑 S + + n \mathrm{S}_{++}^{n} S++n上定义的函数 f ( X ) = log ⁡ det ⁡ X − 1 f(X)=\log \det X^{-1} f(X)=logdetX1。其共轭函数定义为 f ∗ ( Y ) = s u p X ≻ 0 ( t r ( Y X ) + log ⁡ det ⁡ X ) , f^{*}(Y)=\underset{X \succ 0}{\mathrm{sup}}(\mathrm{tr}(YX)+\log \det X), f(Y)=X0sup(tr(YX)+logdetX),其中, t r ( Y X ) \mathrm{tr}(YX) tr(YX) S n \mathrm{S}^{n} Sn上的标准内积。首先说明当只有 Y ≺ 0 Y\prec 0 Y0时, t r ( Y X ) + log ⁡ det ⁡ X \mathrm{tr}(YX)+\log \det X tr(YX)+logdetX才有上界。如果 Y ⊀ 0 Y \nprec 0 Y0,则有 Y Y Y有特征向量 v v v ∥ v ∥ 2 = 1 \|v\|_2=1 v2=1且对应的特征值 λ ≥ 0 \lambda \geq 0 λ0。令 X = I + t v v ⊤ X=I+tvv^{\top} X=I+tvv,则有 t r ( Y X ) + log ⁡ det ⁡ X = t r Y + t λ + log ⁡ det ⁡ ( I + t v v ⊤ ) = t r Y + 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 \infty t时,上式无界。接下来考虑 Y ≺ 0 Y \prec 0 Y0的情形,为了求最大值,令对 X X X的偏导为零,则 ∇ X ( t r ( Y X ) + log ⁡ det ⁡ X ) = Y + X − 1 = 0 \nabla_X(\mathrm{tr}(YX)+\log \det X)=Y+X^{-1}=0 X(tr(YX)+logdetX)=Y+X1=0 X = − Y − 1 X=-Y^{-1} X=Y1 X X X是正定的)。因此 f ∗ ( Y ) = log ⁡ det ⁡ ( − Y ) − 1 − n , f^{*}(Y)=\log \det(-Y)^{-1}-n, f(Y)=logdet(Y)1n,其定义域为 d o m f ∗ = − S + + n \mathrm{dom}f^{*}=-\mathrm{S}_{++}^{n} domf=S++n

    2.4 示性函数

     设 I S I_S IS是某个集合 S ⊆ R n S \subseteq \mathrm{R}^n SRn(不一定是凸集)的示性函数,即当 x x x d o m I S = S \mathrm{dom}I_S=S domIS=S内时, I S ( x ) = 0 I_S(x)=0 IS(x)=0。示性函数的共轭函数为 I S ∗ ( y ) = s u p x ∈ S y ⊤ x , I^{*}_S(y)=\underset{x \in S}{\mathrm{sup}}y^{\top}x, IS(y)=xSsupyx,它是集合 S S S的支撑函数。

    2.5 指数和的对数函数

      为了得到指数和的对数函数 f ( x ) = log ⁡ ( ∑ i = 1 n e x i ) f(x)=\log (\sum\limits_{i=1}^{n}e^{x_i}) f(x)=log(i=1nexi)的共轭函数,首先考察 y y y取何值时 y ⊤ x − f ( x ) y^{\top}x-f(x) yxf(x)的最大值可以得到。对 x x x求导,令其为零,得到如下条件: y i = e x i ∑ j = 1 n e x j , i = 1 , ⋯   , n . y_i=\frac{e^{x_i}}{\sum\limits_{j=1}^{n}e^{x_j}},i=1,\cdots,n. yi=j=1nexjexi,i=1,,n.当且仅当 y ≻ 0 y \succ 0 y0以及 1 ⊤ y = 1 \boldsymbol{1}^{\top}y=1 1y=1时上述方程有解。将 y i y_i yi的表达式代入 y ⊤ x − f ( x ) y^{\top}x-f(x) yxf(x)可得 f ∗ ( y ) = ∑ i = 1 n y i log ⁡ y i f^{*}(y)=\sum\limits_{i=1}^{n}y_i\log y_i f(y)=i=1nyilogyi。根据前面的约定, 0 log ⁡ 0 0 \log 0 0log0等于0,因此只要满足 y ⪰ 0 y \succeq 0 y0以及 1 ⊤ y = 1 \boldsymbol{1}^{\top}y=1 1y=1,即使当 y y y的某些分量为零时, f ∗ f^{*} f的表达式仍然正确。
    &esmsp; 事实上 f ∗ f^{*} f的定义域即为 1 ⊤ y = 1 , y ⪰ 0 \boldsymbol{1}^{\top}y=1,y \succeq0 1y=1,y0。为了说明这一点,假设 y y y的某个分量是负的,比如说 y k < 0 y_k < 0 yk<0,令 x k = − t x_k=-t xk=t x i = 0 x_i=0 xi=0 i ≠ k i \neq k i=k,令 t t t趋向于无穷, y ⊤ x − f ( x ) y^{\top}x-f(x) yxf(x)无上界。如果 y ⪰ 0 y \succeq 0 y0但是 1 ⊤ y ≠ 1 \boldsymbol{1}^{\top}y \neq1 1y=1,令 x = t 1 x=t_1 x=t1,可得 y ⊤ x − f ( x ) = t 1 ⊤ y − t − log ⁡ n . y^{\top}x-f(x)=t_1^{\top}y-t-\log n. yxf(x)=t1ytlogn. 1 ⊤ y > 1 \boldsymbol{1}^{\top}y>1 1y>1,当 t → ∞ t \rightarrow \infty t时上述表达式无界;当 1 ⊤ y < 1 \boldsymbol{1}^{\top}y < 1 1y<1时,若 t → t \rightarrow t时其无界。总之 f ∗ ( y ) = { ∑ i = 1 n y i log ⁡ y i y ⪰ 0 and 1 ⊤ y = 1 ∞ o t h e r w i s e f^{*}(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=1nyilogyiy0and1y=1otherwise换言之,指数和的对数函数的共轭函数是概率单纯形内的负熵函数。

    2.6 范数

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

    2.7 范数的平方

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

    3.基本性质

    3.1 Fenchel 不等式

     从共轭函数的定义可以得到,对任意 x x x y y y,如下不等式成立 f ( x ) + f ( y ) ≥ x ⊤ y , f(x)+f(y)\geq x^{\top}y, f(x)+f(y)xy,上述不等式为Fenchel不等式(当 f f f可微的时候亦称Young不等式)。
      以函数 f ( x ) = ( 1 / 2 ) x ⊤ Q x f(x)=(1/2)x^{\top}Qx f(x)=(1/2)xQx为例,其中 Q ∈ S + + n Q \in \mathrm{S}^{n}_{++} QS++n,可以得到如下不等式 x ⊤ y ≤ ( 1 / 2 ) x ⊤ Q x + ( 1 / 2 ) y ⊤ Q − 1 y . x^{\top}y \leq (1/2)x^{\top}Qx+(1/2)y^{\top}Q^{-1}y. xy(1/2)xQx+(1/2)yQ1y.

    3.2 共轭的共轭

      凸函数的共轭函数的共轭函数是原函数。也即:如果函数 f f f是凸函数且 f f f是闭的(即 e p i f \mathrm{epi} f epif是闭集),则 f ∗ ∗ = f f^{**}=f f=f

    3.3 可微函数

      可微函数 f f f的共轭函数亦称为函数 f f f的Legendre变换。(为了区分一般情况和可微情况下所定义的共轭,一般函数的共轭有时称为Fenchel共轭。)
      设函数 f f f是凸函数且可微,其定义域为 d o m f = R n \mathrm{dom}f=\mathrm{R}^{n} domf=Rn,使 y ⊤ x − f ( x ) y^{\top}x-f(x) yxf(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)=xf(x)f(x).所以,给定任意 y y y,我们可以求解梯度方程 y = ∇ f ( z ) y=\nabla f(z) y=f(z),从而得到 y y y处的共轭函数 f ∗ ( y ) f^{*}(y) f(y)。亦可以换个角度理解,任选 z ∈ R n z \in \mathrm{R}^{n} zRn,令 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)=zf(z)f(z).

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

     若 a > 0 a>0 a>0以及 b ∈ R b \in \mathrm{R} bR g ( x ) = a f ( x ) + b g(x)=af(x)+b g(x)=af(x)+b的共轭函数为 g ∗ ( y ) = a f ∗ ( y / a ) − b g^{*}(y)=af^{*}(y/a)-b g(y)=af(y/a)b。设 A ∈ R n × n A \in \mathrm{R}^{n \times n} ARn×n非奇异, b ∈ R n b\in \mathrm{R}^{n} bRn,则函数 g ( x ) = f ( A x + 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(Ay)bAy,其定义域为 d o m g ∗ = A ⊤ d o m f ∗ \mathrm{dom}g^{*}=A^{\top}\mathrm{dom}f^{*} domg=Adomf

    3.5 独立函数的和

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

    展开全文
  • 在凸分析和凸优化中,凸函数的共轭函数是一个非常重要的概念.给定一个凸函数,要求出该函数的共轭函数,并对共轭函数的图像有一个直观清晰的了解并不容易.而一个函数的图像对理解该函数的性质非常重要.基于凸分析...
  • 1. 共轭函数   定义: 函数f:Rn→Rf:\mathrm{R}^{n} \rightarrow \mathrm{R}f:Rn→R的共轭函数f∗f^{*}f∗为:f∗(y)=sup⁡x∈domf(y⊤x−f(x))f^{*}(y)=\underset{x \in \boldsymbol{\mathrm{dom}} f}{\operator...

    1. 共轭函数

    定义: 函数 f : R n → R f:\mathrm{R}^{n} \rightarrow \mathrm{R} f:RnR的共轭函数 f ∗ f^{*} f为: f ∗ ( y ) = sup ⁡ x ∈ d o m f ( y ⊤ x − f ( x ) ) f^{*}(y)=\underset{x \in \boldsymbol{\mathrm{dom}} f}{\operatorname{sup}}(y^{\top}x-f(x)) f(y)=xdomfsup(yxf(x))事实上,共轭函数和Lagrange对偶函数紧密关联。下面的问题说明了一个简单的联系,考虑问题 m i n i m i z e f ( x ) s . t . x = 0 \begin{array}{ll}\mathrm{minimize} & f(x)\\ \mathrm{s.t.} & x = 0\end{array} minimizes.t.f(x)x=0可知上述问题的Lagrange函数为 L ( x , v ) = f ( x ) + v ⊤ x , L(x,v)=f(x)+v^{\top}x, L(x,v)=f(x)+vx,其对偶函数为 g ( v ) = i n f x ( f ( x ) + v ⊤ x ) = − s u p x ( ( − v ) ⊤ x − f ( x ) ) = − f ∗ ( − v ) g(v)=\underset{x}{\mathrm{inf}}(f(x)+v^{\top}x)=-\underset{x}{\mathrm{sup}}((-v)^{\top}x-f(x))=-f^{*}(-v) g(v)=xinf(f(x)+vx)=xsup((v)xf(x))=f(v)对于更一般地,考虑一个优化问题,其具有线性不等式以及等式约束, minimize ⁡ f 0 ( x ) s . t . A x ⪯ 0 C x = d . \begin{array}{ll}\operatorname{minimize}&f_0(x)\\\mathrm{s.t.}&Ax \preceq 0\\ &Cx =d.\end{array} minimizes.t.f0(x)Ax0Cx=d.利用函数 f 0 f_0 f0的共轭函数,可以将以上问题的对偶函数表述为 g ( λ , v ) = i n f x ( f 0 ( x ) + λ ⊤ ( A x − b ) + v ⊤ ( C x − d ) ) = − b ⊤ λ − d ⊤ v + i n f x ( f 0 ( x ) + ( A ⊤ λ + C ⊤ v ) ⊤ x ) = − b ⊤ λ − d ⊤ v − f 0 ∗ ( − A ⊤ λ − C ⊤ v ) . \begin{aligned}g(\lambda,v)&=\underset{x}{\mathrm{inf}}(f_0(x)+\lambda^{\top}(Ax-b)+v^{\top}(Cx-d))\\ &=-b^{\top}\lambda-d^{\top}v+\underset{x}{\mathrm{inf}}(f_0(x)+(A^{\top}\lambda+C^{\top}v)^{\top}x)\\ &= -b^{\top}\lambda-d^{\top}v-f^{*}_0(-A^{\top}\lambda-C^{\top}v).\end{aligned} g(λ,v)=xinf(f0(x)+λ(Axb)+v(Cxd))=bλdv+xinf(f0(x)+(Aλ+Cv)x)=bλdvf0(AλCv).函数 g g g的定义域也可以由函数 f 0 ∗ f^{*}_{0} f0的定义域得到, d o m = { ( λ , v ) ∣ − A ⊤ λ − C ⊤ v ∈ d o m f 0 ∗ } . \mathrm{dom}=\{(\lambda,v)|-A^{\top}\lambda-C^{\top}v \in \mathrm{dom} f^{*}_0\}. dom={(λ,v)AλCvdomf0}.

    等式约束条件下的范数极小化

     考虑问题 m i n i m i z e ∥ x ∥ s . t . A x = b , \begin{array}{ll}\mathrm{minimize} & \|x\|\\\mathrm{s.t.}&Ax=b,\end{array} minimizes.t.xAx=b,其中 ∥ ⋅ ∥ \|\cdot\| 是任意范数。已知 f 0 = ∥ ⋅ ∥ f_0=\|\cdot\| f0=的共轭函数为 f 0 ∗ ( y ) = { 0 ∥ y ∥ ∗ ≤ 1 ∞ o t h e r w i s e f^{*}_0(y)=\left\{\begin{array}{ll}0&\|y\|_{*} \leq 1\\\infty & \mathrm{otherwise}\end{array}\right. f0(y)={0y1otherwise可以看出此函数是对偶范数单位球的示性函数。可以得到等式约束条件下的范数极小化的对偶函数为 g ( v ) = − b ⊤ v − f 0 ∗ ( − A ⊤ v ) = { − b ⊤ v ∥ A ⊤ v ∥ ∗ ≤ 1 − ∞ o t h e r w i s e g(v)=-b^{\top}v-f^{*}_0(-A^{\top}v)=\left\{\begin{array}{ll}-b^{\top}v & \|A^{\top}v\|_{*}\leq 1\\ -\infty & \mathrm{otherwise} \end{array} \right. g(v)=bvf0(Av)={bvAv1otherwise

    熵的最大化

      考虑熵的最大化问题 m i n i m i z e f 0 ( x ) = ∑ i = 1 n x i log ⁡ x i s . t . A x ⪯ b 1 ⊤ x = 1 \begin{array}{ll}\mathrm{minimize}&f_0(x)=\sum\limits_{i=1}^{n}x_i \log x_i\\\mathrm{s.t.}&Ax \preceq b\\ &\boldsymbol{1}^{\top}x =1 \end{array} minimizes.t.f0(x)=i=1nxilogxiAxb1x=1其中 d o m f 0 = R + + n \mathrm{dom}f_0=\mathrm{R}^{n}_{++} domf0=R++n。关于实变量 u u u的负熵函数 u log ⁡ u u \log u ulogu的共轭函数是 e v − 1 e^{v-1} ev1。因为函数 f 0 f_0 f0是不同变量的负熵函数的和,其共轭函数为 f 0 ∗ ( y ) = ∑ i = 1 n e y i − 1 , f_0^{*}(y)=\sum\limits_{i=1}^{n}e^{y_i-1}, f0(y)=i=1neyi1,其定义域为 d o m f 0 ∗ = R n \mathrm{dom}f_0^{*}=\mathrm{R}^{n} domf0=Rn。则可知其对偶函数为 g ( λ , v ) = − b ⊤ λ − v − ∑ i = 1 n e − a i ⊤ λ − v − 1 = − b ⊤ λ − v − e − v − 1 ∑ i = 1 n e − a i ⊤ λ g(\lambda,v)=-b^{\top}\lambda-v-\sum\limits_{i=1}^{n}e^{-a^{\top}_i\lambda-v-1}=-b^{\top}\lambda-v-e^{-v-1}\sum\limits_{i=1}^{n}e^{-a^{\top}_i}\lambda g(λ,v)=bλvi=1neaiλv1=bλvev1i=1neaiλ

    最小体积覆盖椭球

      考虑关于变量 X ∈ S n X \in S^{n} XSn的问题 m i n i m i z e f 0 ( X ) = log ⁡ det ⁡ X − 1 s . t . a i ⊤ X a i ≤ 1 , i = 1 , ⋯   , m , \begin{array}{ll}\mathrm{minimize}&f_0(X)=\log \det X^{-1}\\ \mathrm{s.t.}&a_i^{\top}Xa_i \leq 1, \quad i=1,\cdots,m,\end{array} minimizes.t.f0(X)=logdetX1aiXai1,i=1,,m,其中 d o m f 0 = S + + n \mathrm{dom} f_0=\mathrm{S}^{n}_{++} domf0=S++n,其中以上问题有着简单的几何意义,对于任意 X ∈ S + + n X \in \mathrm{S}^{n}_{++} XS++n,将其与如下中心在原点的椭球联系起来,则有: ε x = { z ∣ z ⊤ X z ≤ 1 } . \varepsilon_x=\{z|z^{\top}Xz \leq 1\}. εx={zzXz1}.因为椭球的体积与 ( det ⁡ X − 1 ) 1 / 2 (\det X^{-1})^{1/2} (detX1)1/2成正比,所以此问题的目标函数实质上是椭球 ε x \varepsilon_x εx体积的对数的两倍并加上一个常数附加项。所以此问题的约束条件可以写成 a i ∈ ε x a_i \in \varepsilon_x aiεx。因此此问题等价于寻找能够包含点 a 1 , ⋯   , a m a_1,\cdots,a_m a1,,am的,并以原点为中心,具有最小体积的椭球。其不等式约束的放射可以表述为 t r ( ( a i a i ⊤ ) X ) ≤ 1. \mathrm{tr}((a_ia_i^{\top})X) \leq 1. tr((aiai)X)1.则其共轭函数为 f 0 ∗ ( Y ) = log ⁡ det ⁡ ( − Y ) − 1 − n , f^{*}_{0}(Y)=\log \det(-Y)^{-1}-n, f0(Y)=logdet(Y)1n,其中定义域 d o m f ∗ = − S + + n \mathrm{dom} f^{*}=-\mathrm{S}^{n}_{++} domf=S++n。则此问题的对偶函数为 g ( λ ) = { log ⁡ det ⁡ ( ∑ i = 1 m λ i a i a i ⊤ ) − 1 ⊤ λ + n ∑ i = 1 m λ i a i a i ⊤ ≻ 0 − ∞ o t h e r w i s e . g(\lambda)=\left\{\begin{array}{ll}\log \det\left(\sum\limits_{i=1}^{m}\lambda_ia_ia_i^{\top}\right)-\boldsymbol{1}^{\top}\lambda+n&\sum\limits_{i=1}^{m}\lambda_ia_ia_i^{\top} \succ 0\\-\infty&\mathrm{otherwise}.\end{array}\right. g(λ)=logdet(i=1mλiaiai)1λ+ni=1mλiaiai0otherwise.因此,对任意满足 ∑ i = 1 m λ i a i a i ⊤ ≻ 0 \sum\limits_{i=1}^{m}\lambda_ia_ia_i^{\top}\succ0 i=1mλiaiai0 λ ≻ 0 \lambda \succ0 λ0 λ \lambda λ,数值 log ⁡ det ⁡ ( ∑ i = 1 m λ i a i a i ⊤ ) − 1 ⊤ λ + n \log \det\left(\sum\limits_{i=1}^{m}\lambda_ia_ia_i^{\top}\right)-\boldsymbol{1}^{\top}\lambda+n logdet(i=1mλiaiai)1λ+n给出了问题的最优下界。

    展开全文
  • 复合函数的共轭函数例子

    千次阅读 2020-07-29 20:20:25
    求解复合函数的共轭函数 设A∈\in∈Rn×nR^{n\times n}Rn×n非奇异,b∈\in∈RnR^{n}Rn,g(x)=f(Ax+b)g(x)=f(Ax+b)g(x)=f(Ax+b),则其共轭函数为g∗(y)g^{*}(y)g∗(y)=f∗(A−Ty)−bTA−Tyf^{*}(A^{-T}y)-b^{T}A^{-T...

    求解复合函数的共轭函数

    设A ∈ \in R n × n R^{n\times n} Rn×n非奇异,b ∈ \in R n R^{n} Rn g ( x ) = f ( A x + b ) g(x)=f(Ax+b) g(x)=f(Ax+b),则其共轭函数为 g ∗ ( y ) g^{*}(y) g(y)= f ∗ ( A − T y ) − b T A − T y f^{*}(A^{-T}y)-b^{T}A^{-T}y f(ATy)bTATy.

    具体步骤

    g ∗ ( y ) = s u p { < x , y > − g ( x ) } g^{*}(y)=sup\{<x,y>-g(x)\} g(y)=sup{<x,y>g(x)}
    = s u p { < x , y > − f ( A x + b ) } \qquad=sup\{<x,y>-f(Ax+b)\} =sup{<x,y>f(Ax+b)}

    A x + b = z , 则 x = A − 1 ( z − b ) = A − 1 z − A − 1 b Ax+b=z,则x=A^{-1}(z-b)=A^{-1}z-A^{-1}b Ax+b=z,x=A1(zb)=A1zA1b ,则有

    g ∗ ( y ) = s u p { < x , y > − f ( A x + b ) } g^{*}(y)=sup\{<x,y>-f(Ax+b)\} g(y)=sup{<x,y>f(Ax+b)}
    = s u p { < A − 1 z − A − 1 b , y > − f ( z ) } \qquad=sup\{<A^{-1}z-A^{-1}b,y>-f(z)\} =sup{<A1zA1b,y>f(z)}
    = s u p { < A − 1 z , y > − < A − 1 b , y > − f ( z ) } \qquad=sup\{<A^{-1}z,y>-<A^{-1}b,y>-f(z)\} =sup{<A1zy><A1b,y>f(z)}
    = s u p { < A − 1 z , y > − < A − 1 b , y > − f ( z ) } \qquad=sup\{<A^{-1}z,y>-<A^{-1}b,y>-f(z)\} =sup{<A1zy><A1b,y>f(z)}
    = s u p { ( < A − 1 z , y > − f ( z ) ) − < A − 1 b , y > } \qquad=sup\{(<A^{-1}z,y>-f(z))-<A^{-1}b,y>\} =sup{(<A1zy>f(z))<A1b,y>}
    = s u p { ( < z , A − T y > − f ( z ) ) − < A − 1 b , y > } \qquad=sup\{(<z,A^{-T}y>-f(z))-<A^{-1}b,y>\} =sup{(<zATy>f(z))<A1b,y>}
    = f ∗ ( A − T y ) − b T A − T y \qquad=f^{*}(A^{-T}y)-b^{T}A^{-T}y =f(ATy)bTATy

    展开全文
  • 闭函数 一个函数称为闭函数如果它的上方图是一个闭集。 恰当函数 对于函数f:C→Rf: \mathit{C}\xrightarrow[]{} \mathbb{R}f:C​R,如果函数fff满足f(x)>−∞f(x)>...函数fff的共轭函数f∗f^*f∗定义为

    闭函数

    一个函数称为闭函数如果它的上方图是一个闭集。

    恰当函数

    对于函数 f : C → R f: \mathit{C}\xrightarrow[]{} \mathbb{R} f:C R,如果函数 f f f满足 f ( x ) > − ∞ f(x)>-\infty f(x)>对任意 x ∈ C x\in C xC均成立,且存在一点 x 0 ∈ C x_0\in C x0C,使得 f ( x ) < + ∞ f(x)<+\infty f(x)<+,我们就称函数 f f f C C C上是恰当的。

    共轭函数

    函数 f f f的共轭函数 f ∗ f^* f定义为:
    f ∗ ( y ) = sup ⁡ x ∈ d o m f ( y T x − f ( x ) ) f^*(y)=\sup_{x\in dom f} (y^T x-f(x)) f(y)=xdomfsup(yTxf(x))

    • 注意到,无论 f f f如何,共轭函数 f ∗ f^* f总是闭凸的。
    • 若函数 f f f是适当的,则 f ∗ f^* f不一定是适当的。但若 f f f是适当的凸函数,则 f ∗ f^* f也是适当的凸函数。

    定理1[Fenchel’s inequality]

    共轭函数的定义表明了
    f ( x ) + f ∗ ( y ) ≥ x T y ∀ x , y f(x)+f^*(y)\geq x^T y \qquad \qquad \forall x,y f(x)+f(y)xTyx,y

    二次共轭

    二次共轭定义为:
    f ∗ ∗ ( x ) = sup ⁡ y ∈ d o m f ∗ ( x T y − f ∗ ( y ) ) f^{**}(x)=\sup_{y\in dom f^*}(x^Ty-f^*(y)) f(x)=ydomfsup(xTyf(y))则有以下结论:
    (1) f ∗ ∗ f^{**} f是闭凸函数。
    (2)由定理3.1,我们知道有 x T y − f ∗ ( y ) ≤ f ( x ) , ∀ y , x x^Ty-f^*(y)\le f(x),\forall y,x xTyf(y)f(x),y,x,因此,我们有 f ∗ ∗ ( x ) ≤ f ( x ) , ∀ x f^{**}(x)\le f(x),\forall x f(x)f(x),x
    (3)如果 f f f是闭凸函数,则 f ∗ ∗ ( x ) = f ( x ) , ∀ x ∈ d o m f f^{**}(x)=f(x),\forall x\in dom f f(x)=f(x),xdomf

    (3)的证明:我们假设 f f f是闭凸函数,且 e p i   f ∗ ∗ ≠ e p i   f epi\,f^{**}\neq epi\,f epif=epif,而由(2)我们知道 e p i   f ⊆ e p i   f ∗ ∗ epi\,f\subseteq epi\,f^{**} epifepif,我们不妨假设 ( x , f ∗ ∗ ( x ) ) ∉ e p i   f (x,f^{**}(x))\notin epi\,f (x,f(x))/epif,由 e p i   f epi\,f epif的闭凸性,存在一个严格分离超平面:\
    [ a b ] T [ z − x s − f ∗ ∗ ( x ) ] ≤ c < 0 ∀   ( z , s ) ∈ e p i   f \begin{bmatrix} a\\b \end{bmatrix}^T \begin{bmatrix} z-x\\s-f^{**}(x) \end{bmatrix}\le c<0 \qquad \forall \,(z,s)\in epi\,f [ab]T[zxsf(x)]c<0(z,s)epif s → ∞ s\rightarrow \infty s,我们可以得到 b ≤ 0 b\le 0 b0

    • b < 0 b<0 b<0,我们设 y = − a / b y=-a/b y=a/b,将上式两边同除 − b -b b,并且对 ( z , s ) (z,s) (z,s)取最大值,有:
      f ∗ ( y ) − y T x + f ∗ ∗ ( x ) ≤ c − b < 0 f^*(y)-y^Tx+f^{**}(x)\le \frac{c}{-b}<0 f(y)yTx+f(x)bc<0这显然是与Fenchel’s inequality矛盾的。
    • b = 0 b=0 b=0,我们选取 y ^ ∈ d o m   f \hat{y}\in dom\,f y^domf,并选取足够小的 ϵ > 0 \epsilon>0 ϵ>0,则我们有:
      [ a + ϵ y ^ − ϵ ] T [ z − x s − f ∗ ∗ ( x ) ] ≤ c + ϵ ( f ∗ ( y ^ ) + f ∗ ∗ ( x ) − x T y ) < 0 \begin{bmatrix} a+\epsilon\hat{y}\\-\epsilon \end{bmatrix}^T\begin{bmatrix} z-x\\s-f^{**}(x) \end{bmatrix}\le c+\epsilon(f^*(\hat{y})+f^{**}(x)-x^Ty)<0 [a+ϵy^ϵ]T[zxsf(x)]c+ϵ(f(y^)+f(x)xTy)<0则化成了 b < 0 b<0 b<0的情况。
      则(3)成立。
    展开全文
  • 凸函数与共轭函数

    2021-09-12 16:12:23
    函数convex function 定义: 函数f:Rn→Rf:\mathbf{R}^n\rightarrow \mathbf{R}f:Rn→R是凸的,如果dom fdom\, fdomf(f的定义域)是凸集,且对于任意x,y∈dom fx,y\in dom\, fx,y∈domf和任意0≤θ≤10\leq \...
  • 深入理解共轭函数及相关性质解析

    千次阅读 2020-05-08 13:38:42
    共轭函数在凸优化中有着非常重要的作用,是理解对偶的必不可少的元素。在书中,它被定义为 f∗(y)=sup⁡x∈domf(yTx−f(x))f^*(y)=\sup_{x\in dom f}(y^Tx-f(x))f∗(y)=x∈domfsup​(yTx−f(x)) 其中,f:Rn→R,f∗:...
  • 凸优化学习笔记 6:共轭函数

    千次阅读 2020-03-05 00:02:08
    个人博客地址 Glooow,欢迎...1. 共轭函数 1.1 定义 一个函数 fff 的共轭函数(conjugate function) 定义为 f∗(y)=sup⁡x∈domf(yTx−f(x)) f^*(y)=\sup_{x\in\text{dom}f}(y^Tx-f(x)) f∗(y)=x∈domfsup​(yTx−f(x...
  • 一、 原函数的对偶函数和共轭函数 对偶函数 原函数 ==> 拉格朗日函数 ==> 对偶函数(拉格朗日对偶函数) f0f_0f0​ ==>L(x,λ\lambdaλ,v) ==>D(λ\lambdaλ,v) 这里就不具体写形式了,一定要搞清楚...
  • 范数的共轭函数

    千次阅读 2018-11-03 16:00:37
    共轭函数的定义;范数的共轭函数是其对偶范数单位球的示性函数。
  • 求下面问题的一系列共轭函数 (a) 最大值函数。函数f(x)=max⁡i=1,…,nxif(x)=\max_{i=1,\dots,n}x_if(x)=maxi=1,…,n​xi​,定义在Rn\mathbf{R}^nRn上。 (b) 最大若干分量之和。函数f(x)=∑i=1rx[i]f(x)=\sum_{i=1}...
  • 3.3 共轭函数 定义 基本性质 定义 设函数,定义函数为: 此函数称为f(x)的共轭函数。从3.2节逐点上确界的内容也可以看出,此函数也是的逐点上确界函数,而是关于y的仿射函数,可以将其看成是凸函数,这样也是...
  • 共轭函数两个性质的证明

    千次阅读 2019-02-18 13:40:04
    学习机器学习的时候有涉及到共轭函数(也叫对偶函数),这边文章总结一下共轭函数的学习 共轭函数的定义:对于函数 其定义如下: 表示函数的定义域,可以这样理解这个函数:首先它是关于的函数,给定一个 值时...
  • 用定义推导p范数的共轭函数
  • Fenchel共轭函数
  • 共轭函数和原函数的关系

    千次阅读 2018-06-14 15:01:36
    原函数约束很多,不一定是凸函数,也就是说原函数是一个也许有很多...通过求共轭函数,我们把它原函数映射到另一个多维空间(自变量都变了),变成一个新函数,这个函数是凸的,而且它的最大值小于等于原函数的最小...
  • 凸优化第三章凸函数 3.3共轭函数

    千次阅读 2019-01-18 12:53:28
    3.3共轭函数 定义 基本性质 定义 设函数,定义函数为: 此函数称为f(x)的共轭函数。从3.2节逐点上确界的内容也可以看出,此函数也是的逐点上确界函数,而是关于y的仿射函数,可以将其看成是凸函数,这样也是凸...
  • 示性函数(Indicator function) 共轭函数 对偶范数 几个常用公式
  • 复合仿射函数的共轭函数推导   posted on 2018-12-26 11:40 CreatorKou 阅读(...) 评论(...) 编辑 收藏
  • Matlab编写的共轭函数

    2009-09-12 20:51:33
    一个用MATLAB写的共轭函数,希望能对你有帮助!
  • 在Convex Optimization的第三章中提到了共轭函数的仿射变化。但是没有具体说明过程,这里推导一下。 参考资料: Convex Optimization: Chapter-3 函数的共轭函数定义为 现给出其仿射变化函数,其共轭函数为,...
  • 【优化】共轭函数(Conjugate Function)超简说明

    万次阅读 多人点赞 2017-10-10 16:22:18
    从便于理解的角度介绍共轭函数的概念并推导常用例子。
  • 共轭函数Fenchel不等式

    2018-04-10 09:37:00
    f(x)不一定是凸函数,但他的共轭函数一定是凸函数。是仿射函数的逐点上确界。 Fenchel不等式 f(x)+f*(x)>=xTy 如 转载于:https://www.cnblogs.com/xiaoxuesheng993/p/8776528.html...
  • 浅谈凸优化中的共轭函数

    千次阅读 2016-03-08 22:32:07
    浅谈凸优化中的共轭函数函数ff的共轭定义: f∗(y)=sup(yTx−f(x))f^*(y) = \sup (y^Tx - f(x)), x∈domf{x\in {\bf dom} f} 可见,共轭函数是线性函数yTxy^Tx和原始函数f(x)f(x)的最大gap。 可见如果ff是可微...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,601
精华内容 6,240
关键字:

共轭函数