Title

A Continuation Algorithm for a Class of Linear Complementarity Problems Using an Extrapolation Technique

Document Type

Article

Publication Date

6-1-1993

Department

Mathematics

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

Find in your library

Share

 
COinS