2025/07/02 by Vitali Pirau, Pirau, Vitali, Roland Hildebrand +1
Computer Science · Engineering · #Advanced Mathematical Modeling in Engineering #Elasticity and Wave Propagation #FOS: Mathematics #Optimization and Control (math.OC) #Slime Mold and Myxomycetes Research
paper · pdf · doi:10.48550/arxiv.2507.01812
openalex publication_date 2025/07/02 · openalex created_date 2025/10/20 · openalex updated_date 2026/07/28
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 R3 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