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