Corrector-predictor arc-search interior-point algorithm for $P_*(kappa)$-LCP acting in a wide neighborhood of the central path
|
Behrouz Kheirfam *  |
Azarbaijan Shahid Madani University , b.kheirfam@azaruniv.edu |
|
Abstract: (9227 Views) |
In this paper, we propose an arc-search corrector-predictor
interior-point method for solving $P_*(kappa)$-linear
complementarity problems. The proposed algorithm searches 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 central path introduced by Ai and Zhang. The
algorithm does not depend on the handicap $kappa$ of the problem,
so that it can be used for any $P_*(kappa)$-linear complementarity
problem. Based on the ellipse approximation of the central path and
the wide neighborhood, we show that the proposed algorithm has
$O((1+kappa)sqrt{n}L)$ iteration complexity, the best-known
iteration complexity obtained so far by any interior-point method
for solving $P_*(kappa)$-linear complementarity problems.
|
|
Keywords: Linear complementarity problem, interior-point method, corrector-predictor algorithm, arc search, polynomial complexity. |
|
Full-Text [PDF 653 kb]
(20409 Downloads)
|
Type of Study: Original |
Subject:
Continuous Optimization Received: 2016/05/18 | Accepted: 2017/05/13 | Published: 2017/08/4
|
|
|
|