一、基础知识(3)-共轭函数、次梯度

一、共轭函数

1.1 共轭函数的定义和例子

1. 共轭函数： f ∗ ( y ) = s u p x ∈ d o m f { y T x − f ( x ) } f^*(y)=\underset{x\in dom f}{sup}\{y^Tx-f(x)\} f∗(y)=x∈domfsup​{yTx−f(x)}
   • 几何意义：$xy$与$f(x)$之间差值的最大值。
     
2. Fenchel 不等式：$f(x)+f^{\ast }(y)⩾x^{T}y$

1.2 二次共轭函数

1. 二次共轭函数： f ∗ ∗ ( y ) = s u p x ∈ d o m f ∗ { x T y − f ∗ ( x ) } f^{**}(y)=\underset{x\in dom f*}{sup}\{x^Ty-f^*(x)\} f∗∗(y)=x∈domf∗sup​{xTy−f∗(x)}

二、次梯度

2.1 次梯度的定义

1. 次梯度：设$f$为适当凸函数，$x$为定义域$domf$中的一个点，若向量$g\in {\mathbb{R}}^n$满足，$f(y)⩾f(x)+g^T(y-x),\forall y\in domf$,则称$g$为函数$f$在点$x$处的一个次梯度。
2. 次微分： ∂ f ( x ) = { g ∣ g ∈ R n , f ( y ) ⩾ f ( x ) + g T ( y − x ) , ∀ y ∈ d o m f } \partial f(x)=\{g|g\in \R^n,f(y)\geqslant f(x) + g^T(y-x),\forall y \in domf\} ∂f(x)={g∣g∈Rn,f(y)⩾f(x)+gT(y−x),∀y∈domf}
3. 形式化理解：对于$f(x)=|x|$，在$x=0$的点，无导数，所以可以用次梯度。
   
4. 次微分：$\partial f(x)$为在$[a,b]$区间内的次梯度

2.2 次梯度的性质

1. 次梯度的单调性：$f:{\mathbb{R}}^n\to \mathbb{R}$为凸函数，$x,y\in domf$，则$\mu \in \partial f(x),v\in \partial f(y)$
2. 待补…

2.3 凸函数的方向导数

1. $f$为适当函数，给定点$x_0$以及方向$d\in {\mathbb{R}}^n$，方向导数定义为：$\underset{t\downarrow 0}{lim\varphi (t)}=\underset{t\downarrow 0}{\lim }\frac{f(x_0+td)-f(x_0)}{t}$
2. 方向导数定义：$\partial f(x_0;d)=\underset{t>0}{\inf }\frac{f(x_0+td)-f(x_0)}{t}$

2.4 次梯度的计算规则

1. 基本规则

1. 可微凸函数：$f$为凸函数，若$f$在点$x$处可微，则 ∂ f ( x ) = { ∇ f ( x ) } \partial f(x)=\{\nabla f(x)\} ∂f(x)={∇f(x)}
2. 凸函数的非负线性组合：$f_1,f_2$为凸函数，且满足$intdom{f}_1\cap dom{f}_2\ne \varnothing ,x\in dom{f}_1\cap dom{f}_2$，若$f(x)=a_1{f}_1(x)+a_2{f}_2(x),a_1,a_2⩾0$，则次微分为$\partial f(x)=a_1\partial f_1(x)+a_2\partial f_2(x)$
3. 线性变量替换：$h$为适当凸函数，且函数$f$满足$f(x)=h(Ax+b),\forall x\in {\mathbb{R}}^m$,其中$A\in {\mathbb{R}}^{n\times m},b\in R^n$。若存在$x^{\#}\in {\mathbb{R}}^m$，使得$A{x}^{\#}+b\in intdomh$，则$\partial f(x)=A^T\partial h(Ax+b),\forall x\in intdomf$
   待补…