A lower bound on the optimal self-concordance parameter of convex cones

Let $K \subset \mathbb R^n$ be a regular convex cone, let $e_1,\dots,e_n \in \partial K$ be linearly independent points on the boundary of a compact affine section of the cone, and let $x^* \in K^o$ be a point in the relative interior of this section. For $k = 1,\dots,n$, let $l_k$ be the line through the points $e_k$ and $x^*$, let $y_k$ be the intersection point of $l_k$ with $\partial K$ opposite to $e_k$, and let $z_k$ be the intersection point of $l_k$ with the linear subspace spanned by all points $e_l$, $l = 1,\dots,n$ except $e_k$. We give a lower bound on the self-concordance parameter $\nu$ of logarithmically homogeneous self-concordant barriers $F: K^o \to \mathbb R$ on $K$ in terms of the projective cross-ratios $q_k = (e_k,x^*;y_k,z_k)$. The previously known lower bound of Nesterov and Nemirovski can be obtained from our result as a special case. As an application, we construct an optimal barrier for the epigraph of the $||\cdot||_{\infty}$-norm in $\mathbb R^n$ and compute lower bounds on the optimal self-concordance parameters for the power cone and the epigraph of the $||\cdot||_p$-norm in $\mathbb R^2$.

Article

Download

View A lower bound on the optimal self-concordance parameter of convex cones