二阶锥规划的预估校正内点法
Predictor-corrector Interior-point Algorithm for Second-order Cone Programming
-
摘要: 研究二阶锥规划的预估校正内点法.该算法在预估步将中心路径的邻域放大两倍,使得沿着迭代方向可以让对偶间隙有一个较大的缩减,而在校正步采用修正的牛顿方向,使得校正步不仅将迭代点重置于一个更小的邻域,同时还对对偶间隙有一个常数因子的缩减.证明了算法只需迭代O(nln(x0Ts0/ε))次就可找到问题的ε-近似解Abstract: A predictor-corrector interior-point algorithm for second-order cone programming is proposed.The duality gap has a large reduction by enlarging the neighborhood of the central path twice in the predictor step.A modified Newton direction is applied in the corrector step,which makes the method not only replace the iterative points in a smaller neighborhood but also reduce the duality gap by a constant.It is proved that the ε-approximate solution can be obtained in O(nln(xT0s0/ε)) iterations.