漫步最优化四十一——Powell法(下)

四季交替，
光阴推动了变更，
但你一直印在我心。
遇见你的那天，
心似击鼓般兴奋，
呼吸似乎都有了震音。
想你想的入神，
想你充满能量，
想你醒了也像晕了，
想你不由自主的笑了。
——畅宝宝的傻逼哥哥

对于步骤1，d01,d02,…,d0n为坐标方向。对于步骤2，f(x)沿着xk0,xk1,…,xkn最小化。对于步骤3，f(x)在新的共轭方向最小化，对于凸二维问题来说，该算法搜索模式如图4所示。

Powell算法的主要优点是不需要海森矩阵，更进一步，通过使用基于线搜索的一维算法，梯度也不需要。

但是Powell算法有时候不一定线性无关，这样的话生成的方向集无法生成En，即便是凸二次问题也存在这样的情况，如果第二步中最小化f(xk(j−1)+αdkj)时存在某个j使得αkj=0，就会导致这样的情况。这时候步骤三将得到

d k (n + 1) = \sum i = 1 i \neq j n α k i d k i

即新生成的方向不包含dkj，因为dkj别舍弃掉了，这样的n个方向集合无法张成En，这就意味着至少有两个方向是线性相关的，这样的话算法无法收敛到问题的解。

上面的问题可以被避免到，那就是如果出现线性相关，那么下次迭代的话我们不改变方向集，然后得到新的共轭方向。因为下次迭代的时候我们是从新的点xk开始的，所以是可能产生新的方向的。

图4

原则上如果至少有一个αki为零，那么将产生线性相关。不幸的是，由于计算机精度有限，αki的值不可能为零，所以检查αki不是可靠的方法，接下里介绍一种可替代的方法，依然是Powell得出来的。

如果方向向量dki,i=1,2,…,n被归一化使得

d T k i H d k i for i = 1, 2, \dots, n

那么矩阵的行列式

D = [d k 1 d k 2 \dots d k n]

要想为最大值，那么当且仅当方向dki属于共轭集合，所以如果舍弃非共轭方向d1k然后将共轭方向dk(n+1)加入到D中，那么D的行列式将会增加。另一方面，如果dk(n+1)的加入使得D内产生线性相关，那么D的行列式将减小。基于这个原则，Powell开发了修正的算法，该算法中使用一个测试来确定新生成的方向是否用于下次迭代，该测试也能识别是否n个老方向中的一个用新方向来替代，所以减小了线性相关的风险。

有个非常相似的技术也是用来消除线性相关，该方法由Zangwill提出。从计算上看，该方法比Powell修正更加经济有效，因此很值得详细的介绍一下。

Zangwill的方法是在Powell算法上进行了如下修正。

步骤1中的初始方向选为单位坐标向量集
$D 0 = [d 01 d 02 \dots d 0 n] = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ 10 ⋮ 0 01 ⋮ 0 \dots \dots \dots 00 ⋮ 1 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥$
D0的行列式Δ0为单位1。
步骤2中确定αki,i=1,2,…,n的方法跟以前一样，然后选出最大的αki即
$α k m = max {α k 1, α k 2, \dots, α k n}$
步骤3中跟以前一样生成新的方向，然后归一化，
$d k (n + 1) = 1 λ k (x k n - x k 0)$

其中

λ k = ∥ x k n - x k 0 ∥

步骤4不变，步骤5中，用上面得到的新方向代替方向dkm，当然前提是这个替换能够保证
$D k = [d k 1 d k 2 \dots k n]$

的行列式有限且比常数ε1大，其中0<ε1≤1，即

0 < ε 1 < Δ k = det D k \leq 1

否则的话，我们用最近的方向集用于下次迭代。因为

Δ k = det [d k 1 \dots d k (m - 1) d k m d k (m + 1) \dots d k n]

且

d k (n + 1) = 1 λ k \sum i = 1 n α k i d k i

代替了dkm，所以

Δ' k = α k m α k Δ k

注意这里补充两个知识点

如果常数乘以一列并加到另一列，那么行列式不变。
如果某列乘以常数，那么行列式同样乘以该常数。
根据第一个知识点可知Δ′k相加的效果可以消除掉，根据第二个知识点可知需要乘以αkm/λk。如果
$α k m λ k Δ k > ε 1$

那么我们令

d (k + 1) m = d k (n + 1) d (k + 1) i = d k i

其中i=1,2,…,m−1,m+1,…,n。否则的话

d (k + 1) i = d k i

其中i=1,2,…,n。同时也要更新Δk

δ k + 1 = {α k m λ k Δ k Δ k if α k m λ k Δ k > ε 1 otherwise

上面修正得到的结果就是方向矩阵的行列式一直有限且为正，这就表明方向一直是线性无关的。第二项的策略能够确保行列式的值Δk尽可能大，从而避免线性相关。

修正的算法称为Zangwill算法，对于凸二次问题来说，该算法能够收敛。

漫步最优化四十一——Powell法(下)

相关推荐