用投影梯度法解不等式约束的线性规划市公开课获奖课件省名师优质课赛课一等奖课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,用投影梯度法解不等式约束线性规划,1/20,考虑不等式约束线性规划,其中 ，,假设已经有可行解 ，满足,是列满秩矩阵,因为 是方阵，所以存在 ，记,因为 ，所以,2/20,采取投影梯度法，先计算,因为 ，所以 ，所以,因为 ，只用考虑第二、三种情况,首先考虑第三种情况,此时 已经满足,K-T,条件，下面分析这么得到,是什么解？,3/20,原问题,对偶问题,现在已知 ，假如令,可知 是对偶问题基可行解，目标值为,4/20,原问题可行解 ，目标函数,小结：当第三种情况出现时，能够得到,对偶问题基可行解 ，,目标函数,由弱对偶定理可知它们分别是原问题和对偶问题,最优解，而且 是原问题最优基可行解,5/20,再考虑第二种情况,取 ，,则,直线搜索问题,6/20,因为,直线搜索问题等价于,7/20,对直线搜索问题,最优解等于,改进可行解为,因为 原来 个起作,用约束只有一个变成不起作用约束，假如上面,最小值只在一个下标到达（非退化），那么原来,不起作用约束只有一个变成起作用约束，新可,行解起作用约束还是 个，可重复前面过程,8/20,结论,用投影梯度法从满足前面约定初始可行解开始,求解线性不等式约束线性规划问题,本质上就是用对偶单纯型法求解其下述标准线性,规划问题,9/20,用,简约梯度法,解标准线性规划问题,10/20,已知可行解 满足以下条件：,2),每个分量都大于零（非退化情况）,1),存在,考虑标准线性规划问题（）,于是 是下述问题可行解（）,而且，（对应约束是不起作用约束）,11/20,（检验数）,因为 ，所以简约梯度为,可行下降方向：,不等于零条件：,或,（将增加）,（将降低）,12/20,当 是基可行解时,不等于零条件：,或,不满足检验数条件起作用约束变成不起作用约束,和单纯型法区分：,一次迭代允许多个,起作用约束变成不起作用约束,13/20,推导不等式约束,Kuhn-Tucker,定理普通路径,Gordan,定理,任意给定一组向量 ，不存在,充要条件是，存在一组不全为零非负实数,满足,满足,Gordan,Fritz John,Kuhn-Tucker,14/20,Gordan,定理,对于普通性非线性不等式约束，是局部最优解,依据,Gordan,定理，上述必要条件等价于存在不全,这里不需要梯度线性无关条件,必要条件是不存在 满足,不等式,Fritz John,定理,为零非负实数 满足,15/20,Fritz John,定理,不等式,Kuhn-Tucker,定理,因为深入假定 线性无关,能够推定 ，不然有不全为,0,满足,说明相关梯度线性相关，矛盾,因为 ，令 ，能够将,Fritz John,定理写成：存在非负 满足,这就是不等式约束,Kuhn-Tucker,定理,16/20,推导,Gordan,定理普通路径,凸集分离定理,对任意非空凸集 ，假如 为空集，,则存在超平面 满足,几何意义：,Gordan,凸集分离定理,17/20,用,凸集分离定理,导出,Gordan,定理,定义 以下：,无解,为空集,（凸集分离定理）,18/20,19/20,推导凸集分离定理普通路径,投影定理,对任意非空闭凸集 ，假如 ，则存在,唯一 满足,几何意义：,投影定理,凸集分离定理,20/20,