惩罚函数法与广义乘子法.ppt

1、4.6 惩罚函数法与广义乘子法,4.6-1 惩罚函数法,约束最优化问题,基本是想,无约束最优化问题,利用问题的目标函数和约束函数构造新的目标函数罚函数（penalty function）,4.6-1 外惩罚函数法,考虑约束非线性最优化问题,。,(1),对于等式约束问题,最优解必使所有 都接近0。否则，罚函数 的第二项是很大的正数，与最优解取到极小值矛盾。,对于不等式约束问题,最优解必使所有 都接近0或小于0。否则，罚函数 的第二项是很大的正数，与最优解取到极小值矛盾。,一般的约束最优化问题,和 是满足下列条件的实值函数：,其中 是很大的正数， 是连续函数。,函数和 的典型取法:,其中 和 是给

2、定的常数，通常取作1或2。,转化求解法（一）：罚函数法,外罚函数法,Step1 选取初始数据。给定初始点 ，初始罚因子 ，放大系数 ， 允许误差 ，令 。,Step2 求解无约束问题，以 为初始点，求解无约束问题 ，设其最优解为 。,Step3 检查是否满足终止准则，若 ，则迭代终止， 为约束问题 的近似最优解；否则， 令 ，返回Step2。,转化求解法（一）：罚函数法,外罚函数法例题,转化求解法（一）：罚函数法,外罚函数法例题,转化求解法（一）：罚函数法,外罚函数法例题,转化求解法（一）：罚函数法,外罚函数法例题,4.6-2 内惩罚函数法,在迭代中总是从可行点出发，并保持在可行域内部进行搜索

3、。 因此，这种方法适用于只有不等式约束的最优化问题,基本是想,考虑约束非线性最优化问题,显然， 罚函数的作用对企图脱离可行域的点给予惩罚， 相当于在可行域的边界设置了障碍，不让迭代点穿越到可行域之外， 因此也称为障碍函数（barrier function）。,两种常用的形式,0,如果 太小，则会给问题的求解带来很大困难。,利用序列无约束极小化方法（SUMT）,内罚函数法,Step1 选取初始数据。给定初始点 ，初始参数 ，缩小系数 允许误差 ，令,Step2 求解无约束问题，以 为初始点，求解无约束问题 设其最优解为 。,Step3 检查是否满足终止准则，若 ，则迭代终止， 为约束问题 的近似

4、最优解；否则，令 返回Step2。,转化求解法（一）：罚函数法,转化求解法（一）：罚函数法,内罚函数法例题,转化求解法（一）：罚函数法,内罚函数法例题,转化求解法（一）：罚函数法,内罚函数法例题,4.6-3 增广乘子法,把罚函数与Lagrange函数结合起来，构造出更合适的新目标函数， 使得在罚因子适当大的情况下，借助于Lagrange乘子就能逐步达 到原约束问题的最优解。 由于这种方法要借助于Lagrange乘子的迭代进行求解 而又区别于经典的Lagrange乘子法，故称为广义乘子法。,基本是想,（一）、等式约束下的广义乘子法,等式约束的最优问题,其中,。该问题的Lagrange函数,罚项,

5、乘子项,乘子罚函数 （multiplier penalty function）,与外罚函数类似，若设,为单调递增的正数列,等式约束问题转化为求解一系列的无约束问题,（1）,（1）,终止准则：,等式约束下的增广乘子法,Step1 选取初始数据。给定初始点 ，初始乘子 ，初始罚因子 ，放 大系数 ，允许误差 ，参数 ，令 。,Step2 求解无约束问题，以 为初始点，求解无约束问题 ，设其最优解为 。,Step3 检查是否满足终止准则，若 ，则迭代终止， 为等式约束问题,转化求解法（二）：增广乘子法,的近似最优解；否则，转Step4。,Step4 判断收敛快慢。若 则令 转Step5，否则令 ，转

6、Step5;,Step5 进行乘子迭代。令 及 返回Step2。,转化求解法（二）：增广乘子法,转化求解法（二）：增广乘子法,等式约束下的增广乘子法例题,转化求解法（二）：增广乘子法,等式约束下的增广乘子法例题,转化求解法（二）：增广乘子法,等式约束下的增广乘子法例题,（二）、不等式约束下的增广乘子法,上述问题对应的广义乘子法中的乘子罚函数为：,当,时，,当,时，,极小。,不等式约束下的增广乘子法,Step1 引入附加变量 将问题 等价于等式约束问题,Step2 上述问题对应的广义乘子法中的乘子罚函数为：,Step3 对函数 关于 求极小，然后定义出于 无关的乘子罚函数 将不等式约束问题转化为求解一系列无约束问题。,具体计算步骤与等式约束的情形类似。,转化求解法（二）：增广乘子法,转化求解法（二）：增广乘子法,不等式约束下的