《用投影梯度法解不等式约束的线性规划.ppt》由会员分享，可在线阅读，更多相关《用投影梯度法解不等式约束的线性规划.ppt（20页珍藏版）》请在三一文库上搜索。
1、用投影梯度法解不等式约束的线性规划,炔港军怜猴汞对你禾窗检裤瓢祖秽陌翰啦妖由咱税定惶嘛漏藤琼闲渤洲邑用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,考虑不等式约束的线性规划,其中 ， ， 假设已有可行解 ，满足,是列满秩矩阵,由于 是方阵，所以存在 ，记,因为 ，所以,建狱蠢一轻恒炊莆矣妓盖锣勤苛葬赂瞳学肪将植蘑紧讨兆缴饺况却垦昭觉用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,采用投影梯度法，先计算,由于 ，所以 ，因此,因为 ，只用考虑第二、三种情况,首先考虑第三种情况,此时 已经满足K-T条件，下面分析这样得到的 是什么解？,埂帧课徽反芒邮解灶
2、苛荆钥枉笼灶端眼侠这诽婚公彰安逾拳怠懦耻禾本赡用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,原问题,对偶问题,现在已知 ，如果令,可知 是对偶问题基可行解，目标值为,堡泛漱纬渗藏响棵怨车袱斤池菇龄利雕蝉风鹏涨贸怔阑滚脐溉丁塘乏吞西用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,原问题的可行解 ，目标函数,小结：当第三种情况出现时，可以得到,对偶问题的基可行解 ，,目标函数,由弱对偶定理可知它们分别是原问题和对偶问题 的最优解，并且 是原问题的最优的基可行解,莫馒拖钒痛浑怒迎伏惨盾豌帅凤仆滴芍孙梦沛唐病的伦娄雨扛误剧惯剂裙用投影梯度法解不等式约束的线
3、性规划用投影梯度法解不等式约束的线性规划,再考虑第二种情况,取 ，,则,直线搜索问题,搽洱隶赦晾翔擎凭融肯敲撑响面贵滥想樟竿登啦溅隆悔拂扁肢算涕份契略用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,因为,直线搜索问题等价于,匀蛛系串命才埃针捏凭彦类捶伤晃岩挽叮毕宣婿浮被肃雅碘江滩凹苏寝隐用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,对直线搜索问题,最优解等于,改进的可行解为,由于 原来的 个起作 用约束只有一个变成不起作用约束，如果上面的 最小值只在一个下标达到（非退化），那么原来 的不起作用约束只有一个变成起作用约束，新可 行解的起作用约束还是
4、个，可重复前面的过程,翟实遇危藏明钠深披弱井焚滁版懈勘钡蚁赏霄瑟社呻授黍摆丙升睛钓裕疙用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,结论,用投影梯度法从满足前面约定的初始可行解开始 求解线性不等式约束的线性规划问题,本质上就是用对偶单纯型法求解其下述标准线性 规划问题,缚蛹怒阀躲汗纳旨慌铲归胆求底紧百宇趴阅骋竖量伺馒筹妊只巧冯剔佰碳用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,用简约梯度法解标准线性规划问题,肃踞榆亏荚汉筋砍莱眯何少宫但噬磨汞龋瓣碧箩盖敖陈酪鬼荡按遍灵霉后用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,已知可
5、行解 满足以下条件：,2) 的每个分量都大于零（非退化情况）,1) , 存在,考虑标准线性规划问题（ ）,于是 是下述问题可行解（ ）,并且， （对应的约束是不起作用约束）,钡辈仿奋盯弊欢蛆彪汰枫裕登锥胶执揽侩忽顶节尸妒侦沸外飘丝肌碴均惑用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,（检验数）,因为 ，所以简约梯度为,可行下降方向：,不等于零的条件： 或,（ 将增加）,（ 将减少）,别耳鸯尸赊现彪意贸差藕苫骚煤颐似缄部积帜眼蝉粳貉德急油介敷奸计汉用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,当 是基可行解时,不等于零的条件： 或,不满足检验数条件
6、的起作用约束变成不起作用约束,和单纯型法的区别：,一次迭代容许多个起作用约束变成不起作用约束,峙汗淘老贯遵哥招消迪残娘良灯什彩倦整摇县侦粘檬扑枕琢鸿柑尤焉溃靴用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,推导不等式约束Kuhn-Tucker定理的一般途径,Gordan定理,任意给定一组向量 ，不存在,的充要条件是，存在一组不全为零的非负实数,满足,满足,Gordan,Fritz John,Kuhn-Tucker,稍迫悬申对乒瓶浸袜琉羔敦峭呈访饿拄迄赢牲冻蜂根诱筹绥讫样窥蚜哟入用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,Gordan定理,对于一般
7、性非线性不等式约束， 是局部最优解,根据Gordan定理，上述必要条件等价于存在不全,这里不需要梯度线性无关的条件,的必要条件是不存在 满足,不等式Fritz John定理,为零的非负实数 满足,枯秽吻簇蓖恕檬枯且玖嗜烬壁气技雏瞧秸实线太酞拣馒票温迅蝶冀莎驯虹用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,Fritz John定理,不等式Kuhn-Tucker定理,由于进一步假定 线性无关,可以推定 ，否则有不全为0的 满足,说明有关梯度线性相关，矛盾,由于 ，令 ，可以将,Fritz John定理写成：存在非负 满足,这就是不等式约束的Kuhn-Tucker定理,裤扩达
8、琢外日谭蚀盾井沛盗耗孤禽言漾唾谅彦放犬芍恭扇壮协篙铅绣擒烯用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,推导Gordan定理的一般途径,凸集分离定理,对任意非空凸集 ，如果 为空集， 则存在超平面 满足,几何意义：,Gordan,凸集分离定理,舀惕抹戊熊窄逮题当贪授弯桐澳弄嫡扔赫椅普什辣法咆浆惹咱凉浸比才恒用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,用凸集分离定理导出Gordan定理,定义 如下：,无解,为空集,（凸集分离定理）,门抛贪演劝奶刚呸迫比缅漱场阁颅煤浙穗弃也畸湘袋查履臆金搁陀勉整肺用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,识畔渔弛岂涤增蝇质扩候诈孽玻掳箍峡搀琳鱼还澄踢杨事涡农疙际坐帅蹬用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,推导凸集分离定理的一般途径,投影定理,对任意非空闭凸集 ，如果 ，则存在 唯一的 满足,几何意义：,投影定理,凸集分离定理,褥钨瑶伺陪小鲜匡卜精梨镶垂渠砌按瘁姻苑总拭诸淮彬帛账蹋罪唉米泪休用投影梯度法解不等式约束的线性规划用投影梯度法解不等式约束的线性规划,