An efficient primal-dual interior point algorithm for convex quadratic semidefinite optimization

We introduce a primal-dual interior point algorithm for convex quadratic semidefinite optimization. This algorithm is based on an extension of the technique presented in the work of Zhang et al. for linear optimization. The symmetrization of the search direction is based on the Nesterov–Todd scaling scheme. Our analysis demonstrates that this method solves efficiently the problem within polynomial time. Notably, the short-step algorithm achieves the best-known iteration bound, namely \(O(\sqrt{n}\log \frac{n}{\varepsilon })\) $O(\sqrt{n}log\frac{n}{\epsilon })$ -iterations. The numerical experiments conclude that the newly proposed algorithm is not only polynomial but requires a number of iterations clearly lower than that obtained theoretically.