4.4 变尺度法在线视频

前面我们介绍了梯度法也介绍了牛顿法

我们看到了它们各有各的优点和缺点

那么今天我们来讲解变尺度法

也称为DFP法

它既是融合的梯度法和牛顿法的优点

并同时克服了它们两个的缺点

那么DFP法呢是在牛顿法的基础上提出的

具有二次收敛的速度

同时避免了求解海森矩阵和海森矩阵的逆阵

那么它是无约束优化问题的较为有效的方法

并且注意 在工程中得到了广泛的应用

变尺度法呢先有David于1959年提出

后来经过Fletcher和Powell改进而最终确定

因此说呢取他们三位科学家的首字母

就是我们称为是DFP法

我们来看看变尺度法的一个基本思想

那么它呢是构造一个n乘以n阶的矩阵AK

计算中呢以迭代的过程

逐步的逼近海森矩阵的逆阵

并且呢保证计算简单工作量小

那么迭代公式呢我们是这样子的

Xk+1等于Xk减去αk 步长

然后呢AK乘以∇f(Xk)

你看如果是AK是I的话

就是我们单位阵的话

那么变成了什么 梯度法

那如果AK变到了海森矩阵的逆阵的时候

那这是我们的牛顿法

那因此说呢在迭代中呢我们选择A0保证计算简单

工作量小 那我开始就选择A0等于单位阵

然后呢第一步用梯度法

然后呢逐步去逼近牛顿方向

关键的问题就是什么

那就是怎么来构造这个Ak

构造变尺度梯度Ak的基本要求

那么具有下降性收敛性和计算简便性

那么第一我们要保证什么

构造Ak须使Sk为函数值下降的方向

这是一点Xk那么这是函数值上升的方向

这是∇f(X)梯度是函数值上升的方向

负梯度是函数值下降的方向

负的∇f(X) 这是X*

我们构造一个方向呢是这样的一个方向Sk

即Sk的转置乘以负的∇f(X) 大于等于0

将Sk等于负的Ak∇f(X) 代入上式的话

我们就会得到什么呢

∇f(X)转置Ak∇f(Xk)呢是大于零的

那么因此说呢Ak应该是一个实对称的正定矩阵

那么方向负的Ak呢乘以∇f(Xk)呢才是下降的方向

第二个呢我们构造Ak呢必须满足什么

满足Ak随着迭代的过程

到最后呢要逐步的去逼近海森矩阵的逆阵

那么因此说呢我们要保证

Sk等于负的Ak∇f(Xk)呢

逼近牛顿方向

那么这是我们说的DFP的条件

或者我们说的变尺度的条件 这两条

那我们来看一下怎么来构造这个这样的一个Ak

我们目标函数呢f(X)呢是在Xk点处

我们让它进行泰勒展开

我们还是只取前两项

f(X)因为是取前两项

所以是约等于f(Xk)加上∇f(Xk)的转置X减Sk加上二的阶层分之一

然后呢X减Xk然后呢

是相于海森矩阵

左乘一个X减Xk右乘一个X减XK

那么一个是一个转置

一个是原来的

那么这样子的话呢我们可以把它的梯度算一下

∇f(Xk)等于∇fk加上海森矩阵Xk X减去f(Xk)

如果我们用Xk+1呢来代替上式的X那会有什么呢

∇f(Xk+1)呢等于∇f(Xk)加上海森矩阵Xk

Xk+1减Xk

把它整理一下

海森矩阵的逆阵乘以这一项

然后呢等于Xk+1减去Xk

那如果说我令gk+1等于∇f(Xk+1)

gk等于∇f(Xk)那时候呢

那么则有海森矩阵Xk的逆阵

gk+1减去gk等于Xk+1减去Xk

Xk等于海森矩阵逆阵乘以Δgk

那么如果用Ak+1来逼近HXk的逆阵的时候呢

就会有Ak+1Δgk等于ΔXk

那这是我们说的这个变尺度法的条件

也就是说呢可通过当前的信息得到XKΔgk

来构造下一次迭代的Ak+1

那这样的话我们说了Ak也是迭代的话

那我们假设我们下一次的Ak+1等于

上一次的Ak加上一个EK

那么式中呢我们把EK呢称为是校正矩阵

那么如果说呢本次迭代Ak呢已知

如果说求得EK的话

则可以求出Ak+1进行下一次迭代

最开始我们取A0等于I单位阵

目的是从单位阵开始一步一步一步的

最后逼近到海森矩阵的逆阵

那么我们的校正矩阵呢给出来这样一个式子

我们看看EK是怎么推导出来的

那么说呢由变尺度条件Ak+1Δgk等于ΔXk呢

我可以把Ak+1用Ak和EK带进去

Ak+1等于Ak加上Ek

所以说Ak加Ek然后呢Δgk等于ΔXk

那这样的话整理一下

EkΔgk等于ΔXk减去AkΔgk

如果是要满足上面式子

Ek可以取很多

Ek呢等于ΔXk Uk转置AkΔgk Vk转置

式中呢我们看一下

设Uk和Vk呢为待定食量

那么上式呢我们左乘Δgk

变成了EkΔgk

等于ΔXkUk转置Δgk减去AkΔgk Vk转置Δgk

然后呢再变一下形

比较一式和三式

显然有什么呢

Uk转置乘以Δgk等于1Vk转置乘以Δgk是等于1的

那么令Uk等于αkΔXkVk等于βkAkΔgk

那么αkβk呢我们称为是待定系数

