Universal Barrier is n-Self-Concordant

Yin Tat Lee(yintatuw.edu)
Man-Chung Yue(m.yueimperial.ac.uk)

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.

Keywords: Universal Barrier, Self-Concordance, s-Concave Distributions, Moment Inequalities

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation:

Download: [PDF]

Entry Submitted: 09/09/2018
Entry Accepted: 09/09/2018
Entry Last Modified: 09/09/2018

Modify/Update this entry