约束条件极值1.doc

第三讲 非线性规划4约束极值问题(1)问题 思路:有约束无约束; 非线性线性; 复杂简;一、最优性条件1. 可行下降方向(有用约束,可行方向,下降方向)(1) 有用(效)约束设式的有一阶连续偏导设是一个可行解, 下一步考察时，要讨论约束.分析: 应有若,则在内,有,此时各个方向均可选.若, 则形成的边界, 影响下一步选向.故称是点的有效约束.(2) 可行方向(对可行域来说)设为可行点, 为某方向,若存在, 使得则称是点的一个可行方向.(a) 可行方向与有效约束的梯度关系是:.记有效约束下标集 若为的可行方向, 则存在, 使得当,有从而 见下图.(b)反之, 若, 则必为可行方向.对有效约束,只要充分小,得, 所以是可行方向;对无效约束,同样只要充分小, 就有,故也是可行方向;事实上, 对无效,都是可行方向.(3) 下降方向(对目标函数来说)设, 对某方向, 若在内, 有则称是一个下降方向.下降方向判定:若,则是的一个下降方向.因为,只要充分小, 都有.(4) 可行下降方向若的某方向是 可行方向+下降方向,则称是的可行下降方向.即 存在,当时,有且,是继续寻优方向.讨论: 非极小值点存在可行下降方向; 极小值点 无可行下降方向; (可行但不下降,或下降不可行)定理(局部极(最)小必要条件)设是局部极小点, (有效约束下标集)在处可微, 在处连续, 则在处无可行下降方向,即不存在, 使 (*)证 否则由(*)及前面的分析, 可找出可行下降点非局部极小值点矛盾.如图所示问题: 2. 库恩塔克条件(局部最小的必要条件)是非线性规划中最重要成果之一(1) Gordan引理(不加证明)设是个维向量, 则,使,不全为零, 使.(不指向同侧的向量, 正组合为零)(如l=3,n=2)若同侧, 则有P(图a), 否则无P(图b),但可正组为0.(2) Fritz John 定理设是极小值点, 和有一阶连续偏导数, 则存在不全为零的, 使证明 因是问题的解, 故由定理4, 不存在可行下降方向P, 使由Gordan引理,存在不全为零非负数使对无效约束, 令, 则从而有(对所有)且有 , 证毕.注1: 类似于条件极值的必要条件.注2 若,则有效约束的正线性相关同侧有可行下降方向非极值点. 故一般设线性无关.以上条件称为 Fritz John条件, 称为Fritz John点.(3) 必要条件 (库恩-塔克条件)设是极小值点, 和有一阶连续偏导,且有效约束梯度线性无关,则, 使证明 由Fritz John引理, 线性无关得, 作, 即得.式=库恩-塔克条件. 相应点=库恩-塔克点. 简称K-T条件, K-T点.对一般非线性规划 它的K-T条件如下设是极小值点, 相应函数有一阶连续偏导,且有效约束的和线性无关,则和, 使其中,称为广义Lagrange乘子.注1 对凸规划, K-T条件也是充分的.设为某可行解,若是极小点,且, 和,则必与,和同侧, 否则有可行下降方向.由和线性无关即例10 用库恩-塔克条件解非线性规划.解 变为 ,引入广义拉格朗日乘子, 则有所以, 具体分析如下.若引出矛盾, 无解;若:,点; (6)若:,;若:,(4)所以最大值点, 最大值.注: 非凸函数, 在上有两个局部最小值点.还有一个”驻点”附加例题(略)用K-T条件解非线性规划.解 ,(是凸规划),所以, 具体分析如下.若引出矛盾, 无解;若解得,非K-T点;若解得,非K-T点;若解得,全局最小.习题4.1 已