《用投影梯度法解不等式约束的线性规划.ppt》由会员分享，可在线阅读，更多相关《用投影梯度法解不等式约束的线性规划.ppt（20页珍藏版）》请在三一办公上搜索。
1、用投影梯度法解不等式约束的线性规划,考虑不等式约束的线性规划,其中，假设已有可行解，满足,是列满秩矩阵,由于 是方阵，所以存在，记,因为，所以,采用投影梯度法，先计算,由于，所以，因此,因为，只用考虑第二、三种情况,首先考虑第三种情况,此时 已经满足K-T条件，下面分析这样得到的是什么解？,原问题,对偶问题,现在已知，如果令,可知 是对偶问题基可行解，目标值为,原问题的可行解，目标函数,小结：当第三种情况出现时，可以得到,对偶问题的基可行解，,目标函数,由弱对偶定理可知它们分别是原问题和对偶问题的最优解，并且 是原问题的最优的基可行解,再考虑第二种情况,取，,则,直线搜索问题,因为,直线搜索问
2、题等价于,对直线搜索问题,最优解等于,改进的可行解为,由于 原来的 个起作用约束只有一个变成不起作用约束，如果上面的最小值只在一个下标达到（非退化），那么原来的不起作用约束只有一个变成起作用约束，新可行解的起作用约束还是 个，可重复前面的过程,结论,用投影梯度法从满足前面约定的初始可行解开始求解线性不等式约束的线性规划问题,本质上就是用对偶单纯型法求解其下述标准线性规划问题,用简约梯度法解标准线性规划问题,已知可行解 满足以下条件：,2)的每个分量都大于零（非退化情况）,1),存在,考虑标准线性规划问题（）,于是 是下述问题可行解（）,并且，（对应的约束是不起作用约束）,（检验数）,因为，所以
3、简约梯度为,可行下降方向：,不等于零的条件：或,（将增加）,（将减少）,当 是基可行解时,不等于零的条件：或,不满足检验数条件的起作用约束变成不起作用约束,和单纯型法的区别：,一次迭代容许多个起作用约束变成不起作用约束,推导不等式约束Kuhn-Tucker定理的一般途径,Gordan定理,任意给定一组向量，不存在,的充要条件是，存在一组不全为零的非负实数,满足,满足,Gordan,Fritz John,Kuhn-Tucker,Gordan定理,对于一般性非线性不等式约束，是局部最优解,根据Gordan定理，上述必要条件等价于存在不全,这里不需要梯度线性无关的条件,的必要条件是不存在 满足,不等
4、式Fritz John定理,为零的非负实数 满足,Fritz John定理,不等式Kuhn-Tucker定理,由于进一步假定 线性无关,可以推定，否则有不全为0的 满足,说明有关梯度线性相关，矛盾,由于，令，可以将,Fritz John定理写成：存在非负 满足,这就是不等式约束的Kuhn-Tucker定理,推导Gordan定理的一般途径,凸集分离定理,对任意非空凸集，如果 为空集，则存在超平面 满足,几何意义：,Gordan,凸集分离定理,用凸集分离定理导出Gordan定理,定义 如下：,无解,为空集,（凸集分离定理）,推导凸集分离定理的一般途径,投影定理,对任意非空闭凸集，如果，则存在唯一的 满足,几何意义：,投影定理,凸集分离定理,
