Local Convergence of Predictor-Corrector Infeasible-Interior-Point Algorithms for SDPs and SDLCPs

M. Kojima, M. Shida and S. Shindoh

(Formerly titled "Global and Local Convergence of Predictor-Corrector Infeasible- Interior-Point Algorithms for Semidefinite Programs")

An example of SDPs (semidefinite programs) exhibits a substantial difficulty in proving the superlinear convergence in a direct extension of the Mizuno-Todd-Ye predictor-corrector primal-dual interior-point method for LPs (linear programs) to SDPs, and suggests that we need to enforce the generated sequence to converge a solution tangentially to the central surface. A predictor-corrector infeasible-interior-point algorithm, incorporating this additional restriction, for monotone SDLCPs (semidefinite linear complementarity problems) enjoys the superlinear convergence under strict complementarity and nondegeneracy conditions.

Technical Report, October, 1995; revised December, 1995.