Path-following interior point algorithms for the Cartesian P_*(κ)-LCP over symmetric cones  

作　　者：LUO ZiYan XIU NaiHua 

机构地区：[1]Department of Applied Mathematics,Beijing Jiaotong University,Beijing 100044,China

出　　处：《Science China Mathematics》2009年第8期1769-1784,共16页中国科学：数学（英文版）

基　　金：supported by National Natural Science Foundation of China (Grant Nos. 10671010, 70841008)

摘　　要：In this paper, we establish a theoretical framework of path-following interior point al- gorithms for the linear complementarity problems over symmetric cones (SCLCP) with the Cartesian P*(κ)-property, a weaker condition than the monotonicity. Based on the Nesterov-Todd, xy and yx directions employed as commutative search directions for semidefinite programming, we extend the variants of the short-, semilong-, and long-step path-following algorithms for symmetric conic linear programming proposed by Schmieta and Alizadeh to the Cartesian P*(κ)-SCLCP, and particularly show the global convergence and the iteration complexities of the proposed algorithms.In this paper, we establish a theoretical framework of path-following interior point algorithms for the linear complementarity problems over symmetric cones (SCLCP) with the Cartesian P *(κ)-property, a weaker condition than the monotonicity. Based on the Nesterov-Todd, xy and yx directions employed as commutative search directions for semidefinite programming, we extend the variants of the short-, semilong-, and long-step path-following algorithms for symmetric conic linear programming proposed by Schmieta and Alizadeh to the Cartesian P *(κ)-SCLCP, and particularly show the global convergence and the iteration complexities of the proposed algorithms.

关 键 词：Cartesian P *(κ)-property symmetric cone linear complementarity problem path-following interior point algorithm global convergence COMPLEXITY 90C33 90C51 

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