|
Abstract
|
We propose an arc-search corrector-predictor interior point method for solving 𝑃∗(𝜅)-linear
complementarity problems. The proposed algorithm searches for the optimizers along an
ellipse that is an approximation of the central path. The algorithm generates a sequence of
iterates in the wide neighborhood of the central path introduced by Ai and Zhang. The
algorithm does not depend on the handicap 𝜅of the problem, so that it can be used for any
𝑃∗(𝜅)-linear complementarity problem. Based on the ellipse approximation of the central
path and the wide neighborhood, we show that the proposed algorithm has 𝑂((1 + 𝜅)√𝑛𝐿)
iteration complexity, the best-known iteration complexity obtained so far by any interior point
method for solving 𝑃∗(𝜅)-linear complementarity problems. Some numerical results are
presented to show the performance of the algorithm.
|