7.5 一维优化-黄金分割在线视频

各位同学大家好

今天我们继续学习

现代设计方法学第七章

机械优化设计当中的

一维优化问题的求解

那么在上一讲当中

我们给大家讲到了

单峰区间的确定方法

我们采用的是进退试算法

那么今天我们来看一下

那么一旦确定了初始的搜索区间之后

我们如何选择合适的方法来进行

区间的缩小

那么在今天的课程当中

我们要给大家去讲到的是黄金分割法

黄金分割

大家是相对比较熟悉的一个概念

那今天我们来看一下

我们如何利用这个0.618

运用在我们一维优化问题的求解当中

那么在前面的课程当中

我们提到过一维优化问题的求解

实际上就是搜索区间

逐渐缩小的这样一个过程

那么我们大胆的来猜测一下

那么这里的0.618是不是就是

我们每一次区间缩小的比例

就是0.618呢

好 那接下来呢

我们来看一下黄金分割法的基本思路

那么对于黄金分割法来说

首先我们需要知道一个单峰区间

那么然后呢我们在单峰的区间当中

我们内插两个点

内插两个点之后

我们去比较内插两个点的函数值

通过相应的判断

我们不断的去舍去

单峰区间当中的左端或者右端

那么究竟应该舍去左端还是舍去右端

我们一会儿会给大家详细的来说

那么舍去了区间的一部分之后

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

我们初始所确定的这样一个单峰区间

就在逐渐的被缩小

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

黄金分割法

区间缩小的这样一个比例是相等的

也就是它按照固定区间缩短的

这样一个比率来逐步的去缩短

直到极小点所在的区间

缩短到了给定的误差范围之内

那么我们就得到了近似的最优点

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

我们在这里提到的是近似最优解

因为我们采用数值迭代的方法

我们得到的都是近似解

那么只有采用解析的方法

我们才能够得到

它的理论上的极值点

好 那接下来我们来看一下

这个初始的单峰区间

我们如何按照固定的比例

来进行缩短呢

那我们来看一下

那么在这个图上大家可以看到

我给出了这样的两幅图

那么假设我们初始的单峰区间是[a,b]

在[a,b]当中我们内插了两个点

这两个点我们分别用x1和x2来表示

那么这两个点都在[a,b]区间内

同时满足这样一个特点

x1是小于x2的

我们现在令f1=f(x1)

令f2=f(x2)

那么我们来看一下

我们如何去缩短这样一个区间

也就是刚才我们提到的

我要不断的去去掉区间当中的

左端或者右端

那么我们是应该去掉左端

还是去掉右端呢

我们来看一下

那么第一种情况 我们来看一下

如果说f1小于f2的话

那么也就是像我们现在看到的

图上的右侧这个图

那么 f1小于f2

我们很显然可以看到我们的极值点

是位于[a,b]区间的左端

所以我们在这种情况下

区间的右半部分我们是可以去掉的

也就是[x2,b]这个部分是可以去掉的

所以通过这样的一种方法

我们就可以判断

那么接下来我应该是

保留区间的左端还是右端了

那么我们接着往下看第二种情况

如果f1>f2像我们现在看到的

左边这幅图的情况

那么在这种情况下

很显然我们可以看到

它的极值点是在右侧

所以区间的左边这一部分

是可以去掉的

也就是我们看到的

[a,x1]这部分是可以去掉的

那么如果f1=f2的时候

那么通常我们保留的区间

是[x1,x2]

因为极值点肯定会在[x1,x2]区间之内

所以大家可以看到

对于一维的优化问题求解来说

按照这样的一种方法

我们就可以不断的去缩短区间

从而呢逼近我们的极值点

好 那接下来我们来看一下

对于黄金分割法来说

它要内插的这两个点x1 x2

是不是随意来给出的

那么在这里面呢 我们可以看到

对于黄金分割法来说

内插的两个点它是有一定要求的

它的要求我们来看一下

由于黄金分割法

它采取的是

固定区间缩短的这样的一种方法

所以按照这样一种原则

它的区间的缩短率都是取

λ等于0.618的

也就是新的区间是原来区间的0.618倍

所以就是我们在这一节刚开始的时候

我们的猜测是正确的

那么既然每次缩短的区间是0.618倍

