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]](../../InteriorPoint/gif/DVI.gif)
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)