In this paper, we establish the polynomial complexity of a primal-dual path-following interior point algorithm for solving semidefinite optimization（SDO） problems. The proposed algorithm is based on a new kernel fun...In this paper, we establish the polynomial complexity of a primal-dual path-following interior point algorithm for solving semidefinite optimization（SDO） problems. The proposed algorithm is based on a new kernel function which differs from the existing kernel functions in which it has a double barrier term. With this function we define a new search direction and also a new proximity function for analyzing its complexity. We show that if q1 〉 q2 〉 1, the algorithm has O（（q1 ＋ 1） nq1＋1/2（q1-q2）logn/ε）and O（（q1 ＋ 1）2（q1-q2）^3q1-2q2＋1√n logn/c） complexity results for large- and small-update methods, respectively.展开更多
文摘In this paper, we establish the polynomial complexity of a primal-dual path-following interior point algorithm for solving semidefinite optimization（SDO） problems. The proposed algorithm is based on a new kernel function which differs from the existing kernel functions in which it has a double barrier term. With this function we define a new search direction and also a new proximity function for analyzing its complexity. We show that if q1 〉 q2 〉 1, the algorithm has O（（q1 ＋ 1） nq1＋1/2（q1-q2）logn/ε）and O（（q1 ＋ 1）2（q1-q2）^3q1-2q2＋1√n logn/c） complexity results for large- and small-update methods, respectively.
