Numerical analysis of the convex relaxation of the barrier parameter functional of self-concordant barriers
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916828807168000 |
|---|---|
| author | Pirau, Vitali Hildebrand, Roland |
| author_facet | Pirau, Vitali Hildebrand, Roland |
| contents | Self-concordant barriers are essential for interior-point algorithms in conic programming. To speed up the convergence it is of interest to find a barrier with the lowest possible parameter for a given cone. The barrier parameter is a non-convex function on the set of self-concordant barriers on a given cone, and finding an optimal barrier amounts to solving a non-convex infinite-dimensional optimization problem. In this work we study the degradation of the optimal value of the problem when the problem is convexified, and provide an estimate of the accuracy of the convex relaxation. The amount of degradation can be computed by comparing a 1-parameter family of non-convex bodies in $R^3$ with their convex hulls. Our study provides insight into the degree of non-convexity of the problem and opens up the possibility of constructing suboptimal barriers by solving the convex relaxation |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_01812 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Numerical analysis of the convex relaxation of the barrier parameter functional of self-concordant barriers Pirau, Vitali Hildebrand, Roland Optimization and Control Self-concordant barriers are essential for interior-point algorithms in conic programming. To speed up the convergence it is of interest to find a barrier with the lowest possible parameter for a given cone. The barrier parameter is a non-convex function on the set of self-concordant barriers on a given cone, and finding an optimal barrier amounts to solving a non-convex infinite-dimensional optimization problem. In this work we study the degradation of the optimal value of the problem when the problem is convexified, and provide an estimate of the accuracy of the convex relaxation. The amount of degradation can be computed by comparing a 1-parameter family of non-convex bodies in $R^3$ with their convex hulls. Our study provides insight into the degree of non-convexity of the problem and opens up the possibility of constructing suboptimal barriers by solving the convex relaxation |
| title | Numerical analysis of the convex relaxation of the barrier parameter functional of self-concordant barriers |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2507.01812 |