A CONTINUATION ALGORITHM FOR A CLASS OF LINEAR COMPLEMENTARITY-PROBLEMS USING AN EXTRAPOLATION TECHNIQUE
A polynomial-time continuation algorithm is presented for a class of linear complementarity problems with positive semidefinite matrices. The linear extrapolation technique is combined with the Newton iteration in the predictor-corrector procedure of the algorithm to numerically follow the solution curve of the homotopy equations arising from the perturbed Karush-Kuhn-Tucker condition. The convergence rate of the method is proved to be 1 - 4/(7 square-root n) after each cycle consisting of one extrapolation between two Newton steps.
LINEAR ALGEBRA AND ITS APPLICATIONS
(1993). A CONTINUATION ALGORITHM FOR A CLASS OF LINEAR COMPLEMENTARITY-PROBLEMS USING AN EXTRAPOLATION TECHNIQUE. LINEAR ALGEBRA AND ITS APPLICATIONS, 186, 199-214.
Available at: http://aquila.usm.edu/fac_pubs/6473