凸二次规划的有效集方法-

第六章二次规划quadraticprogram一．不等式约束的有效集方法二．二次规划的对偶性质三．二次规划的其他算法一．不等式约束二次规划的有效集方法1.基本思想对于存在不等式约束的二次规划，在每次的迭代中，以已知的可行点为起点，把在该点起作用的约束作为等式约束，将不起作用约束去掉，在此等式约束下极小化目标函数，求得新的比较好的可行点以后，重复以上做法.通过解一系列等式约束的二次规划来实现不等式约束的优化.称为有效集方法或者起作用集方法.一般二次规划标准形式1min(),2..,,,.TTTiiTiiqxxGxgxstaxbiEaxbiI(1)其中G是nn的对称矩阵.,EI分别对应等式约束和不等式约束指标集合.,,,igxandaiEI都是n维向量.等式约束二次规划问题标准形式1min(),2..,TTTqxxGxgxstAxb(2)其中,,,,nmnmnnnxRbRARgRGR且G是对称的，设()rankAm.求解方法：直接变量消去法；Lagrange乘子法.2．理论基础设x是二次规划问题(1)的局部极小点，并且在x处的有效集合为()wxEIx，则x也必是问题1min2..,TTTiixGxgxstaxbiEIx(3)的局部极小点.反之，如果x是(1)的可行点，且是问题(3)的K-T点，而且相应的Lagrange乘子满足0,iiIx(4)则x也是原问题(1)的K-T点.2．理论基础有效集方法的难点在于事先一般不知道有效集()wx.2．理论基础解决办法：构造一个集合序列去逼近有效集()wx，即从初始点出发，计算有效集0()wx，解对应的等式约束子问题，重复这一做法，得到有效集序列()0,1,kwxk，使得0()()wxwx，以获得原问题的最优解.3.算法推导有效集方法是一个可行点方法，即每个迭代点都要求是可行点，每次迭代求解一个等式约束的二次规划.如果等式约束二次规划的解是原约束问题的可行点，则判别相应的是否满足0,iIx，其中满足iiiEIxGxga.如果满足，则停止计算.否则，可去掉一约束重新求解约束问题.当等式二次规划之解不是原问题的可行点，则需要增加约束然后重新求解等式约束问题.在第k次迭代，有可行点kx以及工作集kw，其中kw是由所有的等式约束和有效不等式约束组成.设kp是问题1min,2..0,,TTkkkTikgxpxpGxpstapiw(5)的K-T点，ikkiw是相应的Lagrange乘子.如果0kp，则知kx是问题1min,2..0,,TTTikgxxGxstaxiw(6)的K-T点.如果此时0ik对一切kiwI都成立，则kx也是原问题（1）的最优解.否则令kkiwI,使得min0,kkkkiiikiwI.(7)且令1\kkkwwi，然后重新计算(5)式.设(5)式的解0kp，此时kkxp可能不是原问题（1）的可行点，此时在kx和kkxp之间的线段上取靠近kkxp最近的可行点取为下次迭代的迭代点1kx.1kkkkxxp(8)其中，0min1,minkTikiTiikkTiwkpbxp.(9)（5）式的简化计算令kxxp，则1()212TTkkkTTkqxgxpxpGxppGpqxpc这里12TTkkkcxGxgx为常数项，不影响最优解，从而可以去掉，得到1min,2..0,,TTkTikgppGpstapiw(10)4．有效集方法步骤Step1.计算可行的初始点0x，令00wEIx，:0k.Step2.解等式约束二次规划问题（10），求得kp；如果0kp，则转Step3；如果0kikiwI,则停止，得到解kxx；由（7）式求得ki；1:\,kkkkkwwixx，转Step4.Step3.由（9）计算k：1kkkkxxp；4．有效集方法步骤Step3.由（9）计算k：1kkkkxxp；如果1k，则转Step4.否则，找到kjw使得Tjkkkjaxpb；令:kkwwj.Step4.1:;:1kkwwkk.5.例题：221212121212min()(1)(2.5)..22026022000qxxxstxxxxxxxx1x1x2x（2，0）（4，1）（2，2）（0，1）0x4x2x3x5x记上面的约束为1到5，假设初始可行点为020x，易知有效约束为3和5，从而03,5w.求解（10）式，求得解为10p（此时1k）.Lagrange乘子的求解：AGxg,1201TA,2002G,25g,从而，可以推出35122022010205T,即是35102215，可推出35,2,1T.此时，由于约束的乘子32为最负的，从工作集0w中去掉其约束，得到15w.再解子问题(10).当1k的时候，110p，由(9)式可得11，从而产生新的迭代点21,0Tx.此时，由于没有回代约束215ww.再解子问题(10).20p，解Lagrange乘子，得到55，从而从工作集中去掉约束5，得到3w.第三次迭代是解无约束最优化问题，30,2.5Tp，由公式（9）得到30.6.此时新的迭代点为41,1.5Tx,有一个回代约束，为约束1，从而41w.说明：由k的定义,如果0TttkkTtkbaxap，则把指标t加到起作用约束集合当中.当4k时，（10）的解为40.4,0.2Tp，由公式（9）得到41.此时新的迭代点51.4,1.7Tx,无回代约束，51w.当5k时，（10）的解为50p，此时的11.25，最优解为51.4,1.7Txx迭代终止.二．二次规划问题的对偶性质对于一般二次规划问题(1),当G正半定时，等价于求解,nmxR，使得,,0,0,TiiTiiTiiigGxAaxbiEaxbiIaxbiIiI（11）成立，其中I为不等式约束指标集，11,,,mmAaa.记,TiiiyAgtaxbiI（12）则（11）式可写成110000emTmtbAxHyIt（13）从而等价于(证明略)11max,2..,0,.TTibyGyQystAygiI(14)称（14）为（1）的对偶问题，（1）式相应的称为原始问题.对偶问题的简化形式111min(),2..0,.TTTTibAGgAGAstiI(15)定理1设G正定，如果原始问题有可行点，则xX是（1）的解当且仅当存在,y是对偶问题之解且1xGy以及是原问题在x处的Lagrange乘子.原问题无可行点当且仅当对偶问题无界.三.二次规划的其他算法1．Lemke算法基本思想把线性规划的单纯形方法适当修改，再用来求二次规划的K-T点.2.对偶方法3.内点算法基本思想每个迭代点都是可行域内部点的算法.由Karmarkar提出的求解线性规划内点算法改进得到.自从1984年Karmarkar的著名算法—梯度投影算法(内点算法)发表以来,由其理论上的多项式收敛性及实际计算的有效性,使得内点算法成为近十几年来优化界研究的热点,通过中外学者的深入研究,线性规划与凸二次规划的内点算法研究已取得了不少成果.这些算法大致可分为四种类型:梯度投影算法;仿射尺度算法;路径跟踪法;势函数减少法.作业用有效集方法(积极集方法)求解下列二次规划问题：221122121212min()210..32600qxxxxxxxstxxxx初始可行点选为：T000x，。最优解为T1924，