Interior-Point Abstracts

A predictor-corrector method for for semidefinite linear programming

Chih-Jen Lin and Romesh Saigal

In this paper we present a generalization of the predictor corrector method of linear programming problem to semidefinite linear programming problem. We consider a direction which, we show, belongs to a family of directions presented by Kojima, Shindoh and Hara. This direction has also been analyzed by Zhang, who claims a similar result for a generalization of Mizuno, Todd and Ye method for the linear programming problem. We show that starting with the initial complementary slackness violation of $t_0$, in $(\mbox{log}(\frac{\epsilon}{t_0})\sqrt{n})$ of the predictor corrector method, the complementary slackness violation can be reduced to less than or equal to $\epsilon>0$. We also analyse a modified corrector direction in which the linear system to be solved differs from that of the predictor in only the right hand side, and obtain a similar bound. We then use this modified corrector step in an implementable method which is shown to take a total of $(\mbox{log}(\frac{\epsilon}{t_0})\sqrt{n}\mbox{log}(n))$ predictor and corrector steps. Since it takes $O(n^3)$ multiplications during each predictor or corrector step, after $O(\mbox{log}(\frac{\epsilon}{t_0})n^{3.5})$ multiplications the complementary slackness violation is reduced to less than or equal to $\epsilon$.

Technical Report, Department of Industrial Engineering, University of Michigan, October, 1995.