AN INFEASIBLE-INTERIOR-POINT PREDICTOR-CORRECTOR ALGORITHM FOR THE SECOND-ORDER CONE PROGRAM  

作　　者：迟晓妮 刘三阳 

机构地区：[1]Department of Mathematical Sciences, Xidian University

出　　处：《Acta Mathematica Scientia》2008年第3期551-559,共9页数学物理学报（B辑英文版）

基　　金：the National Science Foundation(60574075, 60674108)

摘　　要：A globally convergent infeasible-interior-point predictor-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 points and iteration points. Under suitable assumptions, it is shown that the algorithm can find an -approximate solution of an SOCP in at most O（√n ln（ε0/ε）） 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.A globally convergent infeasible-interior-point predictor-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 points and iteration points. Under suitable assumptions, it is shown that the algorithm can find an -approximate solution of an SOCP in at most O（√n ln（ε0/ε）） 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.

关 键 词：Second-order cone programming  infeasible-interior-point algorithm  predictor-corrector algorithm global convergence 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]