7.10 约束优化-复合形法在线视频

各位同学大家好

我们已经给大家讲过了

一维无约束优化问题

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

在实际的设计问题当中

我们很多的设计变量

都会存在着各种各样的约束条件

那么因此针对实际的设计问题来说

那么我们更多的一种情况

是约束优化问题

所以接下来我们来看一下

有关约束优化问题的求解方法

对于约束优化问题的求解来说

我们经过前面的学习

我们大家知道它的数学模型为

我们现在

大家看到的这样的一个表达式

设计变量为x

目标函数为f(x )

它受到了这样的一些约束条件的限制

有可能是等式的约束条件

也有可能是不等式的约束条件

那么对于这一类问题的求解

我们称之为约束优化问题的求解

那么我们用什么样的方法

来去求这样些约束优化问题呢

那么我们通常情况下

可以分为这样的两大类

第一类我们是可以直接解

第二类

我们用间接的方法来进行求解

那么直接求解的这样一种方法

是什么呢

我们来看一下

对于直接求解的这样一种方法

我们只适用于

具有不等式约束的优化问题

那么如果

它既存在着等式的约束条件

也存在不等式的约束条件

我们就不能运用直接求解的方法

来进行求解

所以这点大家一定要注意

那么这一类

方法的基本思想指的是什么呢

在约束的可行域内直接搜索

它的约束最优解

那么在这里面大家一定要注意

我加红的这几个字

在约束的可行域内

我们刚刚讲到的梯度法

它的初始点是可以任意选择的

但是在这里面大家看到

我们对于约束优化问题的求解来说

对于直接解法

它要求的是

在约束的可行域内直接来进行搜索

所以它的初始点

就会有相应的限制

我们不能在设计空间当中任意来取值

我们只能在可行域当中来取值

那么在前边我们在讲到

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

给大家提到过可行域的概念

对于我们的约束条件来说

它会把设计空间划分为两大类

一类为可行域

一类为不可行域

所以对约束优化问题的求解来说

我们必须在可行域当中来进行求解

对于直接解法来说

我们常用到的有这样几个

一个复合形法

还有一个可行方向法以及网格法

那么 在我们这门课程当中

我们会给大家去讲到的

这种方法是复合形法

那么 除了直接的求解方法

我们还会有一些间接的求解方法

这种间接的求解方法

它的出现是为了解决

我们直接求解方法

它的一些限制条件

在直接解法当中

不能解决具有等式约束条件的

优化问题的求解

但是 在实际的工程问题当中

我们又有很多的问题

它具有等式的约束条件

所以 在这种情况下

人们提出了间接求解的方法

那么 这种间接求解的方法

它的思想是什么呢

它是把复杂的约束问题

想办法去构造一个新的目标函数

来转化为一系列的无约束优化问题

因为在前面无约束优化问题的求解

我们讲过了很多种的方法

所以一旦把这样一个问题转变为

无约束的优化问题之后

那么它的求解

我们就可以用我们前边提到的

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

来进行计算

那么 这里面的问题是

这种间接的方法

我去如何来转化呢

我如何来构造新的目标函数呢

这是我们大家需要注意的一点

也就是在间接求解方法当中

大家只要

搞明白了如何去构造新的目标函数

那么这样的一种方法

基本上大家也就掌握了

对于间接的求解方法来说

我们常用到的方法有这样几个

一个是消元的这样一种方法

还有简约的梯度法

那另外还有惩罚函数的这样一种方法

在这门课程当中

我们要给大家去讲的

是关于惩罚函数的这样一种方法

那么这种方法我们通常也把它简称为

罚函数法

对于罚函数法来说

它包括两类一类是内点法

还有一类是外点法

那么今天我们先来看一下

直接求解方法当中的复合形法

复合形法它的思路是什么呢

我们来看一下

它呢

首先先要构造一个初始的复合型

那么什么叫初始的复合型呢

我们可以看一下

我们先要在它的可行域当中

去构造k个点

通过这k个点

然后去构造一个多边形或者多面体

那么 对k的数量我们是有规定的

如果我们是一个n维的优化问题

我们要求所选择的

可行点的个数

应该要大于等于n+1小于等于2n

以二维的优化问题为例

k点应该要大于等于三

小于等于四

也就是可以是三角形或者是四边形

那么构造了这样一个

初始的复合形之后

那么接下来我们怎么做呢

我们需要对复合形

进行寻优的迭代计算

那么 我们接下来的循优迭代计算

我们是要利用复合形各顶点处

的目标函数值大小

根据它们之间的大小关系

我们判断目标函数值的下降方向

我们把最坏的那个点不断的去舍掉

