Operations Research Seminar: Roland Hildebrand

Towards an optimal barrier on arbitrary convex cones

Roland Hildebrand, University Grenoble Alpes

 Self-concordant barriers are essential for interior-point algorithms in conic programming. The convergence rate of such an algorithm depends on a scalar parameter n. The smaller the value of n, the fewer iterates are necessary to achieve a given precision. It is therefore of interest to find a barrier with the lowest possible parameter for a given cone. The barrier parameter is , however, a non-convex function on the set of self-concordant barriers on a given cone, and finding an optimal barrier amounts to a non-convex infinite-dimensional optimization problem.

In this talk we discuss ways to tackle this problem. We show how to approximate it by a finite-dimensional non-convex optimization problem, which can be convexified at the cost of obtaining sub-optimal solutions. Our method also yields lower bounds on the optimal barrier parameter for a given convex cone.