漫步最优化三十二——最速下降法

爱需要勇气，
但是也许是天意，
让我爱上你，
也许轮回里早已注定，
今生就该还给你。
一颗心在风雨里，
飘来飘去，
一直都在等待你。
——畅宝宝的傻逼哥哥

考虑优化问题

miminize F = f (x) for x \in E n

根据泰勒级数

F + Δ F = f (x + δ) \approx f (x) + g T δ + 12 δ T H δ

当∥δ∥→0，由于δ引起的F变化量为

Δ F \approx g T δ

右边是向量g,δ的点乘，如果

g δ = [g 1 g 2 \dots g n] T = [δ 1 δ 2 \dots δ n] T

那么

Δ F \approx \sum i = 1 n g i δ i = ∥ g ∥ ∥ δ ∥ cos θ

其中θ是向量g,δ之间的夹角且

∥ g ∥ = (g T g) 1 / 2 = (\sum i = 1 n g 2 i) 1 / 2

上升与下降方向

考虑图1的图像，如果x,x+δ是轮廓A上相邻的两个点，那么当∥δ∥→0

Δ F \approx ∥ g ∥ ∥ δ ∥ cos θ = 0

这是因为在该轮廓上F是常数，由此可得向量g,δ之间的夹角θ等于90∘。从效果上看，点x处得梯度与A正交。对于任意向量δ，要想ΔF取得最大正值，那么θ=0，即δ必须与g同向。另一方面，要想ΔF取得最大负值，那么θ=π，即δ必须与−g同向。梯度g与它的负−g分别称为梯度上升与梯度下降方向，这些概念如图1和图2所示。

图1

基本方法

假设函数f(x)在点x的邻域内是连续的，如果d是点x处的最速下降方向，即

d = - g

那么x的变化量δ

δ = α d

会减少f(x)的值，其中α是一个很小的正常数。通过求解一维优化问题

minimize α F = f (x + α d)

我们可以最大化的减少f(x)，如图3所示。

如果点x处的最速下降方向朝向f(x)的最小值x∗，那么存在α值，使得f(x+αd)对α最小化，f(x)对x最小化，因此这时候多维优化问题通过求解一维问题即可。不幸的是，大部分实际问题中，d没有指向x∗，所以为了求出解需要进行多次迭代。首先从初始点x0开始，计算方向d=d0=−g，确定最小化f(x0+αd0)的α值，用α0表示，那么可得到新的点x1=x0+α0d0，最小化的过程可以用前面介绍的任何一种方法，接下来在点

x k + 1 = x k + α k d k

处重复执行上面的过程直到收敛为止，其中k=1,2,…。这个过程的终止条件可以是∥αkdk∥变得足够小或者αk≤Kα0，其中K是一个很小的正常数。对于最速下降法来说，典型的求解轨迹如图4所示。

图2

方向正交

对于最速下降法，解的轨迹服从zig-zag模式，如图4所示。如果每次迭代所选的α都使得f(xk+αdk)最小，那么相邻的方向是正交的。为了证明这个结论，注意到

d f (x k + α d k) d α = \sum i = 1 n \partial f (x k + α d k) \partial x k i d (x k i + α d k i) d α = \sum i = 1 n g i (x k + α d k) d k i = g (x k + α d k) T d k

其中g(xk+αdk)是点xk+αdk处的梯度，如果α∗是最小化f(xk+αdk)的α值，那么

g (x k + α * d k) T d k = 0

或者

d T k + 1 d k = 0

其中

d k + 1 = - g (x k + α * d k)

是点xk+α∗dk处的最速下降方向。从效果上看，相邻方向dk,dk+1如图4那样是正交的。

消除线搜索

如果可以求出f(x)的海森矩阵，那么我们可以用解析法求出最小化f(xk+αd)的α值，用αk表示。如果δk=αdk，那么根据泰勒级数可知

f (x k + δ k) \approx f (x k) + δ T k g k + 12 δ T k H k δ k

如果dk是最速下降方向，例如

δ k = - α g k

那么我们可以得出

f (x k - α g k) \approx f (x k) - α g T k g k + 12 α 2 g T k H k g k

对其求导并等于零得

