Friday, October 12, 2007
3:30 pm, MC 5158

Tutte Seminar Series
Combinatorics & Optimization
Fall 2007

Hristo Sendov
University of Western Ontario

On the Tunçel Conjecture: A New Class of Self-Concordant Barriers on Sets of Symmetric Matrices

Given a separable strongly self-concordant function $f:\R^n \rightarrow \R$, we show the associated spectral function $F(X)= (f \circ \lambda)(X)$ is also strongly self-concordant function. In addition, there is a universal constant $\mathcal{O}$ such that, if $f(x)$ is separable self-concordant barrier then $\mathcal{O}^2F(X)$ is a self-concordant barrier. We estimate that for the universal constant we have $\mathcal{O} \le 22$. This generalizes the relationship between the standard logarithmic barriers $-\sum_{i=1}^n\log x_i$ and $-\log \det X$ and gives a partial solution to a conjecture of L. Tunçel.

This is a joint work with Javier Peña, Carnegie Mellon University.