Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term

摘要

In this paper we propose primal-dual interior-point algorithms for semidefinite optimization problems based on a new kernel function with a trigonometric barrier term. We show that the iteration bounds are $O(sqrt{n}log(frac{n}{epsilon}))$ for small-update methods and $O(n^{frac{3}{4}}log(frac{n}{epsilon}))$ for large-update, respectively. The resulting bound is better than the classical kernel function. For small-update, the iteration complexity is the best known bound for such methods.