Universal barrier is n-self-concordant

Yin Tat Lee, Man Chung Yue

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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.

Original languageEnglish
Pages (from-to)1129-1148
Number of pages20
JournalMathematics of Operations Research
Volume46
Issue number3
DOIs
Publication statusPublished - Aug 2021

Keywords

  • Convex body
  • Interior-point methods
  • Moment inequalities
  • S-concave distributions
  • Self-concordance
  • Universal barrier

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Cite this