An infeasible-interior-point predictor-corrector algorithm for the second-order cone program

作者：Chi Xiaoni^*; Liu Sanyang

来源：Acta Mathematica Scientia, 2008, 28(3): 551-559.

• second-order cone programming
• infeasible-interior-point algorithm
• predictor-corrector algorithm
• global convergence

A globally convergent in feasible-interior-point predict or-corrector algorithm is presented for the second-order cone programming (SOCP) by using the Alizadeh-Haeberly-Overton (AHO) search direction. This algorithm does not require the feasibility of the initial paints and iteration points. Under suitable assumptions, it is shown that the algorithm can find an c-approximate solution of an SOCP in at most O(root n ln(epsilon(0)/epsilon)) iterations. The iteration-complexity bound of our algorithm is almost the same as the best known bound of feasible interior point algorithms for the SOCP.

• 出版日期2008-7
• 单位西安电子科技大学