1、第 1 页 共 25 页第三讲 非线性规划4 约束极值问题(1)问题 min(),|0,1jfXRgjl思路:有约束 无约束; 非线性线性; 复杂简;一、最优性条件1. 可行下降方向(有用约束,可行方向 ,下降方向)(1) 有用(效) 约束设式的 有一阶连续偏导),(jfXg设 是一个可行解, 下一步考察时，要讨论约束.(0)第 2 页 共 25 页分析: 应有(0)(0)jj gXgX若 ,(0)j则在 内,U有 ,()jg此时各个方向均可选.若 , (0)jX则 形成的边界, 影响下一步选向.j 1x2|()0jRXgfj第 3 页 共 25 页故称 是 点的有效约束.()0jgX()(2
2、) 可行方向(对可行域来说 )设 为可行点, 为某方向,0)P若存在 , 使得(0) 0,R则称 是 点的一个可行方向.(0)X(a) 可行方向 与有效约束 的梯度()jgX关系是:(0)jg.(0)TjP记有效约束下标集第 4 页 共 25 页(0)|,1jJgXjl若 为 的可行方向, 则P(0)存在 , 使得当 ,有0(0)()j jjJ从而 (0) (0)0d,j TjgXPgXPj见下图.第 5 页 共 25 页(b)反之, 若 , 则 必为可行方向.(0)TjgXP(0)(0)()Tj j jgXPo对有效约束 ,只要 充分小,得(0)1 (0)2gX()2g(0)1()第 6 页
3、 共 25 页, 所以 是可行方向;(0)jgXP对无效约束 ,同样只要 充分小, (0)jg就有 ,故 也是可行方向;(0)j事实上, 对无效 , 都是可行方向.(0)j P(3) 下降方向(对目标函数来说)设 , 对某 方向, 若在0XR内, 有(0)(0)fPfX第 7 页 共 25 页则称 是一个下降方向.P下降方向判定:若 ,则 是 的一个下降方向.(0)TfXP(0)X因为 (0)f,(0)()Tfo只要 充分小, 都有 .(4) 可行下降方向若 的某方向 是 可行方向+下降方向,(0)XRP则称 是 的可行下降方向.()第 8 页 共 25 页即 存在 ,当 时,有00且 ,()
4、jgXP()(0)fXPf是继续寻优方向.讨论: 非极小值点 存在可行下降方向 ;(0)极小值点 无可行下降方向 ;(可行但不下降 ,或下降不可行)第 9 页 共 25 页定理(局部极( 最) 小必要条件)设 是 局部极小点, Xmin(,()0ifXg(有效约束下标集 )在 处可,jfgJX微, 在 处连续, ()j则在 处无可行下降方向 ,即不存在 , 使P(*)*)0(,TjgXjJf证 否则由(*)及前面的分析, 可找出可行下降点 非局部极小值点 矛盾.第 10 页 共 25 页如图所示问题: min(),|0,1jfXRgjl2. 库恩塔克条件(局部最小的必要条件 )是非线性规划中最重要成果之一(1) Gordan 引理(不加证明)设 是 个 维向量, 则12,.lAn1x2()fX()f