用一个新的比较好的点来代替它

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

复合形的顶点的个数并没有发生变化

原来的复合形通过点的替换之后

我们又构成了新的复合形

依次进行下去

我们直到逼近它的极值点

所以复合形法是通过不断的去构造

新的复合形的这样一种方法

去逼近极值点的这样一种

求解的思路

在这里面 大家需要注意一下

我们在进行顶点替换的时候这个新点

什么样的点才算是好的

我可以去替换

在原来复合形当中的

不好的那个点呢

一个是它的目标函数值应该是要下降

另外一个是可行点

这个地方我们在这里强调一下

大家一定要注意

目前我们所讲到的方法

是约束优化问题的求解方法

所以在这里面涉及到的点

应该都是可行点

这里的可行点指的是点都在

可行域之内

也就是满足我们的约束条件

那接下来我们来看一下

这是一个构造的复合形

在构造的这个复合形当中

我们可以看到它是由四个顶点

构成的这样一个图形

那么现在有四个顶点

那么这四个顶点的目标函数值

我们分别给它做一个计算

那么计算之后

假设它满足这样一个关系

就是f(x1)>f(x2)>f(x3)>f(x4)

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

一点的目标函数值是最大的

那么四点的函数值是最小的

那么 很显然 在这个地方

我们说 我们要求函数的极小值

这个函数值最大的这个点

对于我们优化问题的求解来说

它是最不好的

所以我们把这个点称之为

最坏的这个点

我们把这个x4这个点

我们称之为最好的这个点

那么另外一个 我们在这里

可以看到我们还有一个形心

xc这个xc指的是什么呢

是去掉了最坏点之后

也就是我把x1点去掉了之后

原来的四个顶点变成了三个顶点

这三个顶点的

算数平均值就是我们这里的xc点

那么有了xc点之后

那接下来我们来判断

我应该往哪个方向去寻找新的点

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

这个方向的判断

我们通常会把xH

也就是这个最坏的这个点

和xc这个点进行连接

在这个方向上 我们进行一维的搜索

去找到对应的点

那么 如果这个点

我们发现它的目标函数值

是在下降的 它是一个好的点

它同样的也在可行域之内

我们就把这个点呢去替换我们原来的

xH去构造新的复合形

也就是由x2x3

x4再加上我新生成的这个点

去构成新的复合形

那么 通过这样的复合形的

不断的构造的这样一个过程

去逼近我们的极值点

这就是复合形法它的求解的思路

好 那接下来我们首先先来看一下

初始的复合形我们如何形成

那在前面我们提到对二维的

优化问题来说

它的初始复合形顶点的个数应该为

3-4个

那么这3-4个点我们如何来生成呢

是不是我们可以随意的来生成呢

我们来看一下

通常对于初始复合形来说

我们以这样的方式来进行构造

那么 第一个

我们人为的去给定k个顶点

构成初始的复合形

第二种 给定一个初始顶点

然后随机产生其它的顶点

那么 有同学可能会问

这个随机产生 我们怎么产生呢

那么在这里面大家需要注意

这里的随机 我们通常会通过

计算机编程语言当中的随机数

来进行产生

这个随机数的概念

或者说我们在这里提到的

随机生成的这样一个概念

在后边我们要讲到的

第八章

可靠性设计这一部分的内容当中

我们同样会运用到

所以这样的一种方法 大家需要注意

在计算机的编程语言当中

生成随机数的

命令通常为rand或者

随机这个英文单词的全拼

第三种方法是

计算机自动生成初始复合形

它的全部顶点

那么它的方法是

首先先产生一个可行点

然后按照我们刚才提到的

第二种方法产生其余的

k减一个可行点

从这个地方大家可以看到

如果我们采用的是第三种方法的话

首先产生的这个可行点

我们对于不同人来说

去求解同样的一个优化问题

我们生成的复合形是不一样的

那么知道了初始复合形的生成之后

那接下来我们来看一下

复合形的搜索方法

那么 也就是我们如何去构造新的

复合形

首先 我们来看第一个反射

这个反射指的是我们在计算完了

初始复合型各个顶点的目标函数值

我们也知道了在这个顶点当中

它的最好点 它的最坏点

以及它的次坏点之后

在这个基础上 我们去掉了最坏点

我们去计算另外的k-1个顶点的中心

也就是我们在这里提到的xc

找到了xc之后

那么接下来的这个反射

这个反射的方向是什么方向呢

一般情况下我们会发现

最坏点xH

和中心点的连线方向

是目标函数值下降的方向

也就是刚才我们看到

那个图当中绿色线条的那个方向

