第四篇最优化问题(五)讲述.doc

第四篇：最优化问题（五） 第13章 最优化问题的其它主题 13.1 非线性规划和库恩－塔克条件1.仅存在非负约束的情况。 问题： 假设f可微 Max s.t. (2) 若局部最大值出现在纵轴上，如下图(b)中的B点，且一阶条件依然有效，则有： (3) 若局部最大值出现在纵轴上，如下图(c)中的C点或D点，且一阶条件无效，则有： 总而言之，f在x1上取极大值，必须满足以下三个条件之一: (1) (2) (3) 这三种情况综合起来等价于： （13.5） （这个三个条件的共同特点是：和至少一个为零，这个特点称为和互补松弛） (13.5)就是f整体极大化问题的必要条件（一阶条件）。 推广：对有n个选择变量的可微目标函数最优值问题： Max s.t. 一阶条件为： （13.7） 2. 不等式约束效应 考察以下含有不等式约束条件的求最大值问题： Max s.t. 且 引入两个虚拟变量s1和s2，可以将问题转化为 Max s.t. 且 定义： 一致， 故极值存在的一阶条件为： (13.10) 若令 则一阶条件等价于： 为什么？ 下面我们举例说明如何使用库恩－塔克条件求最优解。 例1：求如下效用最大化问题的最优解。 Max s.t. 解：拉格朗日函数是 库恩－塔克条件是： ， 且 ， 且 , 且 , 且 采用试错法进行求解 因为且，则且 假设或，则，非最优解。 则，进而，即 (1) 假设配额没有用尽，即， 则有：，进而由可知： 进而，由可知： 由可知：，与矛盾。即最优解并非出现在此假设的情况中。 (2) 假设配额用尽，即 由可知： 进而由得：，，为最优解。 n个变量，m个约束的情形 将库恩-塔克条件推广到n个变量，m个约束条件的问题， Max s.t. ... 且 极小值问题的库恩－塔克条件为： 推广：极小值问题的库恩－塔克条件(n个变量m个约束的情况)： 问题： Min s.t. ... 且 极大值问题的库恩－塔克条件为： 举例2（P498）：应用库恩－塔克条件解决如下极小化问题 Min s.t. 且 ，则由松弛条件可知： 进而由(13.18)最后两行可得： 解得：，，违反非负约束。 (2) 假设，则由和可以求出且 进而可得：，与矛盾。 则有：或 (3) 假设， (3.1)若 则由(13.18) 而，与的前提矛盾。 (3.2) 若 则由可得： 进而由可得：，与的约束条件矛盾。 (3.3) 若， 则由可求出 进而，由可以求出，与前提矛盾。 (3.4 ) 若, 则由则由和可以求出 满足所有条件 (3) 假设，与情况(3)一样讨论可知无满足所有条件的解存在。 故 为最终解。 练习：P500练习13.1： 4