7.8 多维无约束优化-坐标轮换的算法思想在线视频

各位同学大家好

在前面的课程当中我们给大家讲到了

一维优化问题的求解方法

那么对一维的无约束优化问题来说

我们可以通过黄金分割法

通过二次插值的这样一些方法呢

来进行求解

它的求解的思路呢

实际上就是我们首先

要通过进退试算的方法

来确定一个单峰的区间

然后呢

在这个单峰的区间当中

我们选定合适的方法

不断的去缩小这样一个区间

直到这样一个区间缩小到足够小为止

那么这样的话呢

就能够去逼近我们

一维无约束优化问题的极值点

那么对于无约束的优化问题来说

除了一维的问题之外

我们在实际的设计问题当中

我们还会存在多维的无约束优化问题

对于多维的无约束优化问题来说

它的求解的方法又是怎样的呢

那么 今天我们来探讨一下

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

对于多维无约束优化问题的数学表达式

我们在前边学过了

第七章的

优化数学模型的表达方法之后

我们知道它的表达式应该是

我们现在看到的这样

就是目标函数f(X)求它的极小值

那么X是一个向量

它是由x1 x2 xn来组成的

由于它是一个无约束的优化问题

那么因此呢

它没有约束条件

也就是我们在标准数学模型当中

所提到的不等式的约束条件

和等式的约束条件

它是不存在的

那么对于这一类的问题来说

我们又如何来求呢

那么一般情况下我们对无约束的

多维的优化问题来进行求解的方法

主要有这样的两大类

一类呢是解析的方法

一类是直接的方法

那么这两类方法

究竟指的是什么呢

我们来看一下

对于解析的这样一种方法来说呢

我们大家从字面上我们就能知道

我们肯定是要利用数学上的求解方法

来进行这样一个优化问题的解决

那么 因此呢

解析法是利用函数的一阶偏导

甚至二阶偏导来构造搜索方向

那像我们后边提到的梯度法

就属于我们解析法的一种

当然我们还有牛顿法

和变尺度的方法

这一类的方法呢

它所具有的特点是由于计算偏导数

所以它的计算量是很大的

那么对于我们手工的计算来说

这是一件非常困难的一件事情

那另外我们可以看到

解析的方法要进行导数的求解

那么这就要求

我们这样一个目标函数是可导的

所以它有一定的适用范围

那么对于函数不可导的这种情况

怎么办呢

我们就可以利用下面这种方法直接法

直接法呢它不用求函数的导数

而是利用迭代点的函数值

来构造搜索方向

那么这个搜索方向我们如何来构造呢

那么后面我们会给大家讲到

坐标轮换法

鲍威尔方法

等等这样的一些方法

那么这些方法呢

都属于我们在这里提到的直接法

因为它不需要求它的导数

而只需要计算

对应的函数值就可以了

所以它对于目标函数

求导困难的这样一种情况

是非常方便的

但是这种方法

它也有一个不好的地方

就是它的收敛速度

相对于解析法来说是要慢一些的

好 那接下来呢 我们今天先看一下

在多维无约束优化问题求解当中的

第一种方法

也就是我们提到的直接法当中的一种

我们把它称之为坐标轮换法

坐标轮换法是一种什么样的方法呢

它实际上我们从字面上

可以去进行猜测

那么从字面上我们可以看到

坐标轮换

也就是如果是个二维的问题

那么也就是它的x坐标

y坐标我们要进行互换

那么具体这里的互换

指的是一种什么样的互换方法呢

那么我们来看一下

这种方法的基本原理

那么这种方法的基本原理呢

大家可以看到

它实际上呢是依次沿着坐标轴的方向

来进行一维搜索

那么在前面我们曾经给大家讲到过

数值迭代方法的一个关键的问题是

我们要确定合适的搜索方向

不同的搜索方向

就会诞生不同的优化算法

那么 现在对于坐标轮换法来说

它的搜索方向我们可以看到

是依次沿着坐标轴的方向来进行的

也就是说

它如果是一个二维的问题

我先沿着x1再沿着x2进行一维的搜索

那么

这就是它的一个

基本的一个求解思路

那么这样的话呢大家可以看到

它虽然是一个多维的问题

但是因为每次的时候

只是沿着一个坐标轴的方向

来进行搜索

那么这种搜索

实际上就是一个一维的搜索

那么 因此我们可以看到

那么这种方法它实际上是一个

把多维的优化问题

转变为一维的优化问题来进行求解

一维优化问题的求解

我们在前边已经讲过了相应的方法

所以这样的话呢

大家可以看到多维优化问题

通过这样的一种转变

我们就可以进行求解

那么 这是坐标轮换法的基本原理

那有同学可能还会有疑问

