惩罚函数法与广义乘子法课件

4.6惩罚函数法与广义乘子法

4.6惩罚函数法与广义乘子法14.6-1惩罚函数法约束最优化问题

基本是想

无约束最优化问题

利用问题的目标函数和约束函数构造新的目标函数——罚函数（penaltyfunction）

4.6-1惩罚函数法约束最优化问题基本是想无约束最优24.6-1外惩罚函数法考虑约束非线性最优化问题其中，和都是定义在上的实值函数。记问题（1）的可行域为。(1)和约束函数及所构造的、具有“惩罚性质”的辅助函数

“惩罚性质”

要求当且仅当；而时，，并且随着到的距离的增大而增大。4.6-1外惩罚函数法考虑约束非线性最优化问题其中，和都3对于等式约束问题

最优解必使所有都接近0。否则，罚函数的第二项是很大的正数，与最优解取到极小值矛盾。对于不等式约束问题

最优解必使所有都接近0或小于0。否则，罚函数的第二项是很大的正数，与最优解取到极小值矛盾。对于等式约束问题最优解必使所有4一般的约束最优化问题

和是满足下列条件的实值函数：其中是很大的正数，是连续函数。一般的约束最优化问题和是满足下列条件的实值函数：5函数和的典型取法:

其中和是给定的常数，通常取作1或2。函数和的典型取法:其中和是给6转化求解法（一）：罚函数法外罚函数法

Step1

选取初始数据。给定初始点，初始罚因子，放大系数，允许误差，令。Step2

求解无约束问题，以为初始点，求解无约束问题，设其最优解为。Step3

检查是否满足终止准则，若，则迭代终止，为约束问题

的近似最优解；否则，

令，返回Step2。转化求解法（一）：罚函数法外罚函数法Step1选取初始7转化求解法（一）：罚函数法外罚函数法例题转化求解法（一）：罚函数法外罚函数法例题8转化求解法（一）：罚函数法外罚函数法例题转化求解法（一）：罚函数法外罚函数法例题9转化求解法（一）：罚函数法外罚函数法例题转化求解法（一）：罚函数法外罚函数法例题10转化求解法（一）：罚函数法外罚函数法例题转化求解法（一）：罚函数法外罚函数法例题114.6-2内惩罚函数法在迭代中总是从可行点出发，并保持在可行域内部进行搜索。因此，这种方法适用于只有不等式约束的最优化问题

基本是想

4.6-2内惩罚函数法在迭代中总是从可行点出发，并保持在12考虑约束非线性最优化问题显然，罚函数的作用对企图脱离可行域的点给予惩罚，相当于在可行域的边界设置了障碍，不让迭代点穿越到可行域之外，因此也称为障碍函数（barrierfunction）。对于不等式约束问题，其可行域的内部。为了保持迭代点始终含于,是很小的正数，是上的非负实值连续函数，当点趋向可行域的边界时，。考虑约束非线性最优化问题显然，罚函数的作用对企图13两种常用的形式

0

如果太小，则会给问题的求解带来很大困难。

利用序列无约束极小化方法（SUMT）

两种常用的形式0如果太小，则会给问题的求解带来很大14内罚函数法

Step1

选取初始数据。给定初始点，初始参数，缩小系数允许误差，令Step2

求解无约束问题，以为初始点，求解无约束问题设其最优解为。Step3

检查是否满足终止准则，若，则迭代终止，为约束问题

的近似最优解；否则，令

返回Step2。转化求解法（一）：罚函数法内罚函数法Step1选取初始数据。给定初始点15转化求解法（一）：罚函数法内罚函数法例题转化求解法（一）：罚函数法内罚函数法例题16转化求解法（一）：罚函数法内罚函数法例题转化求解法（一）：罚函数法内罚函数法例题17转化求解法（一）：罚函数法内罚函数法例题转化求解法（一）：罚函数法内罚函数法例题184.6-3增广乘子法把罚函数与Lagrange函数结合起来，构造出更合适的新目标函数，使得在罚因子适当大的情况下，借助于Lagrange乘子就能逐步达到原约束问题的最优解。由于这种方法要借助于Lagrange乘子的迭代进行求解而又区别于经典的Lagrange乘子法，故称为广义乘子法。

基本是想

4.6-3增广乘子法把罚函数与Lagrange函数结合起19（一）、等式约束下的广义乘子法等式约束的最优问题

其中。该问题的Lagrange函数罚项

乘子项

乘子罚函数（multiplierpenaltyfunction）

（一）、等式约束下的广义乘子法等式约束的最优问题其中。该问20与外罚函数类似，若设为单调递增的正数列

等式约束问题转化为求解一系列的无约束问题

其中

是第次迭代中采用的Lagrange乘子

（1）（1）与外罚函数类似，若设为单调递增的正数列等式约束问题转化为求21惩罚函数法与广义乘子法课件22终止准则：

与的选取问题：

最优解为时

终止准则：与的选取问题：最优解为时23等式约束下的增广乘子法

Step1

选取初始数据。给定初始点，初始乘子，初始罚因子，放大系数，允许误差，参数，令。Step2

求解无约束问题，以为初始点，求解无约束问题

，设其最优解为。Step3

检查是否满足终止准则，若，则迭代终止，为等式约束问题转化求解法（二）：增广乘子法的近似最优解；否则，转Step4。等式约束下的增广乘子法Step1选取初始数据。给定初始24

Step4

判断收敛快慢。若则令转Step5，否则令

，转Step5;Step5

进行乘子迭代。令及返回Step2。转化求解法（二）：增广乘子法Step4判断收敛快慢。若25转化求解法（二）：增广乘子法等式约束下的增广乘子法例题转化求解法（二）：增广乘子法等式约束下的增广乘子法例题26转化求解法（二）：增广乘子法等式约束下的增广乘子法例题转化求解法（二）：增广乘子法等式约束下的增广乘子法例题27转化求解法（二）：增广乘子法等式约束下的增广乘子法例题转化求解法（二）：增广乘子法等式约束下的增广乘子法例题28（二）、不等式约束下的增广乘子法上述问题对应的广义乘子法中的乘子罚函数为：

当时，当时，极小。（二）、不等式约束下的增广乘子法上述问题对应的广义乘子法中的29不等式约束下的增广乘子法

Step1引入附加变量将问题等价于等式约束问题Step2

上述问题对应的广义乘子法中的乘子罚函数为：

Step3

对函数关于求极小，然后定义出于无关的乘子罚函数

将不等式约束问题转化为求解一系列无约束问题。

具体计算步骤与等式约束的情形类似。转化求解法（二）：增广乘子法不等式约束下的增广乘子法Step1引入附加变量30转化求解法（二）：增广乘子法不等式约束下的增广乘子法例题转化求解法