Primal-dual Interior-point Algorithms for Second-order Cone Optimization Based on a New Parametric Kernel Function  

作　　者：Yan Qin BAI Guo Qiang WANG 

机构地区：[1]Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, P. R. China [2]College of Vocational Technology, Shanghai University of Engineering Science, Shanghai 200437, P. R. China

出　　处：《Acta Mathematica Sinica,English Series》2007年第11期2027-2042,共16页数学学报（英文版）

基　　金：Project sponsored by Shanghai Pujiang Program(Grant No.06PJ14039);Shanghai Educational Committee Foundation(Grant No.06NS031)

摘　　要：A class of polynomial primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function, with parameters p and q, is presented. Its growth term is between linear and quadratic. Some new tools for the analysis of the algorithms are proposed. The complexity bounds of O（√Nlog N log N/ε） for large-update methods and O（√Nlog N/ε） for smallupdate methods match the best known complexity bounds obtained for these methods. Numerical tests demonstrate the behavior of the algorithms for different results of the parameters p and q.A class of polynomial primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function, with parameters p and q, is presented. Its growth term is between linear and quadratic. Some new tools for the analysis of the algorithms are proposed. The complexity bounds of O（√Nlog N log N/ε） for large-update methods and O（√Nlog N/ε） for smallupdate methods match the best known complexity bounds obtained for these methods. Numerical tests demonstrate the behavior of the algorithms for different results of the parameters p and q.

关 键 词：second-order cone optimization linear optimization interior-point methods large- and small-update methods polynomial-time complexity 

分 类 号：O224[理学—运筹学与控制论]