那我如何沿着坐标轴的

方向来进行搜索呢

那么 坐标轴的方向

我们又如何来进行表示呢

那么这个极值点

我们又如何来进行确定呢

那么这个我们后边马上给大家来讲

所以首先大家要清楚

坐标轮换法

是一种多维无约束优化问题

求解的方法

它的思路实际上是用降维的方法

把多维的问题转化为

多个一维的问题来进行求解

好 那接下来我们来看一个图

我们来分析一下对于

坐标轮换法它的搜索过程

假设我们选定了初始点之后

那么在空间当中

我选定了一个初始点之后

那么从这个初始点

我应该沿着什么样的方向来走呢

我们刚才提到了坐标轮换法

是依次沿着坐标轴的

搜索方向来进行搜索

所以这是一个二维的问题

它应该有两个坐标轴

我们如果用x1和x2来表示的话

那么从初始点开始

我们首先先沿着x1轴

进行一次一维的搜索

去得到一个极值点

然后我们再从这个点出发

再沿着x2轴的这个方向

再进行一次一维的搜索

那么得到第二个点

那么这样两个点得到了之后

我们才完成了一轮的迭代

所以在这里面

大家需要注意我们在这个图当中

的一些符号

那么我们的初始点

我们可以用x0来表示

那么另外一个在这里面

大家可以看到它的x的

角标有两个

一个上角标 一个下角标

那么下角标它代表的是第几个点

上角标它有一个括号

括号里面的数字代表的是轮

也就是第一轮的迭代

还是第二轮的迭代

如果是第一轮的迭代

我们括号里面写1

如果是第二轮的迭代

我们括号里面写2

那么我们现在从头

开始

比如说

我们在空间当中任选一点x0点

把这个点作为我们的起始点

那么接下来我们开始运用

坐标轮换的方法来进行求解

那么这个初始点实际上也是我们

第一轮搜索的初始点

所以x0和x10是相同的

当然我说的这个x10 1是

右上角标的括号1

也就是第一轮的初始点

就等于我们选定的

设计空间当中的初始点

从x10出发沿着x1轴

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

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

也就是我得到x11这个点

x11得到了之后

还需要沿着另外的一个坐标轴

也就是x2轴进行第二次的

搜索

这里的第二次的搜索指的是

第一轮第二次的搜索

也就是沿着另外的一个坐标轴的方向

进行一次一维的搜索

那么得到我们第一轮的第二个点

也就是我们用x括号12来表示

那么这样的话呢 大家可以看到

经过两次一维的搜索之后

我们就完成了第一轮的迭代

因为它是一个二维的问题

所以我们在一轮当中

只需要进行两次一维的搜索就可以了

那么如果是个三维的问题

在一轮当中

我们需要进行三次一维的搜索

那么这样的话大家可以看到

我完成了一轮的迭代之后

接下来

我是否需要进行第二轮的迭代呢

那么同样

我要进行迭代终止条件的判断

那么这个迭代终止条件的判断

我怎么来判断呢

那我是用x11减去x0

还是用x12来减去x10呢

那么这个地方我们大家需要注意

在这一轮的起始点是x10这个点

那么这一轮的终止点是x12这个点

所以

我们应该把首尾两个点之间的距离

来作为我们迭代终止条件的判断

如果这两个点之间的距离

小于了我们给定的收敛精度

那么我们这样一个迭代就可以结束

如果不满足我们这样一个

迭代精度的要求

我还要需要进行第二轮的迭代

那么 在第二轮的迭代当中

我们第一次的搜索方向仍然是

从x12开始沿着

x1轴的方向做一次一维的搜索

再沿着x2轴的方向

来进行一次一维的搜索

所以在第二轮的迭代当中

我们大家可以看到第一轮的

第二个点实际上是第二轮的

零点 也就是第二轮的初始点

从第二轮的初始点开始

我沿着x1轴的方向我就可以得到

x21这个点

也就是第二轮的第一个点

那么 从第二轮的第一个点开始

我沿着x2轴的方向

我就可以得到第二轮的第二个点

所以每一轮的迭代都是这样一个过程

所以大家可以看到

坐标轮换的这样一种方法

实际上是非常容易理解的一种方法

也就是在每一轮的迭代当中

我都是先沿着x1

再沿着x2来进行搜索就可以了

但是在这里面大家可以看到

它的搜索的过程是这样的

但是在求解的过程当中

我们大家还是需要注意一些问题

那么比如说

我现在问大家这样一个问题

从x10-x11搜索的这样一个过程当中

我们知道它的表达式应该是

x11应该等于x10+α1乘上一个

s1

这里的s1指的是

第一轮第一次的搜索方向

它是x1轴的方向

这个方向我们如何来表示呢

