Scholarlink

<p>We revisit the main principles for constructing polynomial-time primal-dual interior-point algorithms (IPAs). We investigate the <i>weighted</i> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月12日

查看全文
  • Marianna E.-Nagy,
  • Tibor Illés,
  • Yurii Nesterov,
  • Petra Renáta Rigó

摘要

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.