New complexity bounds for primal--dual interior-point algorithms in conic optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911151390982144 |
|---|---|
| author | Dahl, Joachim Tunçel, Levent Vandenberghe, Lieven |
| author_facet | Dahl, Joachim Tunçel, Levent Vandenberghe, Lieven |
| contents | We provide improved complexity results for symmetric primal--dual interior-point algorithms in conic optimization. The results follow from new uniform bounds on a key complexity measure for primal--dual metrics at pairs of primal and dual points. The complexity measure is defined as the largest eigenvalue of the product of the Hessians of the primal and dual barrier functions, normalized by the proximity of the points to the central path. For algorithms based on self-scaled barriers for symmetric cones, we determine the exact value of the complexity measure. In the significantly more general case of self-concordant barriers with negative curvature, we provide the asymptotically tight upper bound of 4/3. This result implies $O(\vartheta^{1/2}\ln(1/ε))$ iteration complexity for a variety of symmetric (and some nonsymmetric) primal--dual interior-point algorithms. Finally, in the case of general self-concordant barriers, we give improved bounds for some variants of the complexity measure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10263 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New complexity bounds for primal--dual interior-point algorithms in conic optimization Dahl, Joachim Tunçel, Levent Vandenberghe, Lieven Optimization and Control 90C25, 90C51 We provide improved complexity results for symmetric primal--dual interior-point algorithms in conic optimization. The results follow from new uniform bounds on a key complexity measure for primal--dual metrics at pairs of primal and dual points. The complexity measure is defined as the largest eigenvalue of the product of the Hessians of the primal and dual barrier functions, normalized by the proximity of the points to the central path. For algorithms based on self-scaled barriers for symmetric cones, we determine the exact value of the complexity measure. In the significantly more general case of self-concordant barriers with negative curvature, we provide the asymptotically tight upper bound of 4/3. This result implies $O(\vartheta^{1/2}\ln(1/ε))$ iteration complexity for a variety of symmetric (and some nonsymmetric) primal--dual interior-point algorithms. Finally, in the case of general self-concordant barriers, we give improved bounds for some variants of the complexity measure. |
| title | New complexity bounds for primal--dual interior-point algorithms in conic optimization |
| topic | Optimization and Control 90C25, 90C51 |
| url | https://arxiv.org/abs/2509.10263 |