New Interior-Point Algorithm for Linear Optimization Based on a Universal Tangent Direction

Eisenberg-Nagy, Marianna and Illés, Tibor and Nesterov, Yurii and Rigó, Petra Renáta (2026) New Interior-Point Algorithm for Linear Optimization Based on a Universal Tangent Direction. SIAM JOURNAL ON OPTIMIZATION, 36 (1). pp. 185-203. ISSN 1052-6234

Text SIOPT_UTD_IPA2026.pdf - Published Version Restricted to Registered users only Download (491kB) | Request a copy

Abstract

In this paper, we suggest a new interior-point algorithm for linear optimization, based on the idea of parabolic target space. Our algorithm can start at any strictly feasible primal-dual pair and go directly towards a solution by a predictor-corrector scheme. We prove that the complexity of the proposed method coincides with the currently known best complexity results for interior-point algorithms. The method demonstrates a very fast local convergence on the test set problems we have evaluated. One of the main differences between our approach and the standard framework is that our algorithm is based on a parabolic primal-dual barrier function. © by SIAM.

Actions (login required)

View Item