A polynomial projective algorithm for convex feasibility problems with positive-definite constraints
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912438241198080 |
|---|---|
| author | Chubanov, Sergei |
| author_facet | Chubanov, Sergei |
| contents | We study a class of projective transformations of spectraplexes associated with self-dual cones and, on this basis, propose a polynomial-time algorithm for convex feasibility problems with positive definite constraints. At each iteration of the algorithm, either a feasible solution is found or a suitable valid inequality inducing a projective transformation allowing to bring the solution set closer to the center of an associated spectraplex. The closeness to the center is measured in terms of a potential function. The running time of our algorithm makes the existing complexity bounds more precise for the case when the number of equations linking the positive definite variable matrices is not less than the sum of the ranks of the respective positive-semidefinite cones. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_15484 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A polynomial projective algorithm for convex feasibility problems with positive-definite constraints Chubanov, Sergei Optimization and Control 90C22 We study a class of projective transformations of spectraplexes associated with self-dual cones and, on this basis, propose a polynomial-time algorithm for convex feasibility problems with positive definite constraints. At each iteration of the algorithm, either a feasible solution is found or a suitable valid inequality inducing a projective transformation allowing to bring the solution set closer to the center of an associated spectraplex. The closeness to the center is measured in terms of a potential function. The running time of our algorithm makes the existing complexity bounds more precise for the case when the number of equations linking the positive definite variable matrices is not less than the sum of the ranks of the respective positive-semidefinite cones. |
| title | A polynomial projective algorithm for convex feasibility problems with positive-definite constraints |
| topic | Optimization and Control 90C22 |
| url | https://arxiv.org/abs/2506.15484 |