实变函数无约束优化的梯度分析

Love The Way You Lie 2022-01-06 09:41 144阅读 0赞

### 高三打基础，高四985 ###

*   *   *   *  典型的优化问题
             *  松弛
             *  Taylor级数
             *   *  邻域
                 *  认识Taylor级数
                 *  多元函数Taylor级数和极值求解
             *  总结
             *  补充

#### 典型的优化问题 ####

m i n x ∈ D f ( x ) \\underset\{\\bm x\\in \\mathcal D\}\{min\}f(\\bm x) x∈Dminf(x)  
其中， D = d o m f ( x ) \\mathcal\{D\}=dom f(\\bm x) D=domf(x)表示函数 f ( x ) f(\\bm x) f(x)的定义域；变元向量 x ∈ R n \\bm x \\in\\mathbb\{R\}^n x∈Rn称为最优化问题的优化向量，代表需要作出的一种选择，在机器学习中，我们更关注所求参数的值，即极值点是多少，而不关注极值是多少。

#### 松弛 ####

称序列 \{ a k \} k = 0 ∞ \\left\\\{a\_k\\right\\\}^\\infty\_\{k=0\} \{ ak\}k=0∞为松弛序列（relaxation sequence），若 a k + 1 ≤ a k , ∀ k ≥ 0 a\_\{k+1\}\\le a\_\{k\},\\forall k\\ge0 ak\+1≤ak,∀k≥0。在迭代求解最优化问题的过程中，需要产生一个松弛序列 f ( x k + 1 ) ≤ f ( x k ) , k = 0 , 1 , ⋯ f(\\bm x\_\{k+1\}) \\le f(\\bm x\_\{k\}),\\quad k=0,1,\\cdots f(xk\+1)≤f(xk),k=0,1,⋯

#### Taylor级数 ####

##### 邻域 #####

在谈论Taylor级数之前，先认识邻域，简单来说，就是在某一点附近的一个区域，这个区域的大小通常用欧几里得范数（Euclidean norm）表示，不管你是多少维的向量，都可以，如 ∥ x − x ˉ ∥ 2 ≤ r \\|\\bm x-\\bar\{\\bm x\}\\|\_2\\le r ∥x−xˉ∥2≤r表示点 x ˉ \\bar\{\\bm x\} xˉ的一个半径为 r r r的邻域，邻域通常是在很微小的尺度上衡量一件事情。

##### 认识Taylor级数 #####

泰勒级数可以用无穷多个**多项式**近似逼近一个复杂函数，但是通常这是不现实的，一般是研究哪一段就在哪一段附近做泰勒展开，***低阶项可以近似代表展开点附近原函数的值，高阶项是逼近远处原函数值的必要项，当展开点c的邻域足够小时，在邻域内可以利用一阶项，最多二阶项逼近邻域内点***

一元函数的Taylor级数

如果函数  f ( x ) f(x) f(x)在  c c c点有连续的  n n n阶导数，则其在  c c c点的Taylor展开为  
 f ( c + Δ x ) = f ( c ) + f ′ ( c ) Δ x + 1 2 f ′ ′ ( c ) ( Δ x ) 2 + ⋯ + 1 n ! f ( n ) ( c ) ( Δ x ) n + o ( ( Δ x ) n ) f(c+\\Delta x)=f(c)+f&\#x27;(c)\\Delta x+\\frac\{1\}\{2\}f&\#x27;&\#x27;(c)(\\Delta x)^2+\\cdots+\\frac\{1\}\{n!\}f^\{(n)\}(c)(\\Delta x)^n+o((\\Delta x)^n) f(c\+Δx)=f(c)\+f′(c)Δx\+21f′′(c)(Δx)2\+⋯\+n!1f(n)(c)(Δx)n\+o((Δx)n)这是考研的内容，现在想起来还很亲切。

##### 多元函数Taylor级数和极值求解 #####