所以我们就可以看到内插的这两个点

不是我们随意来取的

是有一定要求的

按照每次区间缩短比例相等的原则

我们可以计算出

这个区间缩短的比例λ

它近似等于0.618

那么这也就意味着

只要我们取λ等于0.618

我们就可以满足

区间缩短率不变的这样一个要求

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

就满足了我们黄金分割法的

这样的一个基本要求

那么因此我们大家可以看到

黄金分割法我们也称之为0.618法

是这样得来的

好 那接下来我们来看一下

既然我们确定了每次区间

缩短的比例是0.618倍

那么我们就很容易能够得到

内插两个点的取点规则

那它们的取点规则呢我们可以看到

内插的这个点如果是a1点的话

a1大家可以看它应该等于a点坐标

那也就是我们区间的初始点a点

再加上1-λ倍的

b-a也就是我们的区间长度

所以它应该等于从左端的a点

加上0.382倍的区间长度

那么右侧的这个点a2点呢

它应该等于a点加上0.618倍的

区间长度

实际上我们还可以

做一个换算

大家来看一下

那么对于我们的a2点

它是不是等于b点减0.382倍的区间长度呢

那么通过这样的公式 我们可以看到

区间当中内插的两个点我们就确定了

确定了内插的两个点之后

那接下来的问题

就和我们刚才大家看到的

我们区间缩短当中

我们判断是保留左端

还是保留右端的这个过程是一样

好 那接下来我们来看一下

对黄金分割法来说

它的计算步骤

是这样的

第一步

我们先要给定初始的单峰区间[a,b]

和收敛精度ε

那么这个单峰区间[a,b]

如果在题目当中没有告诉我们

是需要我们自己来

利用进退试算法来进行确定

收敛精度是我们根据题目的要求

来自行设定的

确定了搜索区间和

收敛精度之后

那接下来按照刚才的

内插两点的这样一个规则

我们在[a,b]区间当中内插两个点

插入两个点之后

我们分别

去计算这两个点的目标函数值

然后对两个目标函数值进行比较

也就是我们的f1 f2的大小进行比较

按照我们刚才分析的这样一个思路

我们知道如果f1小于f2

那么在这种情况下我们应该取α2

来作为我们新的区间

也就是我们要把右侧的区间给它去掉

我们保留区间的左侧

那么如果是另外的一种情况

f1是大于等于f2的

那么在这种情况下

我们需要保留的是区间的右侧

把左侧的部分可以去掉

也就是

我们新的区间为[α1 b]这样一个区间

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

经过这样的一次内插两个点

我们就把这个区间缩小为

原来的0.618倍

那么新的区间得到了之后

我们黄金分割法是不是就结束了

很显然我们没有结束

就像其它的数值迭代法一样

我们需要进行迭代终止的判断

那么这个迭代终止的判断

我们通常情况下是用区间长度的

一半来进行判断的

也就是利用区间的中点来进行判断

那么对于新确定的这样一个区间

我们是否就可以

作为我们极值点的这样一个

逼近的区间呢

那么 在这种情况下

我们需要进行迭代终止的判断

好 那接下来呢 我们来看一下

迭代终止条件的判断

我们通常是按照这样一种方法

来进行判断的

那么如果它满足了这样的一个条件

也就是区间长度小于等于我们的

收敛精度

那么这种情况下我们就

不再进行下一次的迭代

而是直接输出我们的最优解就可以了

那么如果说

这个区间长度还很大

它不满足我们这样一个收敛精度的要求

也就是b减a是大于ε

那么在这种情况下

我们需要重新回到第三步

我们需要内插两个点

再次去进行区间的缩短

直到满足

我们这样一个迭代终止条件为止

那么对于它的最优解

我们如何来进行求解呢

如果满足了迭代的终止条件

那么它的最优解的输出

是用区间的中点来作为它的

极值点

也就是x*等于a+b/2

f*等于f(x*)

好 那么这是我们黄金分割法

求解的基本过程

那么为了让大家更好的去理解

这样的一种方法

我们在这里给大家给出了一个例题

大家课下呢可以自己先去试着算一下

然后再和我们在ppt当中给出的答案

做一个比较

那么更好的来掌握这样的一种

一维搜索的这样一种方法

好

今天的内容我们就讲到这