f (x k - α g k) d α \approx - g T k g k + α g T k H k g k = 0

或者

α = α k \approx g T k g k a l p h a g T k H k g k

图3

图4

接下来，如果我们假设α=αk最小化f(xk+αdk)，那么我们得到

x k + 1 = x k - g T k g k a l p h a g T k H k g k g k

αk的精确性依赖于δk的模长，因为泰勒级数的二次近似只在xk的邻域内有效。刚开始∥δk∥相对比较大，所以αk将不准确，但不管怎样，因为在最速下降方向最小化f(xk+αdk)，所以f(x)一直在减少，故αk的精确性在慢慢提高，甚至每次迭代都能实现最大减少f(x)，因此能实现收敛。对于二次函数来说，上面的近似符号可以改成等号，因此每次迭代α=αk都能最大程度减少f(x)。

如果无法得到海森矩阵，那么我们可以计算点xk,xk−α̂ gk处的f(x)值来确定αk，其中α̂ 是αk的估计值。如果

f k = f (x k) f ̂ = f (x k - α ̂ g k)

那么根据泰勒级数可得

f ̂ \approx - α ̂ g T k g k + 12 α ̂ 2 g T k H k g k

或者

g T k H k g k \approx 2 (f ̂ - f k + α ̂ g T k g k) α ̂ 2

从上式可得

α k \approx g) k T g k α ̂ 2 2 (f ̂ - f k + α ̂ g T k g k)

合适的α̂ 为αk−1，即前一个迭代中的最优α。对于第一次迭代我们用α̂ =1。

收敛

如果函数f(x)∈C2有局部最小点x∗且x=x∗处的海森矩阵是正定的，那么可以说明如果xk足够靠近x∗，我们有

f (x k + 1) - f (x *) \leq (1 - r 1 + r) 2 [f (x k) - f (x *)]

其中

r = H k 的 最 小 特 征 值 H k 的 最 大 特 征 值

更进一步，如果f(x)是二次函数，那么上面的不等式对所有k都成立。从效果上看，如果条件成立，那么最速下降法线性收敛，其收敛率为

β = \leq (1 - r 1 + r) 2

显然，如果Hk的特征值基本都相等，那么收敛率比较高；如果至少有一个比最大值特征值小，那么收敛率就比较低。

H的特征值λi,i=1,2,…,n确定几何平面

x T H x = 常 数

这个等式给出了xTHx的轮廓并且如果H是正定的，那么该轮廓是椭球，其轴长为1/λi‾‾√。如果变量个数为二，那么轮廓是椭圆，轴长分别为1/λ1‾‾‾√,1/λ2‾‾‾√，因此如果在二维问题上使用最速下降法，当轮廓接近圆时收敛最快，如果就是圆即r=1，那么一次迭代就达到收敛。另一方面，如果轮廓近似椭圆或者说函数存在细长的谷底，那么收敛就非常慢，尤其是在靠近解的地方。r对收敛的影响通过比较图4与图5就能明显的看出来。

图5

从效果上看，最速下降法试着让梯度减小到零，因为鞍点处的梯度也是零，所以如果这样的点是解的话可能存在问题。然而这样的解基本是不可能，首先，将鞍点作为下次的迭代点这种概率非常低，其次，鞍点邻域内始终有下降方向。

尺度

对某个特定的优化问题，H的特征值或者说最速下降法的性能很大程度上依赖于所选的变量，例如在一维或二维问题中，轮廓是偏向于圆还是椭圆依赖于单位的选择，因此通过伸缩变量这种变量变换的方式可以提高收敛速率。

一种可能的伸缩方式是令

x = T y

其中T是对角矩阵，然后求解问题

minimize y h (y) = f (x) | x = T y

新问题的梯度与海森矩阵分别为

g h = T g x H h = T T H T

因此最速下降方向以及与问题相关的特征值都发生了变化。但是不幸的是，T的选择严重依赖具体的问题，对此没有一般的法则。不过有个小技巧，那就是尽量平衡二阶导

\partial 2 f \partial x 2 i for i = 1, 2, \dots, n

漫步最优化三十二——最速下降法

基本方法

方向正交

消除线搜索

收敛

尺度

相关推荐