Search Directions and Convergence Analysis of Some Infeasible Path-following Methods for the Monotone Semi-Definite LCP

Paul Tseng

We consider a family of primal/primal-dual/dual search directions for the monotone LCP over the space of n by n symmetric block- diagonal matrices. It considers two infeasible predictor-corrector path- following methods using these search directions, with the predictor and corrector steps used either in series (similar to the Mizuno-Todd-Ye method) or in parallel (similar to Mizuno et al./McShane's method). The methods attain global linear convergence with a convergence ratio which, depending on the quality of the starting iterate, ranges from $1-O(\sqrt{n})^{-1}$ to $1-O(n)^{-1}$. The analysis is fairly simple and parallels that for the LP and LCP cases.

Report, Department of Mathematics, University of Washington, Seattle, Washington 98195, U.S.A.