《用投影梯度法解不等式约束的线性规划.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定理,定义 如下：,无解,为空集,（凸集分离定理）,推导凸集分离定理的一般途径,投影定理,对任意非空闭凸集 ，如果 ，则存在 唯一的 满足,几何意义：,投影定理,凸集分离定理,