In the literature, superlinear convergence of implementable polynomial-time interior point algorithms to solve semi-definite programs (SDPs) can only be shown by (i) assuming that the given SDP is nondegenerate and modifying these algorithms, or (ii) considering special classes of SDPs, such as the class of linear semi-definite feasibility problems, when a suitable initial iterate is required as well. Otherwise, these algorithms are not easy to implement even though they can be shown to have polynomial iteration complexities and superlinear convergence. These are besides the assumption of strict complementarity imposed on the given SDP. In this paper, we show superlinear convergence of an implementable interior point algorithm that has polynomial iteration complexity when it is used to solve the homogeneous feasibility model of a primal-dual SDP pair that has no special structure imposed. This is achieved by only assuming strict complementarity and the availability of an interior feasible point to the primal SDP. Furthermore, we do not need to modify the algorithm to show this.
Citation
Submitted