10罚函数法.doc

第十章 罚函数法与广义乘子法 本章主要内容：外罚函数法 内罚函数法 广义乘子法 教学目的及要求：了解外罚函数法、内罚函数法、广义乘子法。 教学重点：外罚函数法． 教学难点：广义乘子法． 教学方法：启发式． 教学手段：多媒体演示、演讲与板书相结合． 教学时间：3学时． 教学内容： §10.1 外罚函数法 考虑约束非线性最优化问题 （10.1.1） 其中都是定义在上的实值连续函数．记问题（10.1.1）的可行域为． 对于等式约束问题 （10.1.2） 定义罚函数 ， 其中参数是很大的正常数．这样，可将问题（10.1.2）转化为无约束问题 ． （10.1.3） 对于不等式约束问题 （10.1.4） 定义罚函数 ， 其中是很大的正数．这样，可将问题（10.1.4）转化为无约束问题 ． （10.1.5） 对于一般的约束最优化问题（10.1.1），定义罚函数 ， 其中是很大的正数，具有下列形式： ． 和是满足下列条件的实值连续函数： 函数和的典型取法为 ， ， 其中和是给定的常数，通常取作1或2． 这样，可将约束问题（10.1.1）转化为无约束问题 ， （10.1.6） 其中是很大的正数，是连续函数． 算法10-1（外罚函数法） Step1 选取初始数据．给定初始点，初始罚因子，放大系数，允许误差，令． Step2 求解无约束问题．以为初始点，求解无约束问题 ， （10.1.11） 设其最优解为． Step3 检查是否满足终止准则．若，则迭代终止，为约束问题（10.1.1）的近似最优解；否则，令，返回Step2． 例1 用外罚函数法在平面上求一点，使得到定点的距离近似最短，取． 解 令，问题可归为求解如下最优化问题 引入罚函数 ． 则原约束最优化问题相应的一系列无约束最优化问题为： ，其中． 解上述无约束问题，得， 同时． 依次对用上述公式计算和，结果如下表所示． 1 0.5 3.5 6.5306 2 1 6 4.4444 3 2 11 2.6446 4 4 21 1.4512 5 8 41 7.6145 6 16 81 3.9018 7 32 161 1.9752 8 64 321 9.9378 9 128 641 4.9844 10 256 1281 2.4961 11 512 2561 1.2490 12 1024 5121 6.2476 由迭代终止条件可得原约束问题的近似最优解（保留4位有效数字）． §10.2 内罚函数法 对于不等式约束问题（10.1.4），其可行域的内部 ． 为了保持迭代点始终含于，我们引入另一种罚函数 ， 其中是很小的正数，是上的非负实值连续函数，当点趋向可行域的边界时，． 显然，罚函数的作用是对企图脱离可行域的点给予惩罚，相当于在可行域的边界设置了障碍，不让迭代点穿越到可行域之外，因此也称为障碍函数． 的两种常用的形式为 ， 及 分别称为倒数障碍函数和对数障碍函数． 算法10-2（内罚函数法或SUMT内点法） Step1 选取初始数据．给定初始内点，初始参数，缩小系数，允许误差，令． Step2 求解无约束问题．以为初始点，求解无约束问题 （10.2.2） 设其最优解为． Step3 检查是否满足终止准则．若，则迭代终止，为约束问题（10.1.4）的近似最优解；否则，令，返回Step2． 算法10-3（求内罚函数法中初始内点的算法） Step1 选取初始数据．给定初始点，初始参数，缩小系数，令． Step2 确定指标集．令 ，． Step3 检验是否满足终止准则．若，则，迭代终止；否则，转Step4． Step4 求解无约束问题．以为初始点，求无约束问题的最优解，其中 ， ． 令，返回Step2． §10.3 广义乘子法 考虑只带等式约束的最优化问题（10.1.2）．不难知道，问题（10.1.2）等价于问题 （10.3.1） 其中．该问题的Lagrange函数 ， 由于中既有罚项，又有乘子项，故称为乘子罚函数． 与外罚函数类似，若设为严