凸二次规划的原-对偶内点算法

凸二次规划的原-对偶内点算法西安交通大学理学院崔恒斌刘蓓刘玉英2011.04.28最优化理论与方法报告l1-magic凸二次规划及其对偶问题凸二次规划问题Lagrange函数：Karush-Kuhn-Tucher条件：为(P)的最优解1min()2().0TTxpxxQxcxPstAxbx1(,,)()2TTTTLxyzxQxcxyAxbzxx******00,00,0TTQxcAyzzxzAxby凸二次规划及其对偶问题根据Lagrange对偶原理：原凸二次规划对偶问题：假设：（i）集合（ii）集合,maxmin(,,)xyzLxyz,1max(,)2()..0,0,0TTyzTdyzxQxbyDstQxcAyzzAxbx|,0nSxRAxbx(,)|,0TTyzQxAyzcz凸二次规划及其对偶问题将对数障碍罚函数法扩展到凸二次规划中：其中，称为壁垒参数（或障碍因子）相应的KKT条件为：（原可行性）（对偶可行性）（互补松弛性）其中，，，记上述系统的解11minln2..,0nTTiiFxQxcxxstAxbx0,0,0TAxbxQxAyzczXZee12(,,,)nXdiagxxx12(,,,)nZdiagzzz(1,1,,1)Te,,xyzW凸二次规划及其对偶问题原问题与对偶问题的对偶间隙为：显然，当时，定理：()()()()Tpxdxxzn0()()0pxdx在假设条件(i)，(ii)下，上述系统的解，当时，、分别收敛到原问题（P）和对偶问题（D）的最优解。W0,yzx算法分析初始点和障碍因子必须满足如下条件：其中，，，障碍因子更新策略：000fe00000001122,,,Tnnfxzxzxz(1,1,,1)Te000Txzn11kkn算法具体步骤：Step1：选取初始点，且满足式，给定较小的正数；给定终止误差，置；Step2：计算对偶间隙，则停止迭代，为（P）的近似解；否则转Step3；Step3：令，计算Step4：，，转Step20000,,WxyzW,00kTkkxzkx11kkn,,kWxyz1kkk1kk注：kTkTkkkkkkkAxbAxQxAyzQxAyzcZxXzeZXe数值实验22221234123412324123411min7524922..135,,,0xxxxxxxxstxxxPxxxxxx22221234121112122313424123411min13522..75249,,,0xxxxyystxyzxyyxDxyzxyzzzzz考虑如下凸二次规划问题及其对偶问题：1000020000200001Q75249c11100101A135b初始点：000(6,4,11,1),(3,3),(2,3,1,13)TTTxyz参数：0.1,0.12,0.01数值实验02040608010012014016018066.056.16.156.26.256.36.35iterationstepx1thevalueofx1intheiteration02040608010012014016018044.14.24.34.44.54.64.74.84.95iterationstepx2thevalueofx2intheiteration0204060801001201401601801111.111.211.311.411.511.611.7iterationstepx3thevalueofx3intheiteration02040608010012014016018000.10.20.30.40.50.60.70.80.91iterationstepx4thevalueofx4intheiteration[6.33304.999511.66640.0005]T数值实验020406080100120140160180-169-168-167-166-165-164-163-162-161iterationstepFthevalueofFintheiteration迭代过程中目标函数的变化情况1989年，R.C.Monteiro和I.Adler给出了用原-对偶内点算法求解凸二次规划问题的一个版本，并证明了其复杂度为，其中迭代次数为。3()OnL()OnL主程序结论与展望原-对偶内点算法融合了对偶原理、Lagrange乘子法、内点罚函数法和Newton法，具有传统优化的特点，同时也大大扩大了内点算法的应用领域；原-对偶内点算法在解决线性规划、二次规划、半定规划、锥规划以及压缩传感、机器学习问题中起到了很好的作用；原-对偶内点算法在初始值的确定上，灵活度远大于一般的内点算法；对于原-对偶内点算法加速技术的研究，主要还是集中在如何快速的求解step3中的线性方程组上；原-对偶内点算法是一类具有广泛应用的算法，值得大家关注，并能在以后的学习和科研中加以运用；参考资料：AMathematicalViewofInterior-PointMethodsforConvexOptimization等。