也就是把我们的最坏点xH

和xc连接起来

那么这个方向

就是目标函数值下降的这个方向

它既然是一个目标函数值下降的方向

那么接下来我们去寻找新的

顶点的时候

我们就可以沿着这个方向

去做一维的搜索就可以了

所以我们是以xc为中心

将最坏的这个点

按照一定的比例来进行反射

这个反射的计算的表达式

我们在这里已经给出了

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

我们这里面有一个系数

这个系数呢 我们用阿尔法来表示

它是反射系数

一般呢我们取α是1.3

在这个地方 很多同学可能会有疑问

这个α为什么要取1.3

我能不能取其它的数值呢

在这个地方

我们需要给大家去解释一下

这个α是一个经验值

那么 在我们实际的求解当中

α的值是可以发生变化的

但是我们建议大家

如果你对你的优化问题并不是非常

清楚的情况下 我们一般建议大家

α按1.3来进行处理

那么经过了这样一种计算之后

我们就会得到了这样一个反射点

那么这个反射点x2

究竟可以不可以作为

新的复合形的顶点

也就是说

它是否可以去替换

我们初始复合形当中的

最坏点x h

那我们需要进行判断

这个判断呢我们需要注意

由于它是约束优化问题

所以我们需要判断x2是不是一个

可行的点

也就是判断它是不是在可行域之内

如果在可行域之内

然后我们还要接下来判断

xR的目标函数值是不是比

最坏点的目标函数值要小

如果小 我们就替代

如果不小 那么

这样的一个点我们是不能去利用的

因为这个点比最坏的那个点还要差

所以在这种情况下呢

我们就不能完成

替代

那么 一旦出现了这样一种情况

怎么办呢

我们通常需要做这样的处理

也就是当我们新生成的反射点

目标函数值大于了我们的最坏点的

函数值

我们需要把α进行缩小

那就意味着我们这一步走的太远了

所以通常我们把它

缩短为原来的0.7倍

那么再次去计算

我们第二次生成的反射点

是不是满足我们这样一个要求

那么判断反射是不是成功

我们在刚才提到

一个是在可行域之内

另外一个呢

判断它的函数值

比最坏点的函数值呢要小

这是第一种搜索的方法

第二种搜索的方法呢 是扩张

扩张的这种搜索方法指的是什么呢

我们当求出来的这个反射点

是一个可行的点

并且呢 我们发现呢

目标函数值呢是下降的

那么 在这种情况下呢

我们就想去做一些尝试

那么 是不是让它走的更远一些

它的函数的下降量会更多呢

所以在这种情况下

我们通常会沿着反射的方向

让它继续移动

那么采取一种扩张的这种手段

那么这个就有点类似于

我们在前边讲到的

加速计算的这样一种方法

那么扩张的系数

我们用γ来表示

一般这个系数我们取1

那么扩张之后的这个点

我们仍然根据

刚才反射成功条件的判断方法

来判断扩张之后的这个点

是不是一个成功的这个点

如果是成功的这个点

我们就把这个点去替换我们的最坏点

而第三种搜索的方法是收缩

收缩的这种搜索

是一个什么样的过程呢

我们来看一下

如果中心点xc以外

我们找不到好的反射点

也就是当我们的反射系数

扩张系数在不断的发生变化

仍然不能够满足我们这样一个要求

也就说

我们找不到一个更好的点的时候

那么这个时候我们通常会采取

收缩的这种搜索方法

也就是在x c的内部

采用收缩的方法来寻找较好的点

那么 如果能够搜索成功

那么就构成新的复合型

那么第四个搜索的方法呢 是压缩

那么 这里的压缩指的是

将复合形的各个顶点呢

向最好的点来进行靠拢

压缩之后的点的计算公式呢

我们在这给出具体的这样一个过程

我们在这里呢 就不再

过多的给大家去做解释了

那么经过前边

初始复合形的生成

以及搜索方法的讲解之后

我们来看一下复合形方法的计算步骤

复合形方法的

计算步骤我们可以看一下

首先 我们先要构造初始的复合形

然后

去计算各个顶点的目标函数值

并且去比较它们的大小

那么我们在这里面呢

要找出最好的那个点

最坏的那个点 以及次坏点

然后呢 去计算它的中心点

计算出来中心点之后

接下来我们要去进行反射点的计算

如果反射能够成功

那接下来我们判断是否收敛

如果收敛成功

我们就得到了它的极值点

如果收敛不成功 我们继续进行

新的复合形的这样一个生成

所以这就是我们

复合形方法的计算步骤

那么有关复合形

求解的这样一个过程

我们今天就讲到这