7.6 多维无约束优化-基本鲍威尔方法在线视频

各位同学大家好

今天我们继续学习

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

那么在上节课呢我们给大家讲到了

坐标轮换法

那么在上讲的内容当中

我们提到坐标轮换这样一种方法

虽然它的计算比较简单

但是它有一个致命的缺点

就是它的收敛的速度是比较慢的

那么在这种情况下

那么有同学可能又会要问

那么我们有没有更好的方法

来替代它呢

那么针对坐标轮换法

收敛速度比较慢的这样一个问题

那今天呢

我们来学习一种新的算法

那么这种算法是什么呢

它的名称叫鲍威尔方法

它的英文的

名称大家可以看到是powell

那么鲍威尔这样一种方法

很显然我们知道这样一种方法呢

是由鲍威尔提出的

这种方法的出现是为了

解决我们在上讲当中提到的

坐标轮换法收敛速度

比较慢的这样一个问题

那么它究竟是如何来解决的呢

它和我们的坐标轮换法有没有关系

那么带着这样一些问题

我们来学习一下鲍威尔方法的求解

鲍威尔方法呢 我们又称之为

共轭方向法

提到了共轭方向

大家应该对这个词不陌生

在之前相关的数学课程当中

我们提到过

那么什么是共轭方向呢

引入了这样一个共轭方向

为什么就能达到提高收敛速度的

这样的一个目的呢

那么我们从现在的这样一段话当中呢

我们可以看到鲍威尔方法呢

又是在坐标轮换法的基础上

去构造的共轭方向

它和坐标轮换法之间的关联关系

又是什么样的呢

那么首先我们来看一下第一个问题

什么叫共轭方向

那么我们只有对这样一个方向

有了充分的了解之后

我们才知道这个方法

为什么能加快收敛的速度

好 那接下来我们来看一下

什么叫共轭方向

对于共轭方向来说

我们假设有两个n维的矢量s1s2

对于nxn阶的对称正定矩阵A

如果它能够满足s1的转置乘上A

再乘上s2应该等于零

如果满足这样条件的话

我们就称n维空间矢量s1和s2对A是共轭的

那么 看到了这样一个表达式之后

很多同学可能会想到这样的一个

我如果把A给它去掉了呢

也就是像我们下面写出来的这个

也就是s1的转置乘上s2如果它等于零

这属于不属于

我们这里的共轭的概念呢

那么很显然我们可以看到

如果s1的转置乘上s2等于零

我们知道这两个方向是垂直的

那么这两个方向垂直

我们就可以得到s1的转置乘上E

再乘上s2是等于零的

很显然我们可以看到

s1和s2是关于E共轭的

那么因此呢

我们大家可以得到这样一个结论

也就是

正交是共轭的一个特例

所以我们判断两个方向

是不是共轭方向

我们就根据这两个方向

和矩阵的这样一个乘积

是不是等于零

如果等于零我们就认为

这样的两个方向

关于这个矩阵是共轭的

好 那接下来我们通过两个

简单的小例子我们来看一下

那么大家可以看到我们给出了A

这样一个矩阵 s1矩阵和s2

那么这时候呢 大家可以看到

对于

这样的一个问题来说

我们算一下s1的转置乘上A在乘上s2

我们可以看到它等于零

它等于零我们就知道它是

s1s2关于A是共轭的

那么我们再算一下

那么把A去掉了之后

也就说这两个方向是不是正交呢

或者说这两个方向是不是垂直呢

我们来看一下这两个方向

很显然也是垂直的

所以这个地方大家可以看到

这里的s1s2是共轭并且正交的

我们再来看另外的一个

那么这个呢 我们可以看到

s1的转置乘上A乘上s2等于0

它满足我们刚才提到的

共轭方向的基本概念

所以它是共轭的

但是我们可以看到

s1的转置乘上s2不等于0

所以它不正交

所以对共轭来说呢我们可以看到

那只要满足了

s1的转置乘上一个矩阵A乘上s2等于0

这两个方向就是共轭的这样一个方向

好那么我们知道了这样一个概念之后

我们看

对于我们这样一种方法的理解来说

有什么样的帮助呢

为什么我们要去

构造这样一个共轭方向呢

我们接下来以一个

二维的正定二次函数为例

我们来看一下

对于二维的正定二次函数来说

它具有两个非常重要的特性

第一个特性我们大家看一下

是二维正定的二次函数

它的等值线是同心的椭圆族

这个大家不陌生我们在前面在讲到

数学模型的它的组成要素的时候

我们曾经给大家提到过这样一个问题

如果等值线是同心的椭圆族

那么椭圆的中心必定是它的极值点

那么我们再来看第二个重要的特性

第二个重要的特性呢

我们可以看到是过同心椭圆族的中心

也就是我们现在大家看到的

这个红色的x*

红色的x*

过这一点我们做任意的一条直线

那么这条直线和椭圆会有两个交点

过这两个交点

我们分别去做切线

那么这两条切线呢是会平行的

也就是我们现在大家可以看到

我过x1x2这两个点

我做出来的这两个切线是平行的

我们换一句话说

那么如果两条平行的任意方向的切线

那么我们把两个切点给它连起来

这条直线必定过椭圆族的中心

那么这个椭圆族的中心呢

我们大家又都知道它就是我们的极值点

所以大家可以看到这个共轭方向

是一个非常好的这样一个方向

因为我一旦找到了工作方向之后

我就能够非常快速的去

