Numerical analysis of the convex relaxation of the barrier parameter functional of self-concordant barriers

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³ 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