用投影梯度法解不等式约束的线性规划市公开课金奖市赛课一等奖课件_第1页
用投影梯度法解不等式约束的线性规划市公开课金奖市赛课一等奖课件_第2页
用投影梯度法解不等式约束的线性规划市公开课金奖市赛课一等奖课件_第3页
用投影梯度法解不等式约束的线性规划市公开课金奖市赛课一等奖课件_第4页
用投影梯度法解不等式约束的线性规划市公开课金奖市赛课一等奖课件_第5页
已阅读5页，还剩15页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

用投影梯度法解不等式约束线性规划第1页第1页考虑不等式约束线性规划其中，，假设已有可行解，满足是列满秩矩阵由于是方阵，因此存在，记由于，因此第2页第2页采用投影梯度法，先计算由于，因此，因此由于，只用考虑第二、三种情况首先考虑第三种情况此时已经满足K-T条件，下面分析这样得到是什么解？第3页第3页原问题对偶问题现在已知，假如令可知是对偶问题基可行解，目的值为第4页第4页原问题可行解，目的函数小结：当第三种情况出现时，能够得到对偶问题基可行解，目的函数由弱对偶定理可知它们分别是原问题和对偶问题最优解，并且是原问题最优基可行解第5页第5页再考虑第二种情况取，则直线搜索问题第6页第6页由于直线搜索问题等价于第7页第7页对直线搜索问题最优解等于改进可行解为由于本来个起作用约束只有一个变成不起作用约束，假如上面最小值只在一个下标达到（非退化），那么本来不起作用约束只有一个变成起作用约束，新可行解起作用约束还是个，可重复前面过程第8页第8页结论用投影梯度法从满足前面商定初始可行解开始求解线性不等式约束线性规划问题本质上就是用对偶单纯型法求解其下述原则线性规划问题第9页第9页用简约梯度法解原则线性规划问题第10页第10页已知可行解满足下列条件：2)每个分量都不小于零（非退化情况）1),存在考虑原则线性规划问题（）于是是下述问题可行解（）并且，（相应约束是不起作用约束）第11页第11页（检查数）由于，因此简约梯度为可行下降方向：不等于零条件：

或（将增长）（将减少）第12页第12页当是基可行解时不等于零条件：

或不满足检查数条件起作用约束变成不起作用约束和单纯型法区别：一次迭代允许多个起作用约束变成不起作用约束第13页第13页推导不等式约束Kuhn-Tucker定理普通路径Gordan定理任意给定一组向量，不存在充要条件是，存在一组不全为零非负实数满足满足GordanFritzJohnKuhn-Tucker第14页第14页Gordan定理对于普通性非线性不等式约束，是局部最优解依据Gordan定理，上述必要条件等价于存在不全这里不需要梯度线性无关条件必要条件是不存在满足不等式FritzJohn定理为零非负实数满足第15页第15页FritzJohn定理不等式Kuhn-Tucker定理由于进一步假定线性无关能够推定，不然有不全为0满足阐明相关梯度线性相关，矛盾由于，令，能够将FritzJohn定理写成：存在非负满足这就是不等式约束Kuhn-Tucker定理第16页第16页推导Gordan定理普通路径凸集分离定理对任意非空凸集，假如为空集，则存在超平面满足几何意义：Gordan凸集分离定理第17页第17页用凸集分离定理导出Gordan定理定义下列：无解为空集（凸集分离定理）第18页第18页第19页第19页推导凸集分离

人人文库> 全部分类> 办公材料 > 办公文档

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论