|
Abstract
|
Abstract In this paper, we propose two interior-point methods for solving P∗(κ)-linear
complementarity problems (P∗(κ)-LCPs): a high order large update path following method
and a high order corrector–predictor method. Both algorithms generate sequences of iterates
in the wide neighborhood (N−2,τ (α)) of the central path introduced by Ai and Zhang. The
methods do not depend on the handicap κ of the problem so that they work for any P∗(κ)-
LCP . They have O((1+κ)√nL) iteration complexity, the best-known iteration complexity
obtained so far by any interior-point method for solving P∗(κ)-LCP. The high order corrector–
predictor algorithm is superlinearly convergent with Q-order (mp+1) for problems that admit
a strict complementarity solution and (mp+1)/2 for general problems, wheremp is the order
of the predictor step.
|