《第四篇 最优化问题》由会员分享，可在线阅读，更多相关《第四篇 最优化问题（48页珍藏版）》请在金锄头文库上搜索。
1、第四篇：最优化问题(五)第13章 最优化问题的其它主题13.1非线性规划和库恩一塔克(Kuhn-Tucker)条件1. 仅存在非负约束的情况。问题：假设f可微s.t.气 0分析：最大值的位置可能有三种情况 若局部最大值出现在可行集内部，如下图(a)中的A点，则极大值 的一阶条件为：漩/、广(七)二0且七 0(2) 若局部最大值出现在纵轴上，如下图(b)中的B点，且一阶条件依 然有效，则有：dK /d气二广二0且七二0(3) 若局部最大值出现在纵轴上，如下图(c)中的C点或D点，且一 阶条件无效，则有：么/ dx = f3 ) v 且工=0总而言之，f在X1上取极大值，必须满足以下三个条件之一:
2、(1) 广(七)二0且七 0(2) 广(七)二0且七二0(3) f (X) 0 且七二0这三种情况综合起来等价于：f(X1) 0 且 xf X1)=0(13.5)(这个三个条件的共同特点是：x1和广(气)至少一个为零，这个特点 称为和广(气)互补松弛)(13.5)就是f整体极大化问题的必要条件(一阶条件)。推广：对有n个选择变量的可微目标函数最优值问题：Max 兀=f(X,X2，x)s.t. Xj 0( j = 1,2,3,., n)一阶条件为：f 0 且 Xf =0 (j = 1,2,3,n)(137).jjj j2. 不等式约束效应考察以下含有不等式约束条件的求最大值问题：Max 兀=f
3、(x , x , x )S.t. g 1(X , x , x ) r 1231g2(X ,x ,x ) 0 123引入两个虚拟变量S1和s2,可以将问题转化为st. gi(x ,x ,x ) + s = r12311g2(x ,x ,x ) + s = r12322且 X , X , X 0123Z = f (x , x , x ) + X r - g 1(x , x , x ) 一 s + X r - g 2(x , x , x ) 一 s 1231 112312 21232dZdZdZ dZdZdZdZ定义: = 0dxdxdxdsdsffkffk1231212由于和s.必须非负，故这些变
4、量的一阶条件必须修改得与(13,.7)(j = 1,2,3, , n) 一致f 0 且 x f =0jjj j故极值存在的一阶条件为:dZ且X =0j dxj(j = 1,2,3)dxj 0dZ且dZ 0s =0(i = 1,2)dsii dsiidZ,=0(i = 1,2)d人i(13.10)若令 Z = f (x ,x , x ) + X r - g 1(x , x , x ) + X r - g2(x , x , x ) 1 2 31 11 2 32 21 2 3则一阶条件等价于：dZdxj-f -(入 g 1 +入 g 2)V 0x. 0 且 x. Z =0jdZ人 0且人矣=0i(j
5、 - 1,2,3-r - gi (x , x , x ) 0dk i 1 2 3i(i - 1, 2)为什么？dZdsiI dZs 0 且 s =0 (i -1,2)ii dsi下面我们举例说明如何使用库恩一塔克条件求最优解。例1：求如下效用最大化问题的最优解。Max u - xyS.t. x + y 100x 0解：拉格朗日函数是Z = xy + X (100 - x - y) + X (40 - x)12库恩一塔克条件是：Z = y-X -X2 0,Z =x-X 0且灯=0y 0且yZ广0Z = 100-x-y 0,X1Z 侦40-x 0,采用试错法进行求解因为刑=0且yZ广0，贝 ij
6、x = 0 或 Z = 0 且 y = 0 或 Z = 0假设x = 0或y = 0,则U = xy = 0,非最优解。则Z = Z = 0，进而 y-X -X = x-X，即 y-X = xx y1212(1) 假设配额没有用尽，即x 。,进而由 X2 ZX2 =。可知：X 2 = 0进而，由y-X2 = x可知：y = x由x + y 100可知：y = x = 50，与x 40矛盾。即最优解并非出现 在此假设的情况中。(2) 假设配额用尽，即x = 40由 x + y 100 可知：y = 60进而由y-X2 = x得：X 2 = 20，X1 = 40，为最优解。n个变量，m个约束的情形
7、将库恩-塔克条件推广到n个变量，m个约束条件的问题，Max 兀=f (七，%,，% )s.t. gi(x ,%，,% ) r12 n 1g2(% ,%，% ) r12 n 2gm(% ,%，,% ) 012 n对应的拉格朗日函数为：Z = f (% , %，% ) + zi=1人r - gi(% , % ，,% )i i12n极小值问题的库恩一塔克条件为:dZ9%j=L 人 gj 0 且 . 9 =0(j = 1,2,., n)j9Z9Xi=r 一 gi(% , %，% ) 0i12 n9Z人 0 且人不=0(i = 1,2,., m)i推广：极小值问题的库恩一塔克条件(n个变量m个约束的情况
8、):问题：Min k = f (气,2,.,% )s【.g1(% , %，,% ) r12 n 1g2(% ,%，% ) r12 n 2gm(% ,%，,% ) r12 n m且 X , X，X 012 n对应的拉格朗日函数为：mZ = f (x , X ，,x ) + z 人r - gi(x , X ，,X )12 ni i12 ni=1极大值问题的库恩一塔克条件为:8Zdxj=l 人 g； 0i=1-dZx 0 且 x. _ =0(j = 1,2,., n)jdZBKir 一 gi(x , x ,., x ) 0 且人 _ =0(i = 1,2,., m)i举例2 (P498)：应用库恩一
9、塔克条件解决如下极小化问题Min c = (x1 - 4)2 + (x2 - 4)2s.t. 2x1 + 3x2 6-3x1 - 2x2 -12且气,% 0解：拉格朗日函数为：之=(犬1 4) + (%2 一 4)十如1 (6 - 2/1 32)+ A2(12 + 由 + 2股)根据库恩一塔克条件，边际条件为：，违反非负约束。2(xi - 4) 2m + 3A2 0|2(x 一 4) 一 3妇 + 2A2 0(13.18)6 2为 一 3x2 0-12 + 3罚 +22 0采用尝试法：QZ QZ 假设七0且气0，则由松弛条件可知：布=齐 =0 1212进而由(13.18 )最后两行可得：2xi
10、 + 3/2 = 63 犬1 + 2冷=12解得:假设十0且气=0，则由竺 0和竺 0可以求出气 4且% 412进而可得：竺= 12 + 3% + 2% 8，与竺0矛盾。 办12办22贝I有：人=0且人丰0 或人丰0且人=0(3) 假设人=0且人。0，(3.1) 若气=0 且 = 0则由(13.18)颦=0办2而生= -12 + 3尤+ 2x =-12 0则由与=0可得：%= 6 2进而由竺=0可得：气=4-x2 =-20的约束条件矛盾。2(3.3) 若气 0且= 0，则由竺=0可求出气=41进而，由竺=0可以求出七0，与前提气0矛盾。1(3.4 )若七0且0,则由则由竺=0和竺=0可以求出1
11、2满足所有条件(3)假设七丰0且气=0，与情况(3)一样讨论可知无满足所有条件的 解存在。为最终解。练习：P500练习13.1： 4、5 （交）13.2约束规范例 1（P501）:Max 兀=x 1s.t. X2 - （1-气）3 0其最优解为（1,0），但最优解并不满足库恩一塔克条件（为什么）。拉格朗日函数：Z =也+幻一了2 + （1 一扪）七第一个边际条件：竽=1 -公1（1 一所）三08Z 18Z18Z八在（1,0）点，有：反=1,故反气=1,不满足松弛条件亦气=0111也就是所，库恩一塔克条件并非一定是极值的必要条件，上面所 举的例子就说明了这一点。而违背能够产生最优解的库恩一塔克条
12、件 是由于可行集(满足约束条件的点集)边界上的某些不规则性(如教 材P501-503所介绍的歧点)。可以使用以下的约束规范来排除边界 上的不规则性。约束规范1. 测试向量定义令X* =(气*, x2*,., x *)是可行集边界上的一个点，并令dx = (dxdx2,., dx )表示从点x*移动的特定方向，如果满足以下两个 条件(1) 如果 * = 0，则 dx*0；(2) 如果 gi(x*) = r，贝i、崩,崩,崩估0 (对极大化问题) 版(x*) = gldx + g idx + g idx Kn日再、1 122 n n 0 (对极小化问题)(所有偏导数g；都在x*计算)则称dx为测试向量。2. 规范弧对测试向量dx，如果存在满足以下三个条件的可微弧(1) 从x*出发；(2) 整个包含在可行区域内；与测试向量相切则称这样的弧段为该测试向量的规范弧。3.
