5.1 复合形法在线视频

今天我们讲解约束优化方法

我们在上一次我们讲了无约束优化方法

我们知道在我们实际工程中往往是存在约束的

因此说对于约束优化方法

以及约束优化问题的求解

实际上是我们真正在工程中会遇到的问题

我们看看对于约束优化问题的求解是如何的

数学模型求f(X)我们的目标函数给出来以后

求它的极小值

然后由不等式约束和等式约束gu(X)小于等于0

有u是1到m个

然后hv(X)是等于0

v是1到p个 p是小于n的

那么它的方法分为两类

一类是直接法

一类是间接法

直接法在可行域内直接搜索或者是探索最优解

如随机方向法复合形法简约梯度法以及

广义简约梯度法和可变容差法等等这些方法

那么这是直接法

另外一个方法是间接法

将约束优化问题化为无约束优化问题

用无约束优化问题的方法来进行求解

那么间接法代表性的包括罚函数法广义乘子法

我们这里边直接法选一个

间接法选一个给大家再进行讲解

第一个我们在直接法里面我们称为是复合形法

那么思路是先在可行域内产生一个具有

k大于n+1顶点的初始复合形或者多面体

对其各个顶点的函数值进行比较

不断的丢掉坏点

用既能使目标函数值有所下降

又满足约束条件的新点

取而代之逐步的去逼近

最优点X*

复形法是求解无约束优化问题的

单纯形法的一个推广

通过这样一个图形来看一看

整个区域是定义域由于约束面的问题

变成了这样的

一个可行域

假如说这是我们的等值线和极值点

对于无约束优化问题

那么它的极值点在这里

但是由于我们的约束面把极值点变成了不可行解

所以说我们对于约束优化问题

我们在这个可行域内求解极小值点就不能取这一点了

那怎么来计算

在可行域内取

k大于等于n+1个点构成

复合形或多面体

这个x应该是两维

k大于等于2+1是3

所以要取三个点

一个点

Xh Xl和Xg

那我们把函数值大的称为是坏点函数值小的称为是好点

那么在这两个之间我们称为是次坏点

Xh是坏点Xl好点Xg是次坏点

我们把这三个点进行连接

产生一个复合形或一个多面体

那么既然是一个平面三个点我们构成一个三角形

我们让坏点

对于好点和次坏点做映射

到了Xr有了Xr以后

我们再去讨论XrXgXhXl的函数值

然后选取好点

坏点和次坏点

应该是Xr会变成一个好点

然后我们舍去坏点来进行计算

删除坏点

然后变成一个新的复合形

Xg就变成坏点了

Xl变成什么了

次坏点

那么这样的话到了好点

同样坏点对于好点和次坏点做映射

然后找到新的点

然后删除坏点

重新构造复合形

然后再做映射

再删除构造新的复合形

再做映射

基本上也是向着我这个X*的方向去逼近

那么我们看一下复合形的方法

刚才我其实我已经说了一些了

第一个

无需求目标函数的导数

只计算目标函数值

因此对目标函数约束函数无特殊要求

第二

不用进行一维搜索

只比较目标函数值

第三

程序简单

第四

当维数n大于等于5时

收敛速度较慢

看一看它的方法与迭代步骤

数学模型minf(X)s.t:gu(X)小于等于0

Xi大于ai小于bi那么包括

性能约束和边界约束

第一形成k我们这里k是大于等于n+1的

小于等于2n的顶点的初始复合形

第二

按目标函数值大小

找出坏点好点和次坏点

坏点是这里面的所有k个点里边的最大那个点

好点应该是所有这里边的最小那个点

然后剩下就是次坏点

然后求Xh点之外的k-1个顶点的形心Xc

我们再给个图看一看Xc

然后如果是高维的话

直接用公式计算就可以了

那么如果Xc为可行点

则求反射点Xr

Xr等于Xc加α

Xc减去Xh那么这里边我们做的映射的时候

我们让步子稍微胆子大一点

做映射

找到我的Xr Xc减Xh然后αXc减Xh

1.3倍的稍微大一点

找到Xr

那我们看了如果说我的Xr越出可行域的时候

那我们怎么办

步子减半

α等于α/2重新求Xr

直到

可行

如果Xc点

