7.7 多维无约束优化-改进鲍威尔方法在线视频

各位同学大家好

那么在上一讲的内容当中

我们给大家提到了

鲍威尔方法

那么鲍威尔方法的出现呢

它提高了坐标轮换法的收敛速度

它在坐标轮换法的基础上

通过去构造共轭方向

使得收敛速度得到了快速的提高

在上一讲当中 我们也提到

鲍威尔方法它对于

搜索方向是具有要求的

它要求我们的方向是线性无关的

一旦出现了线性相关的现象之后

那么它会出现

退化的问题

那么导致呢

优化问题的求解不能得到它的极值点

那么针对这样的一个问题

我们来看一下有没有改进的办法

我们回顾一下鲍威尔方法的

求解过程

在第一轮当中它的第一个搜索方向

和坐标轮换法是相同的

也就是以二维的优化问题为例

第一轮的第一个搜索方向是坐标轴x1

第一轮的第二个搜索方向是坐标轴x2

那么第一轮的第三个搜索方向

是构造的s1方向

那么在第二轮当中

它是替换掉了第一轮当中的

第一个方向x1

通过s1方向

然后再构造s2方向

完成第二轮的迭代

那么在这里面呢

有一个问题大家可以考虑一下

它为什么要替换掉第一个方向呢

那么这第一个方向

一定是个不好的方向吗

那么带着这样一个问题

我们来看一下

那么针对鲍威尔方法存在

退化的这样一个可能性的问题

那么人们提出了改进的鲍威尔方法

那么改进的鲍威尔方法

它是如何来进行搜索的呢

我们来看一下

改进的鲍威尔方法放弃了原算法当中

不加分析的用新生成的方向

去替换上一轮搜索方向组当中的

第一个方向的做法

那么它是如何来解决的呢

我们来看一下

在这个方法当中

它是这样来进行规定的

在每一轮迭代完成的时候

我们会产生一个新的共轭方向sk

那么这个方向产生之后

在组成新的方向组的时候

它不一律舍去上一轮的第一个方向

而是先对共轭方向的好坏来进行判断

也就是像我们前面提到的

基本鲍威尔方法当中

以第一轮为例 我们来做一个解释

基本的鲍威尔方法当中

第一轮第一次搜索方向x1

第二次搜索方向x2

然后生成了一个方向s1

那么这个s1方向究竟是一个好的方向

还是一个不好的方向呢

那么这个地方

在基本的鲍威尔方法当中

没有做判断

在改进的鲍威尔方法

或者有的教材上

称之为修正的鲍威尔方法当中

我们对这样一个方向来进行判断

我们判断一下新生成的s1这个方向

是好的还是坏的

如果这个方向很好

那我们接下来在下一轮当中

我们就使用

如果这个方向不好

那么下一轮当中我们不用它

那么这样的一种

方法就可以有效的避免在

鲍威尔方法当中

有可能会出现线行相关

造成

优化求解不能进行的这样的一个问题

在修正的鲍威尔方法当中

那么如果这个方向是好的

它接下来进行替换的时候

是替换上一轮当中的哪个方向呢

我们要去做判断

这个判断我们如何来进行呢

大家可以看到

我们在这里给了一个方程组

在这个方程组当中

我们来进行这样一个方向的判断

在第k轮的这样一个搜索当中

如果我们可以看到

它满足这样的一个不等式组

那么就表明这个方向

与原来的方向是线性无关的

因此呢

我们就可以将这个方向

作为下一轮的迭代方向

那确定了这样一个方向

是好的方向之后

那接下来我们来判断一下

它究竟是要去替换哪一个方向呢

那么这里面我们来看

我们在进行替换方向判断的时候

那么大家看一下

我们首先先要做这样几个计算

那么在完成这样的几个计算之后

然后我们把下降量

最大的这个方向给它找出来

然后呢 进行方向的替换

那么下降量最大的这样一个方向

我们找出来了之后

我们进行了替换 那么就保证了

非线性函数求优的

这样一个可靠度的这样一个问题

所以对修正的鲍威尔方法来说

它的迭代计算的步骤是这样的

首先我们给定初始点x0

和收敛精度ε

然后取n个坐标轴的单位向量e

来作为初始的搜索方向

那么我们从第一轮开始

所以让k等于1

那么从x10出发

我们依次沿着

我们所确定的这样一个方向

进行n次的一维搜索

那么我们得到n个一维的极小点

然后我们去构造新的共轭方向

那么沿共轭方向我们去计算映射点

那么计算出来映射点之后

我们去计算第k轮当中

相邻极小点目标函数的差值

我们找出其中的最大差值

及其相应的这样一个方向

那么找到了这样一个方向之后

我们来看一下

那么这个方向是否需要替换呢

我们需要进行判断

