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

• 成果类型: Article; Early Access
• 署名作者: Nagy, Marianna E.; Illes, Tibor; Nesterov, Yurii; Rigo, Petra Renata
• 署名单位: Corvinus University Budapest
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02260-x
• 发表日期: 2025
• 关键词: Matrices

摘要

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.