用投影梯度法解不等式约束线性规划

1、用投影梯度法解不等式约束线性规划libXPXCiTiT1, s.t.min考虑不等式约束的线性规划考虑不等式约束的线性规划nPPPA,21A其中其中 ， ， 假设已有可行解假设已有可行解 ，满足，满足nRX nl linbXPnibXPiTiiTi1,1,Tnbbbb,21bXATbAXTX是列满秩矩阵是列满秩矩阵由于由于 是方阵，所以存在是方阵，所以存在 ，记，记1A因为因为 ，所以，所以 XfAAAWTT1采用投影梯度法，先计算采用投影梯度法，先计算由于由于 ，所以，所以 ，因此，因此 XCXfT CXfCACAAAWTT11因为因为 ，只用考虑第二、三种情况，只用考虑第二、三种情况 Xf

2、WA首先考虑第三种情况首先考虑第三种情况0W此时此时 已经满足已经满足K-T条件，下面分析这样得到的条件，下面分析这样得到的是什么解？是什么解？XlibXPXCiTiT1, s.t.minliyCyPybiliiiliii1, 0 s.t.max11原问题原问题对偶问题对偶问题现在已知现在已知 ，如果令，如果令01CAW可知可知 是对偶问题基可行解，目标值为是对偶问题基可行解，目标值为00WYYWbT原问题的可行解原问题的可行解 ，目标函数，目标函数bAXT小结：当第三种情况出现时，可以得到小结：当第三种情况出现时，可以得到对偶问题的基可行解对偶问题的基可行解 ，bACTT00WYCAW1目标

3、函数目标函数CAbT1由弱对偶定理可知它们分别是原问题和对偶问题由弱对偶定理可知它们分别是原问题和对偶问题的最优解，并且的最优解，并且 是原问题的最优的基可行解是原问题的最优的基可行解Y再考虑第二种情况再考虑第二种情况kPD 121,AAAPPPTn00 , 0 , 1 , 0 , 0TkkTTePADAnwwCAW110 kw取取 ，则则kkTTTTTweWDAACDC直线搜索问题直线搜索问题linbtDXPbtDXAwtXCtDXCiTiTkTT1, s.t.minlinbtDXPbtDXAwtXCtDXCiTiTkTT1, s.t.min因为因为linDtPbXPDtAbXAwtXCTi

4、iTiTTkT1, s.t.min0, 0DAbXAwTTk直线搜索问题等价于直线搜索问题等价于linDtPbXPtTiiTi1, s.t.maxlinDtPbXPtTiiTi1, s.t.max对直线搜索问题对直线搜索问题最优解等于最优解等于linDPDPbXPtTiTiiTi1, 0min改进的可行解为改进的可行解为DtXX由于由于 原来的原来的 个起作个起作用约束只有一个变成不起作用约束，如果上面的用约束只有一个变成不起作用约束，如果上面的最小值只在一个下标达到（非退化），那么原来最小值只在一个下标达到（非退化），那么原来的不起作用约束只有一个变成起作用约束，新可的不起作用约束只有一个变

5、成起作用约束，新可行解的起作用约束还是行解的起作用约束还是 个，可重复前面的过程个，可重复前面的过程kTTTe tbDAtXAXAnn结论结论用投影梯度法从满足前面约定的初始可行解开始用投影梯度法从满足前面约定的初始可行解开始求解线性不等式约束的线性规划问题求解线性不等式约束的线性规划问题libXPXCiTiT1, s.t.minliyCyPybiliiiliii1, 0 s.t.max11本质上就是用对偶单纯型法求解其下述标准线性本质上就是用对偶单纯型法求解其下述标准线性规划问题规划问题用用简约梯度法简约梯度法解标准线性规划问题解标准线性规划问题ZXY 已知可行解已知可行解 满足以下条件：满

