On a general class of interior-point algorithms for semidefinite programming with polynomial complexity and superlinear convergence

Rongqin Sheng, Florian A. Potra and Jun Ji

We propose a unified analysis for a class of infeasible-start predictor-corrector algorithms for semidefinite programming problems, using the Monteiro-Zhang unified direction. The algorithms are direct generalizations of the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming. We show that the algorithms belonging to this class are globally convergent, provided the problem has a solution, and have optimal computational complexity. We also give simple sufficient conditions for superlinear convergence. Our results generalize the results obtained by the first two authors for the infeasible-interior-point algorithm proposed by Kojima, Shida and Shindoh and Potra and Sheng.

Reports on Computational Mathematics, No. 89/1996, Department of Mathematics, The University of Iowa

Contact: rsheng@math.uiowa.edu