Optimization Online


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

Roland Hildebrand(roland.hildebrand***at***imag.fr)

Abstract: 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$.

Keywords: conic programming, optimal barriers, self-concordance parameter

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Other )


Download: [PDF]

Entry Submitted: 06/19/2011
Entry Accepted: 06/19/2011
Entry Last Modified: 06/19/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society