用谁来表示它呢

那另外一个第一轮的

步长我们如何来确定呢

也就是现在图上的x11这个点

我们是怎么得到的

它的距离是多大呢

它距离x10的距离是多远呢

那么这个问题我们接下来呢来看一下

对这样一个问题来说呢

它首先我们来看一下

我们在坐标轮换法当中

我们是依次沿着坐标轴的方向

所以对于坐标轴方向

的这样一个确定来说

我们是用单位向量来进行表示的

也就是我们用e1 e2 e3 en来表示的

所以这样的话呢

大家看到对一个二维的

优化问题来说

e1就等于10它的转置

e等于01的转置

那么这样的话呢 大家看到

我们刚刚

提出的第一个问题也就解决了

也就是

在坐标轮换法当中这个方向

我们用谁

来表示

也就是用单位向量e来表示

那么e确定了之后

接下来的一个问题

就是我一步要走多远呢

这个α我们如何来确定呢

那么比如说

像我们现在

看一下第一轮的这样一个过程

那么在第一轮当中

假如我任取了一点初始点x0

那么e1这个方向

我们刚才已经提到了[1 0]的转置

e2是[0 1]的转置

那么接下来我们来看一下

这一轮迭代的一个完整的过程

第一轮的初始点就等于

我们选定的这个初始点x0

所以我们把x0赋给x10

那么x11第一轮的第一个点

我们就可以计算出来了

那11点应该等于

10点加上α1乘上一个e1

那么这个时候呢 大家来看一下

e1是已知的

x10也是已知的

我们在这里面唯一未知的一个是α

那么这个α我们如何来确定呢

那么这种方法大家一定要掌握

这在我们后边的优化算法当中

都会要涉及到这样一个最优步长

确定的方法

实际上 这样一种方法呢也很简单

那么它怎么来求呢

我们来看一下它是这样

这种求解的方法也就是

我们现在把x11给它得到了 之后

我们把x11代入到

我们的目标函数当中

代到目标函数当中之后

大家可以看到

在目标函数的表达式里面

仅有一个未知量α

那么目前我们来看

我们所做的这件事情呢

是一个优化问题的求解

我想求的是目标函数的极小值

那么在目标函数的

这样一个表达式里面

它仅仅含有α

所以我们很容易就会

想到我们在高等数学当中

极值问题的求解

我们令这个目标函数的表达式

它的一阶导数为零

我们就可以求出在k点处的

或者说我们刚才提到的

在第一轮当中的

α1我们就可以得到

也就说在这个地方大家可以看到

最优步长的确定方法

实际上就是

把新生成的这一点的坐标

代入到目标函数当中

那么去求它对应的目标函数值

那么让目标函数值

它的一阶导数为零

我们去得到对应的α

那么α我们求出来了之后

我们再返回到

新生成的这个点的坐标里面

大家就可以看到

从10点到11点

这个过程我们就完全解决了

因为11这个点已经

可以完全的求出来了

因为10是已知的α我们现在求出来了

s也已知

它等于e1

所以这样的话呢

新的一点就可以确定了

那么对于x12的确定

我们同样的这样一种方法

所以在这里面呢 大家需要注意

在坐标轮换法当中

大家知道搜索方向

是沿着坐标轴的方向

那么最优步长的确定方法

是把新生成的这个点

的坐标代入到目标函数当中去求

目标函数的极小值

运用高等数学上的方法

我们求出最理想的步长

也就是我们提到的最优步长α

那么新点就可以产生了

那么 按照这样的一种方法

我们每一轮的迭代都可以完成计算

那么 在什么情况下

这个坐标轮换要终止呢

那么就是要看一下

我们迭代的终止准则

那么我们对比一下在每一轮当中

它的起点和终点两点之间的距离

如果

这一轮的起点和终点

之间的距离足够小

那么我们的坐标轮换就可以终止了

那么最后的这个点就是我们的极值点

这就是我们

今天要给大家讲到的

坐标轮换的这样一种方法

那么这种方法大家可以看到

它的计算是比较简单的

那么有同学说 那是不是我所有的

优化问题都可以用这样一种

比较简单的方法来进行求解呢

但是在这里面大家需要注意

这个方法虽然简单 但是它也有缺点

它的缺点是收敛特别慢

它的收敛的速度和等值线的形状

是有关系的

所以这样一种方法

并不适合所有问题的求解

那另外一个

对于这样一种方法的求解来说

仅仅适用于低维的优化问题

对于多维的优化问题来说

比如说n大于10的这样一种

高维的优化问题是不适用的

好

今天的内容我们就讲到这儿

那么大家课下可以去看一下

我们教材上的坐标轮换法

对应的例题

大家自己来学习一下

今天的内容就到此结束