An infeasible start predictor corrector method for semi-definite linear programming

Romesh Saigal and C. J. Lin

In this paper we present an infeasible start path following predictor corrector method for semidefinite linear programming problem. This method does not assume that the dual pair of semidefinite programs have feasible solutions, and, in at most $O(|\mbox{log}(\frac{\epsilon}{\delta(A,b,C)\rho})|n)$ iterations of the predictor corrector method, finds either an approximate solution to the dual pair or shows that there is no optimal solution in a well defined bounded region. The nonexistence of optimal solutions is detected in a finite number of iterations. Here $\epsilon$ is a measure of non-optimality and infeasibility of the pair of solutions found, and is generally chosen to be small; $\delta(A,b,C)$ is a function of the data of the problem and $\rho$ is a measure of the size of the region searched, and is generally large. The method we present generalizes a method for linear programming developed by Mizuno. We give some preliminary computational experience for this method, and compare its performance ( measured by the number of iterations ) with that of the code SP of Vandenberghe and Boyd which is based on a potential reduction strategy, and the code SDPA of Fujisawa and Kojima which is based on a path following and potential reduction strategy.

Contact: rsaigal@engin.umich.edu


 [DVI]  [POSTSCRIPT]  [IP PAGE]  [SEARCH AGAIN]