北邮最优化课件13-惩罚函数法.ppt

《北邮最优化课件13-惩罚函数法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、帅天平北京邮电大学数学系§13，罚函数法最优化理论与算法2021/8/81最优化理论13惩罚函数法考虑约束问题（13.1.1）向量形式其中2021/8/82最优化理论13惩罚函数法如何求解约束问题？可行方向法：沿下降可行方向搜索其他方法？序列无约束优化算法：通过求解一系列无约束问题的解来近似约束问题的解。罚函数法是序列无约束问题算法的典型代表。2021/8/83最优化理论13.1外点惩罚函数法但由于F在可行域D的边界不连续.因此难以直接由求解F的极小值来求问题(13.1.1)的极小点.罚函数法的基本思想是构造辅助函数F,把原来的约束问

2、题转化为求极小化辅助函数的无约束问题易见约束问题(13.1.1)的解等价于的解例如可以定义函数F:RnR为2021/8/84最优化理论13.1外点罚函数法于是构造辅助函数极为重要！！！外点法的基本思想是构造辅助函数2021/8/85最优化理论13.1外点罚函数法（13.1.2）对于约束问题于是(13.1.2)转化为:可定义辅助函数:参数是很大的正数.2021/8/86最优化理论13.1外点罚函数法对于不等式约束问题(13.1.5)可定义辅助函数:参数是很大的正数.于是(13.1.2)转化为:2021/8/87最优化理论13.1外

3、点罚函数法对于一般形式的问题(13.1.1).可定义辅助函数其中P(x)具有如下形式:连续函数和满足2021/8/88最优化理论13.1外点罚函数法连续函数和的典型取法有于是把约束问题(13.1.1)转化为无约束问题其中是很大的正数,P(x)是连续函数2021/8/89最优化理论13.1外点罚函数法该问题的可行域D=-,-1],最优解x*=-12021/8/810最优化理论13.1外点罚函数法罚因子的选取非常重要!!!2021/8/811最优化理论13.1外点罚函数法2021/8/812最优化理论13.1外点罚函数法1.

4、3收敛性证明:先证12021/8/813最优化理论13.1外点罚函数法证2(13.1.14)（13.1.15）2021/8/814最优化理论13.1外点罚函数法将上两式的两端分别相加并整理得(13.1.16)(13.1.17)最后证3.:(13.1.18)2021/8/815最优化理论13.1外点罚函数法由(13.1.17)和(1.18)可得:2021/8/816最优化理论13.1外点罚函数法由(13.1.20)-(13.1.21)知(13.1.19)成立.2021/8/817最优化理论13.1外点罚函数法Th13.1.3设问题(13

5、.1.1)的可行域S非空,且,使得集合证明:根据假设,S是紧集,f(x)是连续函数,因此问题(13.1.1)存在2021/8/818最优化理论13.1外点罚函数法于是故可设:根据P(x)的定义,当xS,P(x)=0,当xS,时,P(x)>0.由引理13.1.1和1.2可知,2021/8/819最优化理论13.1外点罚函数法注意到(13.1.26),可以断言,对每个.存在正整数K(),使得当k>K()时有.由(13.1.16)可知2021/8/820最优化理论13.1外点罚函数法由(13.1.28)和(1.29)可

6、知2021/8/821最优化理论13.1外点罚函数法另一方面,由于f(x)连续,则又考虑到(13.1.24)和(13.1.30),则2021/8/822最优化理论13.1外点罚函数法于是由(13.1.25)得(13.1.33)2021/8/823最优化理论13.2内点罚函数法13.2.1基本思想(13.2.1)因此,此方法适用于下列不等式约束的问题:记可行域为内点法产生的点列从可行域的内部逼近问题的解2021/8/824最优化理论13.2内点罚函数法内点罚函数法的基本思想:构造辅助(光滑)函数2021/8/825最优化理论13.2内点

7、罚函数法保持迭代点含于可行域内部的方法是定义障碍函数其中B(x)是连续函数,当点x趋向可行域边界时,B(x).是很小的正数.这样,当x趋向边界时,函数F(x,)趋于无穷大;否则,由于很小,则函数F(x,)的取值近似f(x).因此可通过求解下列问题得到原问题的近似解:2021/8/826最优化理论13.2内点罚函数法两种最重要的形式:2021/8/827最优化理论13.2内点罚函数法2.2计算步骤2021/8/828最优化理论13.2内点罚函数法定义障碍函数例13.2.1用内点法求解下列问题用解析法求解问题2021/8/82

8、9最优化理论13.2内点罚函数法解得令2021/8/830最优化理论13.2内点罚函数法2.3.收敛性2021/8/831最优化理论13.2内点罚函数法设x*是问题(13.2.1)的最优解.又知(13.2.8)2021/