得到这样一个极值点

因为我构造了一个s1

构造了一个s2这样的两个方向

这两个方向一定之后

那么我把这两个切点一连

那么在这个方向上

我只要做一次一维的搜索

就可以一步到达它的极值点

所以这样的话大家可以看到

相对于我们坐标轮换法来说

每次都是第一个坐标轴

第二个坐标轴

第二轮又是第一个坐标轴第二个坐标轴

这样的一种方法来进行搜索

它的收敛速度显然要快很多

所以共轭方向

是一个非常好的这样一个方向

那么鲍威尔方法就是把这样一种方向

作为我们的搜索方向

那么我们在前面提到鲍威尔方法呢

又是在坐标轮换的基础上来构造

那么究竟如何在坐标轮换的基础上

来构造呢

我们在这里来看一下

那么对鲍威尔方法来说

它的第一轮的第一步

和第一轮的第二步

和前边讲到的坐标轮换法

是完全相同的

也就是

我们在空间当中任选一点

作为我们的初始点x0

那么x0同时是我们第一轮的初始点

第一轮的初始点

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

进行一次一维的搜索

我们得到第一轮的

第一个点

从第一轮的第一个点开始

然后我们沿着第二个坐标轴的方向

得到第一轮的第二个点

那么按照前边

坐标轮换法的这样一种思想

到了这个点之后我就要需要进行

迭代终止的判断

那么如果迭代满足迭代终止的条件

迭代就结束

如果不满足

我需要重复进行前面的步骤

但是鲍威尔这样一种方法

是为了加速我们前面提到的

坐标轮换法的收敛速度

所以它在进行了这样的两次

一维的搜索之后

它又增加了一步

所增加的这一步

就是我们刚才提到的

去构造一个共轭方向

那么这个共轭方向

它是如何来构造的呢

它是这样

它把我们的x10这个点

和x12这个点进行连接

这两个点连起来之后

我们大家可以看到就得到了一个方向

那么沿着这个方向

做一次一维的搜索

那么所得到了这个点

我们用x1这个点来表示

大家注意

这里的x1是x右上角标有一个括号1

它的右下角标我们看到没有

那么x1这个点

是鲍威尔方法当中第一轮的终止点

那么这种情况下

我们就可以进行

迭代终止条件的判断了

那么判断x1点和我们的x10点

两点之间的距离是不是足够小

如果没有足够小

那么我们需要进行下一轮的迭代

那么在下一轮的迭代当中

我们又是如何来展开的呢

在这个地方大家要格外的注意

它和我们的坐标轮换法不一样

坐标轮换法是第一轮x1x2

第二轮仍然是x1x2

所以这种方法大家非常容易理解

但是对于鲍威尔方法来说

由于在第一轮当中

它生成了三个方向

一个是x1一个是x2

还有一个我们把x10和x12连接起来

之后构造出来的s1这样一个方向

这三个方向在下一轮的迭代当中

并没有全部的使用

它的原则是去掉第一个方向

也就是我把x1这个方向给它去掉

那么在第二轮当中

我们是把x1点

作为我们第二轮的初始点

从这一点沿着x2轴的方向

我们得到了第二轮的第一个点

那么接下来的这个方向呢

我们是从这个点开始

沿着我们在第一轮当中生成的s1

的这个方向来进行搜索

那么沿着这个方向来进行搜索之后

大家看一下我们这个图

在这个图上大家可以看到

现在就有了两条平行线

那么这两条平行线大家可以看到

它都是s1

大家回想下我们刚才刚刚提到的

正定二次函数

我们画出来的那个图

这两条平行线有了

我把这两条平行线和等值线

的切点给它连起来

那么连起来之后大家可以看到

那么这个方向

就是我们和s1所共轭的

这个s2这样一个方向

那么这个方向

必定会过我们椭圆的中心

也就必定会过我们的极值点

所以呢这样的话

大家可以看到我们的极值点

就可以找到

在第二轮的迭代当中

我们是从x20沿着x2的这样一个方向

去得到x21

从x21沿着s1的方向我们去得到x22

那么我们把x22和x20连接起来

构成s2方向

沿着这个方向进行一次一维的搜索

就得到了我们第二轮的终止点x2

那如果它是一个正定的二次函数的话

那么这个x2点就是它的极值点

所以大家可以看到

对于二次函数来说

它的收敛速度是非常快的

所以这也就是为什么我们在这里

提出这样的一种鲍威尔的求解方法

对鲍威尔求解方法来说

我们可以看到

它的收敛的速度

显然要快于我们的坐标轮换

尤其是对于正定的二次函数来说

它的收敛速度是非常非常快的

但是很显然我们可以看到

对于正定的二次函数来说

它的收敛速度加快了很多

但是对于非正定的二次函数来说

它的收敛速度并没有显著的增加

那另外一个对鲍威尔方法来说

它有一个基本的要求

它要求的是各轮迭代当中

方向组的向量应该是线性无关的

那么如果一旦出现了线性相关的问题

并且这种线性相关的问题

是非常有可能出现的

那么这种现象一旦出现之后

会造成一个搜索退化的问题

那么搜索一旦退化之后

极值点我们就得不到

所以鲍威尔方法

它也有自身的这样一个缺点

但是对于正定的二次函数来说

鲍威尔方法

是一种非常快速的这样一种方法

我们经过两轮的迭代之后

我们就能够得到它的极值点

好

有关鲍威尔方法的内容

我们今天就讲到这