考过研的同志们应该清楚地记着，考研大纲多元函数无约束极值问题一般就要求到二元函数 f ( x , y ) f(x,y) f(x,y)，套路是这样的，先求一阶偏导数，令 f x ′ = 0 , f y ′ = 0 f&\#x27;\_x=0,f&\#x27;\_y=0 fx′=0,fy′=0，这样就得到若干驻点，再求二阶偏导数，满足 f x x ′ ′ f y y ′ − ( f x y ′ ′ ) 2 > 0 f&\#x27;&\#x27;\_\{xx\}f&\#x27;\_\{yy\}-\\left(f&\#x27;&\#x27;\_\{xy\}\\right)^2>0 fxx′′fyy′−(fxy′′)2>0，则是极值点；若 f x x ′ ′ f y y ′ − ( f x y ′ ′ ) 2 < 0 f&\#x27;&\#x27;\_\{xx\}f&\#x27;\_\{yy\}-\\left(f&\#x27;&\#x27;\_\{xy\}\\right)^2<0 fxx′′fyy′−(fxy′′)2<0，则不是极值点；若等于零，则需从极值的定义判断。  
这种做法抽象程度太低，即概括性不强，同时解释性也不好，下面，我们将通过多变量函数的泰勒展开，利用梯度向量和Hessian矩阵进行判定，解释性往往也更强，同时这里面也将用到二次型的相关知识。  
多变量实值函数 f ( x ) f(\\bm x) f(x)，其中 x = \[ x 1 , ⋯ &ThinSpace; , x n \] T \\bm x=\[x\_1,\\cdots,x\_n\]^T x=\[x1,⋯,xn\]T，令 Δ x = x − c \\Delta\\bm x=\\bm x-\\bm c Δx=x−c，在半径 r r r足够小的邻域内，函数 f ( x ) f(\\bm x) f(x)在点 c \\bm c c的二阶Taylor级数逼近为 f ( c + Δ x ) ≈ f ( c ) + ( ∂ f ( c ) ∂ c ) T Δ x + 1 2 ( Δ x ) T ∂ 2 f ( c ) ∂ c ∂ c T Δ x = f ( c ) + ( ∇ f ( c ) ) T Δ x + 1 2 ( Δ x ) T H ( f ( x ) ) Δ x f(\\bm c+\\Delta\\bm x)\\approx f(\\bm c)+\\left(\\frac\{\\partial f(\\bm c)\}\{\\partial \\bm c\}\\right)^T\\Delta\\bm x+\\frac\{1\}\{2\}(\\Delta\\bm x)^T\\frac\{\\partial^2 f(\\bm c)\}\{\\partial \\bm c\\partial\\bm c^T\}\\Delta\\bm x\\\\ =f(\\bm c)+\\left(\\nabla f(\\bm c)\\right)^T\\Delta\\bm x+\\frac\{1\}\{2\}(\\Delta\\bm x)^T\\bm H(f(\\bm x))\\Delta\\bm x f(c\+Δx)≈f(c)\+(∂c∂f(c))TΔx\+21(Δx)T∂c∂cT∂2f(c)Δx=f(c)\+(∇f(c))TΔx\+21(Δx)TH(f(x))Δx

式中  
 ∇ f ( c ) = ∂ f ( c ) ∂ c = ∂ f ( x ) ∂ x ∣ x = c H ( f ( c ) ) = ∂ 2 f ( c ) ∂ c ∂ c T = ∂ 2 f ( x ) ∂ x ∂ x T ∣ x = c \\nabla f(\\bm c)=\\frac\{\\partial f(\\bm c)\}\{\\partial\\bm c\}=\\frac\{\\partial f(\\bm x)\}\{\\partial\\bm x\}\\bigg|\_\{\\bm x=\\bm c\}\\\\ \\bm H(f(\\bm c))=\\frac\{\\partial^2 f(\\bm c)\}\{\\partial \\bm c\\partial\\bm c^T\}=\\frac\{\\partial^2 f(\\bm x)\}\{\\partial \\bm x\\partial\\bm x^T\}\\bigg|\_\{\\bm x=\\bm c\} ∇f(c)=∂c∂f(c)=∂x∂f(x)∣∣∣∣x=cH(f(c))=∂c∂cT∂2f(c)=∂x∂xT∂2f(x)∣∣∣∣x=c  
分别是函数 f ( x ) f(\\bm x) f(x)在点 c \\bm c c的**梯度向量**和**Hessian**矩阵。  
在更小邻域内，满足二阶项可以忽略的情况下，函数的一阶Taylor级数逼近为  
 f ( c + Δ x ) ≈ f ( c ) + ( ∇ f ( c ) ) T Δ x f(\\bm c+\\Delta\\bm x)\\approx f(\\bm c)+\\left(\\nabla f(\\bm c)\\right)^T\\Delta\\bm x f(c\+Δx)≈f(c)\+(∇f(c))TΔx

