Djamel Benterki, Adnan Yassine, Amina Zerari: Interior-point algorithm for semidefinite programming based on a logarithmic kernel function, 3-17

Abstract:

In this work, we propose a primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with an efficient logarithmic barrier term. We show that the best result of iteration bounds can be achieved, namely $O(\sqrt{n}\log n\log \frac{n}{\varepsilon }),$ for large update and $O(\sqrt{n}\log \frac{n}{\varepsilon })$ for small-update methods.

Key Words: Semidefinite optimization, kernel functions, primal-dual interior-point method, large and small-update methods, complexity bound.

2010 Mathematics Subject Classification: Primary 90C22; Secondary 30C40, 90C51.