Abstract:

In this paper we present a large-update primal-dual interior-point algorithm
for convex quadratic semi-definite optimization problems based on a new parametric
kernel function. The goal of this paper is to investigate such a kernel function and
show that the algorithm has the best complexity bound. The complexity bound is
shown to be O(√n log n log n
 ).

Key words: Kernel function｜ Interior-point algorithm , Polynomial complexity , Large-update methods