非线性规划-KT条件

第 1 页 共 25 页第三讲 非线性规划§4 约束极值问题(1)问题 min(),{|0,1}jfXRgjl思路:有约束 无约束; 非线性线性; 复杂简;一、最优性条件1. 可行下降方向(有用约束,可行方向 ,下降方向)(1) 有用(效) 约束设式的 有一阶连续偏导),(jfXg设 是一个可行解, 下一步考察时，要讨论约束.(0)第 2 页 共 25 页分析: 应有(0)(0)jj gXgX若 ,(0)j则在 内,U有 ,()jg此时各个方向均可选.若 , (0)jX则 形成的边界, 影响下一步选向.j 1x2{|()0}jRXgfj第 3 页 共 25 页故称 是 点的有效约束.()0jgX()(2) 可行方向(对可行域来说 )设 为可行点, 为某方向,0)P若存在 , 使得(0) 0,[,]R则称 是 点的一个可行方向.(0)X(a) 可行方向 与有效约束 的梯度()jgX关系是:(0)jg.(0)TjP记有效约束下标集第 4 页 共 25 页(0){|,1}jJgXjl若 为 的可行方向, 则P(0)存在 , 使得当 ,有0[](0)()j jjJ从而 (0) (0)0d,j TjgXPgXPj见下图.第 5 页 共 25 页(b)反之, 若 , 则 必为可行方向.(0)TjgXP(0)(0)()Tj j jgXPoQ对有效约束 ,只要 充分小,得(0)1 (0)2gX()2g(0)1()第 6 页 共 25 页, 所以 是可行方向;(0)jgXP对无效约束 ,同样只要 充分小, (0)jg就有 ,故 也是可行方向;(0)j事实上, 对无效 , 都是可行方向.(0)j P(3) 下降方向(对目标函数来说)设 , 对某 方向, 若在0XR内, 有[](0)(0)fPfX第 7 页 共 25 页则称 是一个下降方向.P下降方向判定:若 ,则 是 的一个下降方向.(0)TfXP(0)X因为 (0)f,(0)()Tfo只要 充分小, 都有 .((4) 可行下降方向若 的某方向 是可行方向+下降方向,(0)XRP则称 是 的可行下降方向.()第 8 页 共 25 页即 存在 ,当 时,有00[]且 ,()jgXP()(0)fXPf是继续寻优方向.讨论: 非极小值点 存在可行下降方向 ;(0)极小值点 无可行下降方向 ;(可行但不下降 ,或下降不可行)第 9 页 共 25 页定理(局部极( 最) 小必要条件)设 是 局部极小点, Xmin(,{()0}ifXg(有效约束下标集 )在 处可,jfgJX微, 在 处连续, ()j则在 处无可行下降方向 ,即不存在 , 使P(**)*)0(,TjgXjJf证 否则由(**)及前面的分析, 可找出可行下降点 非局部极小值点 矛盾.第 10 页 共 25 页如图所示问题: min(),{|0,1}jfXRgjl2. 库恩—塔克条件(局部最小的必要条件 )是非线性规划中最重要成果之一(1) Gordan 引理(不加证明)设 是 个 维向量, 则12,.lAn1x2()fX()f第 11 页 共 25 页,使P0,12,.TjAjl,不全为零, 使 .j10ljA(不指向同侧的向量, 正组合为零 )(如 l=3,n=2)若同侧, 则有 P(图 a), 否则无 P(图 b),但可正组为 0.3A12H()a31A2H()b第 12 页 共 25 页(2) Fritz John 定理设 是 极小值点, 和 有一阶连续X()fX()jg偏导数, 则存在不全为零的 , 使01,.l0()(),2,.,1.ljjjfgXl证明 因 是问题的解, 故由定理 4, 不存在可行下降方向 P, 使第 13 页 共 25 页()0,TjfXPgjJ由 Gordan 引理 ,存在不全为零非负数使0,jJ()()0jjJfXgX对无效约束 , 令 , 则j ()j从而有(对所有 )l第 14 页 共 25 页01()()0ljjfXgX且有 , 证毕.,,2j jgl注 1: 类似于条件极值的必要条件 .注 2 若 ,则有效约束的 正线性相关0()jg同侧有可行下降方向 非极值点.X故一般设 线性无关 .()jg0以上条件称为 Fritz John 条件, 称为 Fritz John*点.第 15 页 共 25 页(3) 必要条件 (库恩-塔克条件)设 是 极小值点, 和 有一阶连续X()fX()jg偏导,且有效约束梯度线性无关,则 , 使1.l1()()00,2,.,.ljjjjfgXl证明 由 Fritz John 引理, 线性无关()jJ第 16 页 共 25 页得 , 作 , 即得.00/j式=库恩-塔克条件. 相应点= 库恩-塔克点. 简称 K-T 条件, K-T 点.对一般非线性规划min(),01jfXhigjlmin(),01,ijfXhigjl它的 K-T 条件如下设 是 极小值点, 相应函数有一阶连续偏导,第 17 页 共 25 页且有效约束的 和 线性无()ihX(),jgJ关,则 和 , 12,.Tm1.)TlM使11()()()00,2,.,.mli jjfhgXgXjl其中 , 称为广义 Lagrange 乘子.12m1.l注 1 对凸规划, K-T 条件也是充分的.第 18 页 共 25 页设 为某可行解,kX若 是极小点,且 , 1()0kg和 ,2则 必与,()kfX和 同侧, 否则有可行下降方向.1g2)k由 和 线性无关()k(g12)()kkf gX即1x2()kfX()f1()0kg2k第 19 页 共 25 页12()()()0kkfXggX例 10 用库恩-塔克条件解非线性规划.2max()4)16f1()gX()k()kf86()0k)20k2R164第 20 页 共 25 页解 变为 ,212min()4)06fxg,12()),(,()1fxgx引入广义拉格朗日乘子 , 则有所以 , 具体分析如下.12121(4)06,0x第 21 页 共 25 页若 引出矛盾, 无解;120,若 : ,点; ( 6)1x)9fx1若 : , ;12,4(0若 : , ( 4)06)f2所以最大值点 , 最大值 .1x9x注: 非凸函数 , 2()4)f在 上有两个局部最小值点.[1,6]还有一个”驻点”164第 22 页 共 25 页附加例题(略) 用 K-T 条件解非线性规划.2min()305fx解 ,(是凸规划 )212i(),fxg,12()3),(,(1fxgx第 23 页 共 25 页所以 , 具体分析如下.12121(3)005,x若 引出矛盾, 无解;2若 解得 ,非 K-T 点;10,10,6x若 解得 ,非 K-T 点;2,54若 解得 , 全局最小.1,3()f第 24 页 共 25 页习题4.1 已知非线性规划 1312max()0,fX的极大点为 , 试(0)(1) 转化目标函数后, 写出其 K-T 条件;(2) 求出 K-T 点..4.2 试用 K-T 条件求解问题第 25 页 共 25 页.2min()4)16fXx。