那么具体的这样一个判断

大家可以看到

我们是根据这样的两个式子

来进行判断

如果它同时满足下面的这样两个式子

那么这个方向就是一个好的方向

那么如果上述的条件是不满足的

那么则进入到第k+1轮迭代的时候

我们仍然采用第k轮迭代的方向

所以从这里面大家可以看到

修正的鲍威尔方法

那么它从最大程度上

去改变了我们在基本鲍威尔方法当中

有可能出现线性相关的这样一个问题

那么它的解决的办法就是

我要根据这样的

条件来进行判断

这个方向是不是一个好的

那另外一个

我们还要根据相应的式子来去计算

我要去替换上轮当中的哪个方向

所以经过这样的一些分析之后呢

我们可以看到

修正的鲍威尔方法就改变了

我们基本鲍威尔方法当中所存在的

这样的一些问题

那么所有的迭代都进行完成之后

那接下来我们就可以进行收敛的判断

那么收敛的判断我们依然可以选择

我们在前面提到的几种

收敛的判断准则

根据收敛的判断结果

我们来决定是否进行下一轮的迭代

那接下来呢

我们为了更好的给大家去解释

修正的鲍威尔方法

我们接下来呢来看一个例题

那么这例题呢 大家可以看到

是利用鲍威尔方法

来求目标函数的最优解

它的初始点现在已经告诉我们

迭代的精度ε是等于0.001

那么首先我们来看一下

它要进行第一轮的迭代

那么第一轮迭代的时候

我们可以看到首先

我们先沿着第一个坐标轴的方向

e1进行一次一维的搜索

那么沿着e1进行一次一维搜索的时候

我们可以看到

我们可以得到了

这个第一轮的第一个点

那么在这里面大家可以看到

我们给出了一个相对比较详细的

最优步长的确定的具体的例子

所以如果在前边

对于最优步长的确定

大家没有掌握很好的同学

可以结合着这个例题 我们来看一下

所以我们把x 11

代入到目标函数的表达式当中

我们去求它的极值

那么就可以得到α1

α1得到了之后

我们可以看到

我就可以

再次代入到x11的表达式当中

把x11点

坐标值得到

把x11点的目标函数值可以计算出来

然后我们从这点开始

沿着第二个坐标轴的方向

进行一次一维的搜索

那么这两次搜索都完成之后

那么接下来按照基本鲍威尔方法的

求解思路

我们接下来要去构造新的方向

所以大家可以看到

第一轮的迭代对于基本鲍威尔方法

和修正的鲍威尔方法

两者是一样的

那么构成了新的方向之后

那接下来我们来看一下

我沿着s1方向

进行一次一维的搜索 得到了它的

极小点

那么接下来呢

我们要进行这样一个迭代

终止条件的判断

那么判断我们根据第一轮的起点

和第一轮的终点两点之间的

距离来进行判断

那么从这个地方

大家可以看到两点之间的距离

它是大于ε

那么大于ε

那就意味着我需要进行第二轮的迭代

那么但是在这个地方

大家需要注意的是

按照基本的鲍威尔方法

如果是进行到这一步的时候

那我直接进行第二轮的迭代就可以了

第二轮当中第一个迭代的方向就是

e2这样一个方向

但是呢对修正的鲍威尔方法来说

在第二轮的迭代之前

我们需要进行判断

一个判断这个方向是不是好

那另外一个我们需要判断

我需要去替换哪个方向

所以在这里大家可以看到

在第二轮的迭代计算的开始

我们首先需要去确定在上一轮当中

最大函数下降量及其相应的方向

所以我们在这里 大家可以看到我们

计算了△

那么根据△的大小

我们就能确定出来

它的最大的方向是哪个

那么同时我们可以计算出来

它的映射点及其对应的函数值

那么这些计算完了之后

接下来我们就可以进行检验

那么这个检验的时候

我们就根据刚才提到的

两个检验的条件来进行判断

那么在这个题目当中大家可以看到

那么我们经过了这样一个检验之后呢

发现它满足这样的两个条件的要求

那么

既然满足了这样的两个条件的要求

那么就意味着

我们这样一个方向呢是好的

那么这个方向是好的

那需要去进行替换

那么在替换之后

第二轮的方向是哪个方向呢

大家可以看到

是我们红框里面标出来的这个方向

也就是

我们在进行第二轮的迭代的时候

我们去掉的是

函数值下降量最大的那个方向

而不是一律的去替换掉

第一轮的第一个方向

那这样的话就最大可能的

避免了线性相关现象的出现

确定了第二轮的搜索方向之后

那接下来的过程我们就是

按照第二轮的搜索方向

分别做一维的搜索就可以了

好 那这个例题我们就讲到这

有关修正的鲍威尔方法这部分的内容

我们到此结束