The Entropic Barrier: Exponential Families, Log-Concave Geometry, and Self-Concordance

Sébastien Bubeck () and Ronen Eldan ()
Additional contact information
Sébastien Bubeck: Microsoft Research Redmond, Redmond, Washington 98052
Ronen Eldan: Weizmann Institute of Science, Rehovot 76100, Israel

Mathematics of Operations Research, 2019, vol. 44, issue 1, 264-276

Abstract: We prove that the Cramér transform of the uniform measure on a convex body in ℝ 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. As a side result, our calculations also show that the universal barrier of Nesterov and Nemirovski is exactly n -self-concordant on convex cones.

Keywords: linear optimization; interior-point methods; self-concordant barrier (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0923 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:44:y:2019:i:1:p:264-276

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().