不在可行域内的话缩小

ai和bi重新产生k-1个顶点

形成新的复合形再求Xc

那么再返回第二步

第四步计算f(Xr)若f(Xr)小于f(Xh)

则用Xr代替Xh转第六步

否则进行下一步

如果说f(Xr)大于f(Xh)

再令α等于α/2

直到α小于δ等于10的-5

仍不能使Xr优于它的时候

则我们要什么

用Xg替代Xh

返回第三步

终止准则

那么最后求复合形的形心

那么求它形心以后

如果说了两次Xj和Xc’最大的

这个东西小于ε

或者是这个东西小于ε的话

我们认为它就可以收敛

输出X*就等于Xl 如果不满足要求

则返回第二步

进行下一轮的迭代

产生初始复合形的方法

基本要求

初始复合形的k个顶点都必须是可行解

我们也给大家一些求解

构造初始复合形的一些方法

第一个全部顶点人为预先按照实际情况给定

当n比较小时候还是可行的

n较大的时候就不适合了

第二个人为的预先设定一个顶点

其余顶点用随机方法进行生成

在可行域内给定一个初始解

其余k-1个初始解

用随机数方法产生一个公式就出来了

xji等于ai加上伽马ji然后bi减ai

我先满足什么

边界约束

然后它是一个0到1区间的伪随机数

那么这是来产生这样的一个rj

那么这样产生的这样的一个随机的有一个是可行的

其他的我随机产生的这样的一个点

以后我们来调整它一下

显然按上述方法产生的顶点

必满足边界约束

aibi

但不一定满足约束gu(X)

小于等于0的条件

因此对每个顶点必须检测是否满足约束条件

如果满足则可作为复合形的顶点

否则按照以下的方法

我们来看怎么生成可行点

设X1X2Xq

q是大于1小于k的顶点

满足全部的约束条件

求这q个顶点的形心

X0等于1/q的X系列的一直到q∑求完

求完形心以后

然后让q+1到k 让k-q这些不满足约束的点

向这个形心去靠拢

得到新点

Xq+1等于什么呢

X0加上 βXq+1减去X0

这个 β 是我们的系数

一般我 β 取0.5

这是我们的X0

这是我的可行域

非可行域

这个点是不可行的

X0是可行的

X0是我们的q个顶点的形心

我让这个东西一步一步的往回拉

Xq减去X0

然后 β倍的一半往上去靠拢

因此说Xq’q+1等于0.5倍的Xq+1减上X0

移动一次以后

Xq+1还不满足

再取0.5

再往回拉

直到满足为止

讨论第一个

如果说可行域是凸集的话

X0点必为可行点

用上面的方法可成功的在可行域内产生初始形

什么是凸集

集合内找两点

两点连线

一定全部在集合内的

等于凸集

我们如果说这样的情况

这是我们找到前面的几个可行解

可行解找它的形心

然后不可行解

对这个形心往回拉

本来是在可行域之外的

拉回到可行域之内

如果说可行域是非凸集的话

X0点可能也在可行域之外

那么用上述方法则不会成功

我们看什么情况

这种情况

我在非凸集内

我的X1X2Xq这三个点是不是满足约束的

都是可行

对不对

但是有对这三个点的连形心可不一定是可行的

这个形心不一定可行的话

那你这样的话

它都不一定可行

它是榜样都不一定是可行的话

你对于外头的话的点对它进行映射

你在这照着它学习

你也不一定能满足要求

对不对

就像我们说的这个这表示考试的红线60分

本来你的榜样都是不及格的

你照你榜样去学

你怎么学你可能也学不及格

有这个问题

那怎么办

那你就要什么

应采用缩小边界约束ai bi的方法重新产生新顶点

那可能什么

你这三个点太松了

我把这个边界做的更苛刻一点

我让这个形心可能就落在了我这个里头

然后进行映射

进行一步步缩短

然后达到可行解

那么这样就能产生初始解

那么初始解产生完以后

下面几步那就一步步进行迭代了

每一步去迭代来进行计算了

就是复合型方法

实际上思想你看非常巧妙

就用了简单的找可行解

然后比较函数值大小

然后做映射

找到更好的点

步步迭代 步步下降

最终逼近你的最优解