Complexity analysis of an interior point algorithm for the semidefinite optimization based on a kernel function with a double barrier term

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 q₁ > q₂ > 1, the algorithm has O((q₁+1) n q₁+1 /2(q₁-q₂) log n/∈) and O((q₁+1) 3_q1-2_q2+1 2(q₁-q₂) √n log n/∈) complexity results for large- and small-update methods, respectively.