An Inexact Tensor-Train Primal-Dual Interior-Point Method for Semidefinite Programs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911155443728384 |
|---|---|
| author | Kelbel, Frederik Dolgov, Sergey Kalise, Dante Russo, Alessandra |
| author_facet | Kelbel, Frederik Dolgov, Sergey Kalise, Dante Russo, Alessandra |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_11890 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Inexact Tensor-Train Primal-Dual Interior-Point Method for Semidefinite Programs Kelbel, Frederik Dolgov, Sergey Kalise, Dante Russo, Alessandra Optimization and Control 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. |
| title | An Inexact Tensor-Train Primal-Dual Interior-Point Method for Semidefinite Programs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2509.11890 |