Universal Barrier is $n$-Self-Concordant

Abstract

This paper shows that the self-concordance parameter of the universal barrier on any $n$-dimensional proper convex domain is upper bounded by $n$. This bound is tight and improves the previous $O(n)$ bound by Nesterov and Nemirovski. The key to our main result is a pair of new, sharp moment inequalities for $s$-concave distributions, which could be of independent interest.

Cited by in corpus (4)

• Solving Linear Programs with Sqrt(rank) Linear System Solves
• A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
• Convex optimization
• The tropicalization of the entropic barrier