##
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.

Contact: tseng@math.washington.edu