什么是KT点.pdf

《什么是KT点.pdf》由会员分享，可在线阅读，更多相关《什么是KT点.pdf（26页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1/26 第三讲 非线性规划 4 约束极值问题(1)问题 min(),|()0,1,jf XRX gXjl 思路:有约束无约束;非线性线性;复杂简;一、最优性条件 1.可行下降方向(有用约束,可行方向,下降方向)(1)有用(效)约束 设式的(),()jf XgX有一阶连续偏导 设(0)X是一个可行解,下一步考察时，要讨论约束.2/26 分析:应有(0)(0)(0)()0()0()0jjjgXgXgX 若(0)()0jgX,则在(0)()U X内,有()0jgX,此时各个方向均可选.若(0)()0jgX,则(0)X()0jgX 形成的边界,影响下一步选向.1x2x()0R X g X()f X(

2、)0jgX(0)X3/26 故称()0jgX 是(0)X点的有效约束.(2)可行方向(对可行域来说)设(0)X为可行点,P为某方向,若存在00,使得(0)0,0,XPR 则称P是(0)X点的一个可行方向.(a)可行方向P与有效约束(0)()0jg X的梯度(0)()jg X关系是:(0)()0Tjg XP.4/26 记有效约束下标集 (0)|()0,1jJj g Xjl 若P为(0)X的可行方向,则 存在00,使得当00,有(0)(0)()()0,jjgXPgXjJ 从而(0)(0)0d()()0,djTjgXPgXPjJ 见下图.5/26 (b)反之,若(0)()0TjgXP,则P必为可行方

3、向.(0)(0)(0)()()()()TjjjgXPgXgXPo(0)1()0gX(0)2()0gX(0)2()gX(0)1()gXP(0)X6/26 对有效约束(0)()0jgX,只要充分小,得(0)()0jgXP,所以P是可行方向;对无效约束(0)()0jgX,同样只要充分小,就有(0)()0jgXP,故P也是可行方向;事实上,对无效(0)()0jgX,P都是可行方向.(3)下降方向(对目标函数来说)设(0)XR,对某P方向,若在000,07/26 内,有(0)(0)()()f XPf X 则称P是一个下降方向.下降方向判定:若(0)()0Tf XP,则P是(0)X的一个下降方向.因为(0

4、)()()f Xf XP(0)(0)()()()Tf Xf XPo,只要充分小,都有(0)()()f Xf X.(4)可行下降方向 8/26 若(0)XR的某方向P是 可行方向+下降方向,则称P是(0)X的可行下降方向.即 存在00,当00,时,有(0)()0jgXP且(0)(0)()()f XPf X,是继续寻优方向.讨论:(0)X非极小值点存在可行下降方向P;(0)X极小值点 无可行下降方向P;(可行但不下降,或下降不可行)9/26 定理(局部极(最)小必要条件)设X是min(),()0if XXg X局部极小点,(),(),jf XgXjJ(有效约束下标集)在X处可微,(),jgXjJ在

5、X处连续,则在X处无可行下降方向P,即不存在P,使 10/26*()0,()0,TjTgXPjJf XP (*)证 否则由(*)及前面的分析,可找出可行下降点 X非局部极小值点矛盾.如图 所示 1x2x()f X()f X1()g X11/26 问题:min(),|()0,1,jf XRX gXjl 2.库恩塔克条件(局部最小的必要条件)是非线性规划中最重要成果之一(1)Gordan 引理(不加证明)设12,.,lA AA是l个n维向量,则 P,使0,1,2,.,TjA Pjl 0j,不全为零,使10ljjjA.12/26(不指向同侧的向量,正组合为零)(如 l=3,n=2)若同侧,则有 P(

6、图 a),否则无 P(图 b),但可正组为 0.(2)Fritz John 定理 设X是极小值点,()f X和()jgX有一阶连续偏导数,则存在不全为零的01,.,l,使 3A1A2APH()a3A1A2APH()b13/26 01()()0()0,1,2,.,0,1,2,.,ljjjjjjf XgXgXjljl 证明 因X是问题的解,故由定理 4,不存在 可行下降方向 P,使()0()0,TTjf XPgXPjJ 由 Gordan 引理,存在不全为零非负数0,jjJ 14/26 使 0()()0jjj Jf XgX 对无效约束jJ,令0j,则()0jjgX 从而有(对所有l)01()()0l

7、jjjf XgX 且有 ()0,0,1,2,.,jjjgXjl,证毕.注 1:类似于条件极值的必要条件.15/26 注 2 若00,则有效约束的()jg X正线性相关 同侧有可行下降方向X非极值点.故一般设()jgX线性无关00.以上条件称为 Fritz John 条件,*X称为 Fritz John点.(3)必要条件(库恩-塔克条件)设X是极小值点,()f X和()jgX有一阶连续偏导,且有效约束梯度线性无关,则1,.,l,使 16/26 1()()0()0,1,2,.,0,1,2,.,ljjjjjjf XgXgXjljl 证明 由 Fritz John 引理,()jgXjJ线性无关 得00

8、,作00/0j,即得.式=库恩-塔克条件.相应点=库恩-塔克点.简称 K-T 条件,K-T 点.对一般非线性规划 17/26 min(),()0,1,()0,1,ijf Xh XimgXjl min(),()0,()0,1,()0,1,iijf Xh Xh XimgXjl 它的 K-T 条件如下 设X是极小值点,相应函数有一阶连续偏导,且有效约束的()ih X和(),jgXjJ线性无关,则12(,.,)Tm和1(,.,)TlM,使 18/26 11()()()0()0,1,2,.,0,1,2,.,mliijjijjjjf Xh XgXgXjljl 其中12,.,m,1,.,l称为广义Lagra

9、nge乘子.注 1 对凸规划,K-T 条件也是充分的.设kX为某可行解,若kX是极小点,且1()0kgX,2xk()f X1()0kg X2()kgXk19/26 和2()0kgX,则()()kf X必与,1()kgX和2()kgX同侧,否则有可行下降方向.由1()kgX和2()kgX线性无关 1122()()()kkf XgXgX 即 1122()()()0kkf XgXgX ()kX()()kf X()1()0kg X2()gXR20/26 例 10 用库恩-塔克条件解非线性规划 2max()(4)16f xxx.解 变为 212min()(4)()10()60f xxgxxgxx,164

10、21/26 12()2(4),()1,()1f xxg xgx ,引入广义拉格朗日乘子12,则有 所以1212122(4)0(1)0(6)0,0 xxx,具体分析如下.若120,0,引出矛盾,无解;若120,0:1x,点;()9f x(16)22/26 若120,0:4x,()0f x;若120,0:6x,()4f x(24)所以最大值点1x,最大值()9f x.注:2()(4)f xx 非凸函数,在1,6上有两个局部最小值点.还有一个”驻点”附加例题(略)用 K-T 条件解非线性规划 16423/26 2min()(3)05f xxx.解 212min()(3),()0,()50f xxg xxgxx,(是凸规划)12()2(3),()1,()1f xxg xgx,24/26 所以1212122(3)00(5)0,0 xxx,具体分析如下.若120,0,引出矛盾,无解;若120,0,解得10,6x,非 K-T 点;若120,0,解得15,4x,非 K-T 点;若120,0,解得3x,()0f x全局最小.25/26 习题 4.1 已知非线性规划 131212max()(1)0,0f Xxxxx x 的极大点为(1,0),试(1)转化目标函数后,写出其 K-T 条件;(2)求出 K-T 点.4.2 试用 K-T 条件求解问题 26/26 2min()(4)16f Xxx.