Parabolic target-space interior-point algorithm for monotone weighted linear complementarity problem

Abstract

We revisit the main principles for constructing polynomial-time primal-dual interior-point algorithms (IPAs). We investigate the weighted Linear Complementarity Problem (WLCP), by extending the framework of Parabolic Target Space (PTS), proposed by Nesterov (2008) for primal-dual Linear Programming (LP) Problems. This approach has several advantages. The proposed method based on the PTS approach starts from an arbitrary strictly feasible primal-dual pair and follows a single central path toward the solution. It has the best known worst-case complexity bound. Finally, it works in a large neighborhood of the deviated central path, allowing very large steps. The latter ability results in a significant acceleration at the end of the process, confirmed by our preliminary computational experiments.