5.2 惩罚函数法在线视频

我们来讲解惩罚函数法

该方法也是在今后工程优化中

经常所用到的一种方法

它的基本思想

我们来看一看

根据约束函数的特点

构造惩罚项

加到目标函数中去

构成惩罚函数

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

来进行求解

那么故又称为序列无约束优化问题SUMT方法

因此说根据惩罚项的构造方法不同和形式不同

惩罚函数法又分为内罚函数法

外罚函数法和混合罚函数法

我们来一个一个来讲解一下

第一个

我们来看一下内罚函数法

我们又称为内点法

所谓内点法

我们说每一个迭代点都在可行域之内

引例minf(X)=x有一个约束条件

g(X)等于1-x小于零

是一个什么 一维的优化问题

显然X*等于1

f(X)等于1

画一个图

大家看更明显x f(X)

然后约束条件应该是X大于1

Y等于x嘛

一定是x等于1的时候取最小 构建内罚函数

我们做一个φ(X,rk)等于什么

x减去rk然后1减x/1

我把这一项-rk (1-x)/1

我们把它称为惩罚项

这是我们惩罚项 我们说称rk是罚因子

rk是大于零的

我们来分析一下

当x在可行域内的时候

gX等于1-x小于零

惩罚项是大于零的

当x越趋向于约束边界

1-x越趋向于零

它分之一是不是

变成无穷大了

要求问题极小化

所以说X不能越出约束边界

保证迭代过程始终在可行域之内

当rk趋向于零的时候

惩罚项趋向于零

那么xrk就是x*就是原函数的最优解

我们看那么x为内点按无约束优化问题来求极值

我们按解析法 偏φxrk对x求偏导

那么1-rk (1-x)的平方分之一

然后令它等于0

那我就有什么

X*等于1加上根号下rk

我做一个表格rk大于零

然后来取值不同的值

rk等于1 0.1

0.010.001一直到0

我x*rk 带进去就好了

rk取1的话1加根号1等于2

rk取0.1的话

1加根号下0.1算出来是1.316

然后你当rk等于0的话

x*就变成1了

我们看x*等于2的时候带进去

我的φx*rk是多少

应该是3

然后这是1.632

1.2到最后当rk取0的时候

原函数它的极值是1

刚好当rk取0的时候变回到原函数了

而且我们的x*就是我的极值点

我们来看一看

几何意义

这是我的目标函数

实际上我知道x取1的情况下这是极值点

我们说这个函数φxrkx-rk(1-x)/1

基本上是一个这样的一个形状

这个函数你可以描点画出来

对它的极值点

就是x*r0 2,3这个点

当rk取定后对φxrk的优化求解

就是x是变量r1取0.1的话还是x为变量

那么求它的极值呢

实际上这样一个图形

那么它的极值点是在这

它是1.316

然后1.632

那么rk再取

然后xr2再往里取

x取零的时候刚好就是我的极值点

这条红线就是我的传播路径

那么看一般形式minf(X)

s.t:gu(X)小于等于0 u等于1,2到m

然后我内罚函数

φxrk是f(X)减去rkΣgu(X)分之一

-rkΣu等于1到m

这是它的惩罚项rk是内罚因子是递减的

正数序列 r大于r0大于r1大于r2大于r3一直到rk

最后是大于零

limk趋向于无穷大rk是趋向于0的

有几个问题需要讨论一下

第一个如果gu(X)大于零的时候

罚函数中的负号改为正号不就行了吗

第二

X在可行域之内时gu(X)小于零惩罚项都为正

当X*到约束边界时候

gu(X)趋向于0惩罚项趋向于无穷大

惩罚项起作用

惩罚

能使函数猛增

保证迭代点不越出可行域

第三个

当k趋向于无穷大的时候

rk趋向于零

没有惩罚项了

所以说我的φx*rk就变成了f(X*)型

因为等式约束不存在可行域

所以说内罚函数法不能求解等式约束问题

我们来看一下框图

输入内点X0 r0 c ε

c等于0.1到0.02

然后k等于0

min

φxrk

得到X*

rk我可以来判断我的X*rk和X0是不是小于

ε

然后调用无约束优化的方程来进行求解

如果是的话

我们就输出X*

等于X*rkf(X*)就结束了

如果不是的话

我令什么X0等于

X*rk rk+1等于crk

然后进行求解

这是我们的内罚函数方法的一个框图

那么内罚函数法在实际中应用中注意几个问题

第一个初始点X0选取利用原来的设计方案

作为初始解

第二随机的产生一个初始解

然后进行迭代

第三采用搜索方法产生

如果说我初始解已经构成

那么这个解可能会满足某一些约束

假如说X0满足S个约束的话

那么剩下m-s个约束不满足情况下怎么办

你就要进行修正

然后让剩下的m-s个不满足约束也还满足约束

就可以了

变成了构造一个可行的初始解

怎么构造

我们来看一下

构造X0让gu(X)小于等于0是一到S个是满足的

而s+1到m个是不满足变成了g(X0)是大于零

这时候怎么办呢

在m-s个约束中选一个违反约束最严重的一个

