A Continuation Algorithm for a Class of Linear Complementarity Problems Using an Extrapolation Technique
Document Type
Article
Publication Date
6-1-1993
Department
Mathematics
School
Mathematics and Natural Sciences
Abstract
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.
Publication Title
Linear Algebra and Its Applications
Volume
186
First Page
199
Last Page
214
Recommended Citation
Ding, J.
(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: https://aquila.usm.edu/fac_pubs/6473