The entropic barrier: a simple and optimal universal self-concordant barrier
This provides a foundational advancement in convex optimization by offering a simple and optimal barrier construction, impacting algorithms for solving convex programs.
The paper tackled the problem of constructing an explicit universal barrier for convex bodies with optimal self-concordance, proving that the Cramér transform of the uniform measure yields a (1+o(1)) n-self-concordant barrier, which improves upon a seminal result by Nesterov and Nemirovski.
We prove that the Cramér transform of the uniform measure on a convex body in $\mathbb{R}^n$ is a $(1+o(1)) n$-self-concordant barrier, improving a seminal result of Nesterov and Nemirovski. This gives the first explicit construction of a universal barrier for convex bodies with optimal self-concordance parameter. The proof is based on basic geometry of log-concave distributions, and elementary duality in exponential families.