就说gk是这里边最大那个将gk(X)作为目标函数

求X使得什么

min gk(X )gu(X)小于等于0

gu(X)减gk(X)

小于等于0

目的是不破坏已满足约束的条件

保证gu(X)小于等于gk(X）u是x=1到m

可利用函数自身的惩罚函数

求出上述问题的极值点

在求的过程中

一旦gk(X)小于零

则可以停止迭代了

得到一个新点

至少多满足约束条件

依次这样进行

则可以使所有的约束条件都满足为止

初始罚因子r0的选取

实践经验表明

r0选择对计算效率的影响甚大

需要一定的技巧和经验

如果r0选的过小

惩罚项所起的作用

很小 迭代点

有跑出可行域的危险

如果r你选择过大

惩罚项值非常大

那么会增加无约束优化问题的迭代次数

使计算效率降低

我们一般r0可以取1到50

一般r0取1

一般使惩罚项起作用与目标函数的作用是相当的

那就是什么

那就r0我可以让f(X0)和Σ这样的惩罚项它的摩

它两个基本上是匹配的

就是让我的惩罚项

和我的目标函数两者之间是对等的

内罚函数的特点

第一内罚函数定义在可行域内

求解过程在可行域内进行

因此说所得到的解总是可行解

第二

它只能求解不等式约束

不能求解等式约束问题

第三

初始点必须是可行解

造成了一定的困难

使求解的一开始就形成了一些不方便

那么基于这三个问题

我们构造了外罚函数法或称为是外点法

迭代点在可行域之外

同样我们通过一个例子来看一看外罚函数法的

计算过程

还是刚才那个例子

minf(X)等于x

s.t:g(X)等于1-x小于等于0

显然它的极值点是X*等于1

f(X*)是等于1

画图来看一下

是这么一个过程

x*和f(X*)

那我们这里边要建立外罚函数

φXMk x加上Mkmax

1-x和0比较

然后的平方

这一项我们称它为惩罚项

讨论一下

第一个

如果说1-x小于0

迭代点在可行域内

惩罚项等于0

满足于条件不受惩罚

外罚函数与目标函数是相同的

第二

当1-x大于0的时候

则迭代点在可行域之外

惩罚项是大于零的

不满足约束条件

受惩罚 x距离约束边界愈远

惩罚项愈大即惩罚作用愈明显

那么设x为外点

则惩罚函数为φXMk就变成了什么

x加上Mk(1-x)的平方对于每个Mk求它的极值

对于每给定一个Mk这个φXMk的极值就是

X*Mk等于1-2M分之一

那就这样子

我每一个Mk都会有一个极值

有一个φXMk Mk取1/4

那么1/4带进去Mk是-1

然后带进去是等于0 -1,0,1/2,3/4

当Mk等于无穷大时候

把X*就从什么

约束可行域之外

随着Mk的增加

逐步的拉到可行域的边界上

最终找到那个极值点就是外罚函数法

做一个图看一看

这是我的f(X)这是我的极值点

Mk等于1/4的时候是一个二次函数

它的极值点是哪

在-1这个点

然后φXMk等于0

因此说当Mk取定

对于φXMk优化求解X就是变量

好了Mk如果取1/2那就这样的一个曲线

实际上是X*是取零

φ是取1/2

如此这样子的话再往里边取

是取到了1/2,3/4

每次取点从这一点开始

逐步地拉回到我的约束面上

最终取到1，1这个点

那么外罚函数的一般形式

我们说minf(X)

s.t:gu(X)小于等于0

Hv(X)是等于0的

那么我的外罚函数

是φXMk,f(X)+MkΣ求和

我让不等式约束与0作比较

然后取max

平方

等式约束就是说取它平方

那么这一块就是惩罚项

Mk我们称为是外罚因子是递增的正数序列

M0小于M1一直小于Mk,Mk+1

到最后的话

当K取向无穷大的时候

我M可以收敛到无穷大

我们讨论一下

第一个

如果说guX大于等于0

我们的约束条件是大于零的话

我们就把这里边的max改成min

第二个当X满足所有的约束条件

即在可行域内和等式约束线或约束面上的时候

无论MK取何值惩罚项都是等于0的

即满足约束不受惩罚对惩罚函数的求解

即对原函数问题的求解

第三

如果是不满足约束

在可行域之外

那么这时候惩罚项是大于零

惩罚项起作用

即不满足约束受惩罚

X离约束边界越远

那么惩罚项值越大及惩罚作用越明显

我们看罚因子序列

Mk我们是Mk+1取c倍的Mk递增序列的话

那么c一般取5到10

一般取8M0取1开始

那么罚因子Mk的选取对计算的稳定性有明显的影响

Mk取太大了

惩罚函数病态严重

数值解困难可能导致寻优失败

如果Mk的变化太缓慢的话

惩罚作用不太起作用

那么迭代次数就会变太多

但是有可能你的寻优成功率可能会提升

因此说那么应通过程序调试试算取得

理论上k趋向于无穷大

X*Mk等于X*

实际上Mk不可能取到无穷大

因此要确定收敛准则

那么收敛准则计算Q1等于max

u等于1到m gu(X*）Mk

Q2等于max，v等于1到p,hv然后绝对值

然后我取这两个里面最大的那个

如果说q小于等于10的-3到10的-4次方的时候

我们认为X*Mk已经特别接近约束边界了

那么就停止

那么或者我们用惩罚因子控制量

R如果Mk并不是大于R则继续迭代

如果Mk大于R

及它俩相减小于ε2的话我们终止迭代

看一下它的框图

输入X0，M0，c,ε1,ε2,和R

c是递增的序列

我们c一般取5到10

或取5到8都可以

然后k等于0

构造罚函数求罚函数的极小值得到X*Mk

这一步就是要调用无约束优化问题

来进行求解

然后我们来判断

收敛条件 就是Q1Q2

max的guX和max的hvX然后呢取

最大这个值

如果说Q小于ε1了

则我就输出X*等于XMk,f(X*)

然后就END了

如果不是的话

我的Mk是不是大于我的这个R

如果不大于它

我们就继续做

如果满足的话再看一看

我的点距准则是不是小于ε2

如果小于呢就终止

如果不小于就继续迭代

这是我们的外罚函数法的迭代步骤和框图

外罚函数的特点

第一惩罚函数定义在可行域外

由非可行域外逐步去逼近最优解

故对初始点X0没有要求

可行不可行都可以

因此说计算方便

第二可解等式约束

也可以解不等式约束

第三个

最后所得到的最优解是非可行解

只能近似地满足约束条件

解决办法很简单

增加约束裕度

我让guX小于等于0

变成为guX小于一个Δ

Δ大于零

小于一个非常小的一个数

这是我的等值线

约束条件

本来我是要求的

X*这一点

那怎么办

我把我的裕度收缩一点

我让它收缩一个Δ

我的新问题变成这个约束面了

那好了

我从外向新约束面去求解的话

是不要求这一点了

这是我新的X*

一样的问题

我永远我可能也达不到你这个X*

我在原问题时候

已经落在这个原问题的可行域之内了

我就是可行解了

综合内罚和外罚函数的优点

克服它们之间的不足

人们提出混合罚函数法

那么对于混合罚函数法来说

一般形式那么它一定是能够满足

等式约束和不等式约束

那么我们的 φXrk呢，是f(X)-rk

内罚函数的基本形式加上rk分之一实际上是递增的一个hv

然后我们这里的罚因子rk是一个递减的正数序列

rkk趋向于无穷大的时候是趋向于零的

那么混合罚函数法还有一些其他形式

同学们有兴趣可以去参考相关的书籍

混合罚函数法的迭代过程与外罚函数相类似

且初始点不必在可行域内

并且可以解等式和不等式约束

我们看一道例子

利用外罚函数法来求解这个问题

minf(X)等于x1

加x2

s.t g1X等于x1平方减x2小于0

g2X等于负的x1小于0

第一个

构造外函数

x1加x2

这是我的目标函数

然后第一个约束和零比max取最大的平方

第二个约束和零比

max平方

我们让x为非可行解

它既然是非可行解的话

那么一定是x1平方减x2大于零

-x1是大于0

对吧

那就有 φXMk等于x1加x2加上Mk

这个的平方加上这个的平方

然后对它进行求解了

那么这里求解

我们说你可以用数值迭代方法求解

那么这里为了简单

我们用解析法求偏导来求就行了

偏 φ比偏x1 偏φ比偏x2

利用这两个偏导数等于0

就可以得到惩罚函数的最优解了

X*Mk等于x1Mk和x2Mk

x1和x2都带着Mk的等于2乘以1加Mk分之负一

4乘以1加Mk平方分之一减去2Mk分之一

所以说Mk从零开始不断的去增大

每给一个固定的Mk我能得到一个固定的x*

显然Mk增大XMk将逐步从可行域外

逼近约束边界

当Mk取最大的时候

XMk就是原问题的最优解

最后得到是x*就是0,0点

做一个图

我们看

x1x2这是我的g1X等于0

然后是不是外表抛出了

g2X是这条

然后把这边抛出来

X到底是取里头取外头怎么办

不能带0,0了

带个0，1进去

是不是看看到底是取这里头还取外头

你看这个可行域你要画出来图很简单

在这个可行域里边

你说我取哪个值能让

f(X)等于x1加x2最小

是不是只有取0,0点是最小的

就是可行域

这是我的等值线

这是我的X*

它的逼近路线是不是这样子的

逐步的从可行域之外去逼近我的可行域

那么这是我们讲的罚函数法

那么这里边我们对于约束优化问题来说

我们这里边讲了一个是直接法我们的复合形法

一个是间接法罚函数法

那么对于直接法我们看到了什么

构造复合形只是选择可行解

然后计算函数值比较函数值大小

计算下一个可行解

然后一步步迭代

那么对于间接法我们说的罚函数法

通过把我的这里面的约束条件通过构造惩罚项

加载到了你的目标函数里头

然后通过把约束优化问题变成了无约束优化问题

然后来进行求解

这是我们今天讲的求解约束优化问题的两类方法