An Inexact Tensor-Train Primal-Dual Interior-Point Method for Semidefinite Programs
arXiv:2509.11890
The paper proposes a primal‑dual interior‑point algorithm that uses tensor‑train decompositions to efficiently solve large semidefinite programs, providing convergence analysis and demonstrating performance on combinatorial optimization benchmarks.
Abstract
In this work, we introduce an interior-point method that employs tensor decompositions to efficiently represent and manipulate the variables and constraints of semidefinite programs, targeting problems where the solutions may not be low-rank but admit low-tensor-train rank approximations. Our method leverages a primal-dual infeasible interior-point framework with global and local convergence estimates. In experiments on Maximum Cut, Maximum Stable Set, and Correlation Clustering, the tensor-train interior-point method handles problems up to size with certified primal-dual accuracy, reported gaps of approximate order , and remains the only primal-dual SDP solver reported at the largest dimensions across all three benchmarks. Moreover, numerical evidence indicates that tensor-train ranks of the iterates typically remain structured and moderate along the interior-point trajectory, with instance-dependent growth for harder high-rank cases, supporting the scalability of the approach. Tensor-train interior-point methods offer a promising avenue for problems that lack traditional sparsity or low-rank structure, exploiting tensor-train structures instead.
Added convergence theory, new plots, and more experimental coverage