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

Eisenberg-Nagy, Marianna and Illés, Tibor and Nesterov, Yurii and Rigó, Petra Renáta (2025) Parabolic target-space interior-point algorithm for monotone weighted linear complementarity problem. MATHEMATICAL PROGRAMMING. ISSN 0025-5610 (In Press)

Preview

Text s10107-025-02260-x.pdf - Published Version Available under License Creative Commons Attribution. Download (462kB) | Preview

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.

Actions (login required)

Edit Item