Superlinear Convergence of Interior-Point Algorithms for Semidefinite Programming

Florian A. Potra and Rongqin Sheng

We prove the superlinear convergence of the primal-dual infeasible-interior-point path-following algorithm proposed recently by Kojima, Shida and Shindoh and the present authors, under two conditions: (1) the SDP problem has a strictly complementary solution, and (2) the size of the central path neighborhood approaches zero. The nondegeneracy condition suggested by Kojima, Shida and Shindoh is not used in our analysis. Our result implies that the modified algorithm of Kojima, Shida and Shindoh, which enforces condition (2) by using additional corrector steps, has superlinear convergence under the standard assumption of strict complementarity.

Reports On Computational Mathematics, No. 86/1996, Department Of Mathematics, The University Of Iowa.