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