显然，为了保证 f ( c ) ≤ f ( c + Δ x ) f(\\bm c)\\le f(\\bm\{c\}+\\Delta\\bm x) f(c)≤f(c\+Δx)对邻域内的所有点都成立，梯度向量在点 c \\bm c c需满足：  
 ∇ f ( c ) = ∂ f ( x ) ∂ x ∣ x = c = 0 \\nabla f(\\bm c)=\\frac\{\\partial f(\\bm x)\}\{\\partial \\bm x\}\\bigg|\_\{\\bm x=\\bm c\}=0 ∇f(c)=∂x∂f(x)∣∣∣∣x=c=0

在梯度向量 ∇ f ( c ) = 0 \\nabla f(\\bm c)=0 ∇f(c)=0的情况下，对于二阶项不能忽略的邻域，**此时**函数 f ( x ) f(\\bm x) f(x)的二阶Taylor级数逼近：  
 f ( c + Δ x ) ≈ f ( c ) + 1 2 ( Δ x ) T H ( f ( x ) ) Δ x f(\\bm c+\\Delta\\bm x)\\approx f(\\bm c)+\\frac\{1\}\{2\}(\\Delta\\bm x)^T\\bm H(f(\\bm x))\\Delta\\bm x f(c\+Δx)≈f(c)\+21(Δx)TH(f(x))Δx

于是我们容易得到以下结论：

（1）若二次型  ( Δ x ) T H ( f ( x ) ) Δ x ≥ 0 (\\Delta\\bm x)^T\\bm H(f(\\bm x))\\Delta\\bm x\\ge0 (Δx)TH(f(x))Δx≥0对邻域内所有的  Δ x \\Delta \\bm x Δx恒成立，或Hessian 矩阵半正定  
 H ( f ( c ) ) = ∂ 2 f ( x ) ∂ x ∂ x T ∣ x = c ⪰ 0 \\bm H(f(\\bm c))=\\frac\{\\partial^2 f(\\bm x)\}\{\\partial \\bm x\\partial\\bm x^T\}\\bigg|\_\{\\bm x=\\bm c\}\\succeq 0 H(f(c))=∂x∂xT∂2f(x)∣∣∣∣x=c⪰0  
则  f ( c ) ≤ f ( c + Δ x ) f(\\bm c)\\le f(\\bm\{c\}+\\Delta\\bm x) f(c)≤f(c\+Δx)在我们规定的邻域内恒成立，即点  c \\bm c c是函数  f ( x ) f(\\bm x) f(x)的一个局部极小点。

（2）若二次型  ( Δ x ) T H ( f ( x ) ) Δ x ≤ 0 (\\Delta\\bm x)^T\\bm H(f(\\bm x))\\Delta\\bm x\\le0 (Δx)TH(f(x))Δx≤0对邻域内所有的  Δ x \\Delta \\bm x Δx恒成立，或Hessian 矩阵半负定  
 H ( f ( c ) ) = ∂ 2 f ( x ) ∂ x ∂ x T ∣ x = c ⪯ 0 \\bm H(f(\\bm c))=\\frac\{\\partial^2 f(\\bm x)\}\{\\partial \\bm x\\partial\\bm x^T\}\\bigg|\_\{\\bm x=\\bm c\}\\preceq 0 H(f(c))=∂x∂xT∂2f(x)∣∣∣∣x=c⪯0  
则  f ( c ) ≥ f ( c + Δ x ) f(\\bm c)\\ge f(\\bm\{c\}+\\Delta\\bm x) f(c)≥f(c\+Δx)在我们规定的邻域内恒成立，即点  c \\bm c c是函数  f ( x ) f(\\bm x) f(x)的一个局部极大点。

（3）若二次型在邻域内的某些点大于等于零，另一些点小于零，或Hessian matrix 不定，则点  c \\bm c c是函数  f ( x ) f(\\bm x) f(x)的一个 **鞍点**。

（4）若上面(1)(2)里面的“=”去掉，则点  c \\bm c c是函数  f ( x ) f(\\bm x) f(x)的一个 **严格**局部极小（大）点。