计算一下带进去αkΔXk的转置Δgk等于1

那αk就等于什么

一除以ΔXk转置乘以Δgk

那么βk乘以AkΔgk转置Δgk等于1的话呢

βk等于AkΔgk转置Δgk分之一

把αk和βk这样待定系数呢表示出来以后

我们看一下这个式子带到这里边

你就可以求Uk了 Uk求出来了

或者Vk求出来了

你的Ek也可以求出来了

UkVk求出来了Ek也求出来了

实际上你把这个式子和这个式子带到这里边

你再整理一下

你看一下就是我刚才给你那个Ek的那个表示形式

那么Ek给出来以后

那么每一步的你在迭代Sk的过程中

你的Ak也在迭代

迭代到最后呢快逼近你的X*的时候

你的Ak+1就变成了海森矩阵的逆阵

然后呢就可以求出来了

那我们看看DFP方法的步骤和迭代框图是什么样子

第一个呢同样你输入你的初始点

X0你的N然后呢ε

n是我们的维数

第二步呢k等于0

从第0步开始 在第0步最开始的时候

Ak我们说到取最简单的单位阵

然后呢gk我们说的是∇f(X0)

那么Sk呢等于负的Akgk我们进行一维搜索αk

那么Sk+1等于Sk加上αkSk

αk是步长

Sk是方向

那么gk+1呢等于∇f(Xk+1)

如果是 是小于ε的话

那我就可以输出了

那我X*就等于Xk+1F*求出来就可以了

我们就END就结束了

如果不是 k等于n

如果是的话呢怎么办

我们让X0等于Xk+1

然后重新去做迭代

如果不是的话

那我就计算ΔXkΔgk Ek然后呢

Ak+1等于Ak加上EK

算完这个以后呢Ak+1等于新的

然后带进去

就可以进行下一次迭代

那么这是DFP方法的一个迭代步骤

那DFP方法特点呢

第一DFP方法呢具有牛顿法的二次收敛速度

因为呢Ak呢最终会逼近海森矩阵的逆阵

第二对任意给定的初始点X0

X都具有最速下降方向-∇f(X0)

因为呢A0等于I S0等于-∇f(X0)

每次迭代的方向都是共轭的

第四计算公式具有递推性 便于迭代

只需要给出X0和A0即可往下进行计算

第五 计算方便

无需计算二阶导数矩阵及其逆阵

因此说呢DFP方法呢在实践中呢得到了广泛的应用

是无约束方法中常用的方法

与我们变尺度方法里边呢DFP方法相等同的

我们还有一个BFGS方法

我们来看一看

实际上BFGS方法是Broydon等人在DFP方法上呢

基础上提出的

BFGS方法呢避免了DFP方法

由于舍入误差和一维搜索不准确不精确

导致的某个变尺度矩阵变成奇异阵的问题

那BFGS方法呢具有更好的数值稳定性

其迭代步骤呢与DFP方法是相同的

那么不同的仅仅是什么

就是我们这一轮的校正矩阵是不同的

BFGS方法的校正矩阵呢EK等于这么大一堆

它很好地避免什么

在刚才那个DFP方法里头的校正矩阵里

分母上有Ak Ak是个单位阵

然后你再分之一以后呢会有精度舍入误差的问题

BFGS方法呢把这个Ak给通过变形

通过这个巧妙设计呢Ak在分子上

这样话就不会存在那样的一个问题

那么还是Ak+1等于Ak加上Ek

这是我们的变尺度方法

那好我们最后呢把这一章的

无约束优化方法所讲几个方法呢再总结一下

看看它的特点和它的使用范围

第一个呢我们来看一看Powell法

Powell法呢它的特点呢不需要求导

只需要计算函数值

适用于中小型问题的无约束优化问题

是一种较为有效的方法

但是呢随着维数增多

收敛速度变慢

第二梯度法

我们称为是最速下降法

因为什么

因为负梯度是我们的函数的最速下降方向

迭代计算简单 存储量小

对初始点的选择要求低

注意最初几步迭代函数值下降较快

但是愈逼近极值点下降愈慢

因此说呢经常不单独使用

常与其他方法呢混合使用

共轭梯度法 我们也说了

是对最速下降法在收敛速度上的一个重大改进

具有二阶收敛速度

而计算呢又比牛顿法大为简化 存储量小

常用于多维的最优化方法

牛顿法 收敛速度快

但对初始点要求较高

且要求计算二阶导数的矩阵以及逆阵

计算量和存储量 都以为数n的平方比例增加

故在工数量中呢很少直接使用

牛顿法和这个梯度法

我们说了它两个混合起来

就是我们最后的DFP变尺度方法

可用到求解维数n大于一百的优化问题

n大于一百的优化问题都可以用变尺度法来求解

对于高维大型问题

由于收敛速度快效果好

被认为是无约束优化最有效的方法之一

但需要较大的存储量

DFP在数值稳定性不够理想情况下

可用BFGS的方法来进行替换

就是你要计算发现它的数值稳定性不太好的话

因为什么你要求Ak分之一的话

你可以尝试用BFGS来替换它

来提高它的数值稳定性

减少它的舍入误差

这是DFP法

我们说在实际的问题中

如果你们做了一个工程问题

发现这个问题没有约束

那就是无约束的多维优化问题的话

那么你可以想一想杨老师讲的这几个方法

可以在选取合适的方法来进行求解你的问题

那么这也是我们讲的这个第四章

对于多维的无约束优化问题的求解方法