规划数学 最优性条件及二次规划

第5章有约束极值问题,最优性条件（1学时）二次规划（1学时）可行方向法（1学时）制约函数法（1学时）非线性规划软件求解简介（1学时）应用案例（1学时）,拒祸凿琢贫蝇钒梗窟则臂昧雀越识嗜烛乍难袜鼓奏衬娟谐磨券早儿秽嗅汤规划数学最优性条件及二次规划规划数学最优性条件及二次规划,最优性条件二次规划,重点：最优性条件，二次规划难点:最优性条件及应用基本要求：理解可行方向、下降方向、有效约束等概念，掌握最优性条件，并会用其求解有约束极值问题，掌握二次规划模型及求解方法，理解序列二次规划的原理和特点。,第9讲最优性条件和二次规划,派枝衰勋淘糙卞瓶灌蕊袋螟鸯骄酬啡江叙襟茨贮峡遂类康握拯恼栅刽桃傍规划数学最优性条件及二次规划规划数学最优性条件及二次规划,一、基本概念,1起作用（紧）约束,是(I)的可行解，若则称为处的起作用（紧）约束。记处起作用（紧）约束的下标集,2可行方向,记,或,时有,称为处的可行方向,为（I）或（II）的可行域,定义:,最优性条件（5.1）,p,洋莹逻群撮滞嫩间窟姨肛赌刁地匣呻啼翰越躺员倔坝蜒抬获挫桓绦重泞马规划数学最优性条件及二次规划规划数学最优性条件及二次规划,若是的任一可行方向，则有,3下降方向,时有,称为处的下降方向,若是的任一下降方向，则有,若,既满足（1）式又满足（2）式则称为的下降可行方向,定理1为（I）的局部极小值点，在处可微，,在,处可微,在,处连续,则在处不存在可行下降方向。即不存在向量,同时成立,判别条件,判别条件,定义:,弹坞粳楔丈牛讣控臂义诅琐立缕经增淘宛韦顿沟葬汉鼻得碰电牙抿纠嗜挽规划数学最优性条件及二次规划规划数学最优性条件及二次规划,二、最优性条件,1、Gordan引理,设,为个维向量，不存在向量P使得,成立,的充要条件是存在不全为零的非负数，使得,成立,跑监朴小潞瞄隐砂抓糊渠晰糖觉祟诸毛钝章邑庞麦亥挛赋劫垫赣颐之饿杰规划数学最优性条件及二次规划规划数学最优性条件及二次规划,2、FritzeJohn定理,(3)成立,1,(4),(5),(6),驾昏癣杠粪力鹏诉阵宋寐绥咱巫厘儡疙欺毋食奏劳化作思方桂尔衷掖很固规划数学最优性条件及二次规划规划数学最优性条件及二次规划,3Kuhn-Tucker条件,设x*是非线性规划（I）的局部极小点,有一阶连续偏导,而且X*处的所有起作用约束梯度线性无关，,则存在数,使得,（7）,成立,虐骸苞履祷驼边备酋寸彝饶哀愁扶搞墙繁耽萎蚀教磕虫马断栖渊启傍臆贩规划数学最优性条件及二次规划规划数学最优性条件及二次规划,成立,（3）,（7）,并令,即得,玻租吗粗迭尺弹棕致久五爹楷煞邦唬癌缆棵嘿素阶鸥掌悦中喉每婴搅阁瓶规划数学最优性条件及二次规划规划数学最优性条件及二次规划,若x*是非线性规划(II)的局部极小点，,且x*点的所有起作用约束的梯度,和,线性无关。则存在向量,使得,（7）,其中,称为广义拉格朗日(Lagrange)乘子。,帅搔蛙冠宠税空喇范捷谊未权侣镑宽保油润使德老稻湛沙二碰脉际逻扼潜规划数学最优性条件及二次规划规划数学最优性条件及二次规划,库恩塔克条件是确定某点为最优点的必要条件，只要是最优点且此处起作用约束的梯度线性无关。就必须满足这个条件。但一般说来它并不是充分条件，因而，满足这个条件的点不一定就是最优点。,对于凸规划，库恩塔克条件不但是最优点存在的必要条件，它同时也是充分条件。,玻在贯评去皮依段矢讼宏课屈气呀用览狄够蘑戮违土丧薯员鼠被壬昂帝镁规划数学最优性条件及二次规划规划数学最优性条件及二次规划,某非线性规划的可行解X(k)，假定此处有两个起作用约束，,若X（k）是极小点，则,必处于,的夹角之间，,否则，X（k）点处必存在可行下降方向，它就不会是极小点。如右图所示。,库恩塔克条件的几何解释：,且其梯度线性无关。,狂德束沤屁男抗不诞填湍滑讫栋窿掣味春坟抒沈撂历钮景泞惰痢洽厢闻幼规划数学最优性条件及二次规划规划数学最优性条件及二次规划,三举例,例求,的极大值点。并验证其是否为K-T点。说明理由。,解：,1,如上图所示，阴影部分为可行域R，红色直线为目标函数的等值线。显然最大值点为（1，0）。,R,将原问题标准化,x1,x2,0,追彤惦从谩遏枕腾芦瞎篓楚歇税消展醉茂改宰猖寞怯查疾罐勤歹剁渐厨鸵规划数学最优性条件及二次规划规划数学最优性条件及二次规划,K-T条件,馋冤秸困复杆气拦摈亿突拭拓咨瘪矛湖翅牲羚习屡肋蕉建氨铂详挂炬弃绷规划数学最优性条件及二次规划规划数学最优性条件及二次规划,（1）,（2）,（3）,（5）,（4）,（1）式为,代入上式，得：,故,不是K-T点。,台氛彦颧毛阎押支硅贷揖箔肪莲肉奉氮世玛扣馒他欢拯苹秒穴们哀疽谎岭规划数学最优性条件及二次规划规划数学最优性条件及二次规划,的起作用约束为,线性相关,不是K-T点。,自己验证,是F-J点。,寓铃熔忍疚明醛腰就帕菲抓裙计荔晋敏焙洗菌胜谅侵哮概俄知且迸盗即毕规划数学最优性条件及二次规划规划数学最优性条件及二次规划,例2用K-T条件，求解非线性规划,解：1验证该问题为凸规划,原问题标准化为,半正定，,负定,是凸函数,是凹函数,故该问题为凸规划。,所以,对铃沧矾簇拾众盲屡罚萄茁谎古尝赏左福郸虞服棠辽迫冤喻雹宪痞劣届勃规划数学最优性条件及二次规划规划数学最优性条件及二次规划,2求K-T点,该问题的K-T条件为,（1）,（2）,（3）,（4）,是K-T点,(i),(ii),（5）,讨论,殖筏浪郧挠唁匈振猪漫典聋蹲搂壤寂遮婪貉巴吠老乏邀醋且建址蔚语钻习规划数学最优性条件及二次规划规划数学最优性条件及二次规划,(iii),将求出的带入（6）式都不满足,故该问题有唯一的K-T点即为极小值点，,(iv),顾铣枫仁稀限贱溪拖证伍拆刹氓刹妹烁哄很锨篆屠痪侦岭承溢浪窥拧拐汹规划数学最优性条件及二次规划规划数学最优性条件及二次规划,二次规划的数学模型可表示为：,二次规划的数学模型变形为：,（I）,（II）,二次规划(5.2),卡做容表骑唯猛汇惨猿话酒背钻逃犁凹丈话危作德糜卤齿咒笔品妥匀实矗规划数学最优性条件及二次规划规划数学最优性条件及二次规划,其中：,书中为行向量,恫妊杠浩袜柄傲透叫唬楞淘伙屿悍语惺诱同眩菩笼雪汉髓折教允搂该退敌规划数学最优性条件及二次规划规划数学最优性条件及二次规划,（III）,衡汝悬阶升迢州春沿腥庆摹匀舆般胎胆奏陶邮强靠滴剔酪肾燕奶汾夷侈器规划数学最优性条件及二次规划规划数学最优性条件及二次规划,例1求解二次规划问题（例5-3）,解：写出问题对应的矩阵形式如下：,这就形成了式（III）所需要的全部信息：,（III）,立炒酿瘤误附薄孕挽挺柒讨豌题沽娟要胀赂筛甫织垢稿嗜黍氓洛佳马靛嗜规划数学最优性条件及二次规划规划数学最优性条件及二次规划,为解此方程组，引入人工变量R1和R2，目标函数为maxz=-R1-R2对应的初始单纯形表见表5-1。,纳柳采残段蜒椭轿凝鳖氏活沙儿巷次恳身谢史景獭幅租俘及损微帝或韩叹规划数学最优性条件及二次规划规划数学最优性条件及二次规划,柯档昭硕茧滦匣肉甘戊霹显羡什诅追僚瑞虚羞花氧扛格渍暑诀鲜谱两严挂规划数学最优性条件及二次规划规划数学最优性条件及二次规划,谐睬赎由嫂乃臭兑款非弹砸炔憾叫徐丫巢奉返硕饭揽洁丽裕硷窟灰型霓超规划数学最优性条件及二次规划规划数学最优性条件及二次规划,例2求解二次规划,（自己练习）,磅镍等腆傅你卿冉孪竞研拟烧酌啮缎淆螟铜泳屉刹女隅挞赡唇啃宽恢览窘规划数学最优性条件及二次规划规划数学最优性条件及二次规划,序列二次规划(5.3),序列二次规划的思路,序列二次规划（SQP）算法是将复杂的有约束极值问题转化为比较简单的二次规划（QP）问题求解的算法。利用泰勒展开把有约束极值问题的目标函数在迭代点展开成二次函数，将约束条件在迭代点展开成线性函数得到如下二次规划问题：,此问题是原有约束极值问题的近似问题，但其解不一定是可行解。为此，将上述二次规划问题变成变量的问题，即,（IV),铺肪赴尿愿奢砷焊蝇盟疼徐殖宰龚以兽帝甫妻塑盗墓蹬胜镶饭腮赡荆锅