#### 总结 ####

在无约束优化的极值问题中

1.  **严格**局部极**小**点的二阶**充分**条件是： ∇ f ( c ) = ∂ f ( x ) ∂ x ∣ x = c = 0 和 H ( f ( c ) ) = ∇ c 2 f ( c ) = ∂ 2 f ( x ) ∂ x ∂ x T ∣ x = c ≻ 0 \\nabla f(\\bm c)=\\frac\{\\partial f(\\bm x)\}\{\\partial \\bm x\}\\bigg|\_\{\\bm x=\\bm c\}=0\\quad和\\quad\\bm H(f(\\bm c))=\\nabla^2\_\{\\bm c\}f(\\bm c)=\\frac\{\\partial^2 f(\\bm x)\}\{\\partial \\bm x\\partial\\bm x^T\}\\bigg|\_\{\\bm x=\\bm c\}\\succ 0 ∇f(c)=∂x∂f(x)∣∣∣∣x=c=0和H(f(c))=∇c2f(c)=∂x∂xT∂2f(x)∣∣∣∣x=c≻0
2.  **严格**局部极**大**点的二阶**充分**条件是： ∇ f ( c ) = ∂ f ( x ) ∂ x ∣ x = c = 0 和 H ( f ( c ) ) = ∇ c 2 f ( c ) = ∂ 2 f ( x ) ∂ x ∂ x T ∣ x = c ≺ 0 \\nabla f(\\bm c)=\\frac\{\\partial f(\\bm x)\}\{\\partial \\bm x\}\\bigg|\_\{\\bm x=\\bm c\}=0\\quad和\\quad\\bm H(f(\\bm c))=\\nabla^2\_\{\\bm c\}f(\\bm c)=\\frac\{\\partial^2 f(\\bm x)\}\{\\partial \\bm x\\partial\\bm x^T\}\\bigg|\_\{\\bm x=\\bm c\}\\prec 0 ∇f(c)=∂x∂f(x)∣∣∣∣x=c=0和H(f(c))=∇c2f(c)=∂x∂xT∂2f(x)∣∣∣∣x=c≺0
3.  Hessian矩阵不定，则不能保证该点是一个极值点，它可能只是一个鞍点。

#### 补充 ####

1.  多变量实值函数的Taylor展开可能有点抽象，我们逐项理解：(1) 常数项很好理解，这是展开点函数值；(2) 一阶项：二元函数 f ( x , y ) f(x,y) f(x,y)全微分的定义： d f ( x , y ) = f x ′ d x + f y ′ d y = ( f x ′ , f y ′ ) ⋅ ( d x , d y ) df(x,y)=f&\#x27;\_xdx+f&\#x27;\_ydy=(f&\#x27;\_x,f&\#x27;\_y) \\cdot(dx,dy) df(x,y)=fx′dx\+fy′dy=(fx′,fy′)⋅(dx,dy),因此推广到更多元也不难理解；(3) 二阶项：对于多元函数 f ( x ) f(\\bm x) f(x)求两次偏微分后和对其Taylor级数求两次偏微分后的结果一致，即 ∇ c 2 f ( c ) = ∂ 2 f ( x ) ∂ x ∂ x T ∣ x = c = H ( f ( c ) ) \\nabla^2\_\{\\bm c\}f(\\bm c)=\\frac\{\\partial^2 f(\\bm x)\}\{\\partial \\bm x\\partial\\bm x^T\}\\bigg|\_\{\\bm x=\\bm c\}=\\bm H(f(\\bm c)) ∇c2f(c)=∂x∂xT∂2f(x)∣∣∣∣x=c=H(f(c))这符合Taylor公式的定义原则。
2.  Hessian矩阵是对称矩阵，判定Hessian是正定矩阵的方法：① 正定二次型的定义： ∀ x ≠ 0 , x T A x > 0 \\forall \\bm x \\neq\\bm0,\\bm x^TA\\bm x>0 ∀x̸=0,xTAx>0，则 A A A为正定矩阵；② 该对称矩阵的所有顺序主子式都大于零；③ 该对称矩阵的所有特征值都大于零；④ 该矩阵合同于同型单位矩阵。

> 以上内容均参考张贤达著《矩阵分析与应用》，更多高阶理论，请参考该书第四章。