6、足以下条件：2)2) 的每个分量都大于零（非退化情况）的每个分量都大于零（非退化情况）1BZ1) , 1) , 存在存在AXBZNYb0 s.t.minXbAXXCT考虑标准线性规划问题（考虑标准线性规划问题（ ）nmRA于是于是 是下述问题可行解（是下述问题可行解（ ）Y 1min s.t. 0,0f YBbNYY并且，并且， （对应的约束是不起作用约束）（对应的约束是不起作用约束）10BbNY1( )TTBNf YC BbNYC Y( )TTBNf YC ZC Yid（检验数）（检验数） 1 ,TTn mTTBNrf Z Yf Z Yf YN BZYrN B CC 因为因为 ，所以简约梯度

7、为，所以简约梯度为1if 0,if 0Tiin mii iirrDdddy rr可行下降方向：可行下降方向： 不等于零的条件：不等于零的条件： 或或1( )miiif Yr y0ir 0 and0iiyriy（ 将增加）将增加）iy（ 将减少）将减少）ZXY 当当 是基可行解时是基可行解时0Y id 不等于零的条件：不等于零的条件： 或或0ir 0 and0iiyr0ir 不满足检验数条件的起作用约束变成不起作用约束不满足检验数条件的起作用约束变成不起作用约束和单纯型法的区别：和单纯型法的区别：一次迭代容许多个起作用约束变成不起作用约束一次迭代容许多个起作用约束变成不起作用约束推导不等式约束推

8、导不等式约束Kuhn-Tucker定理的一般途径定理的一般途径Gordan定理定理任意给定一组向量任意给定一组向量 ，不存在，不存在的充要条件是，存在一组不全为零的非负实数的充要条件是，存在一组不全为零的非负实数kiRCni, 2 , 1,满足满足nRDkiDCTi, 2 , 1, 0kiwi, 2 , 1,满足满足01kiiiCwGordanFritz JohnKuhn-TuckerGordan定理定理对于一般性非线性不等式约束，对于一般性非线性不等式约束， 是局部最优解是局部最优解根据根据Gordan定理，上述必要条件等价于存在不全定理，上述必要条件等价于存在不全这里不需要梯度线性无关的条

9、件这里不需要梯度线性无关的条件nRDX的必要条件是不存在的必要条件是不存在 满足满足不等式不等式Fritz John定理定理liDXgDXfiTT1, 0)(, 0)(为零的非负实数为零的非负实数 满足满足0)()(10liiiXgwXfwliwi, 2 , 1 , 0,Fritz John定理定理不等式不等式Kuhn-Tucker定理定理0)()(1liiiXgwXf由于进一步假定由于进一步假定 线性无关线性无关liXgi, 2 , 1),(可以推定可以推定 ，否则有不全为，否则有不全为0的的 满足满足00w说明有关梯度线性相关，矛盾说明有关梯度线性相关，矛盾0)(1liiiXgwiw由于由

10、于 ，令，令 ，可以将，可以将liwwwii1,000wFritz John定理写成：存在非负定理写成：存在非负 满足满足liwi1,这就是不等式约束的这就是不等式约束的Kuhn-Tucker定理定理推导推导Gordan定理的一般途径定理的一般途径凸集分离定理凸集分离定理对任意非空凸集对任意非空凸集 ，如果，如果 为空集，为空集，则存在超平面则存在超平面 满足满足几何意义：几何意义：12,kR kTHZR W Zb12,TTW ZbZW ZbZ Gordan凸集分离定理凸集分离定理21H12用用凸集分离定理凸集分离定理导出导出Gordan定理定理定义定义 如下：如下：12,1,2, ,0kTniikiZR zC D ik DRZR z 12,kR 无解无解kiDCTi, 2 , 1, 012为空集为空集12,TTW ZbZW ZbZ （凸集分离定理）（凸集分离定理）11,0,1,2,kkTiiiiiiniwC Dw zDRzik11,0,1,2,kkTiiiiiiniwC Dw zDRzik10,0,1,2,kiiiiw zzik0,1,2,iwik 10,kTni