{"ID":2870904,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.11890","arxiv_id":"2509.11890","title":"An Inexact Tensor-Train Primal-Dual Interior-Point Method for Semidefinite Programs","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 maintains approximate superlinear convergence despite inexact computations in the tensor format and leverages a primal-dual infeasible interior-point framework. In experiments on Maximum Cut, Maximum Stable Set, and Correlation Clustering, the tensor-train interior point method handles problems up to size $2^{12}$ with duality gaps around $10^{-6}$ in approximately 1.5~h and using less than 2~GB of memory, outperforming state-of-the-art solvers on larger instances. Moreover, numerical evidence indicates that tensor-train ranks of the iterates remain moderate along the interior-point trajectory, explaining 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.","short_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 maintains approxima...","url_abs":"https://arxiv.org/abs/2509.11890","url_pdf":"https://arxiv.org/pdf/2509.11890v1","authors":"[\"Frederik Kelbel\",\"Sergey Dolgov\",\"Dante Kalise\",\"Alessandra Russo\"]","published":"2025-09-15T13:07:39Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}