Constructing self-concordant barriers for convex cones

Yurii Nesterov (nesterovcore.ucl.ac.be)

Abstract: In this paper we develop a technique for constructing self-concordant barriers for convex cones. We start from a simple proof for a variant of standard result on transformation of a $\nu$-self-concordant barrier for a set into a self-concordant barrier for its conic hull with parameter $(3.08 \sqrt{\nu} + 3.57)^2$. Further, we develop a convenient composition theorem for constructing barriers directly for convex cones. In particular, we can construct now good barriers for several interesting cones obtained as a conic hull of epigraph of a univariate function. This technique works for power functions, entropy, logarithm and exponent function, etc. It provides a background for development of polynomial-time methods for separable optimization problems. Thus, our abilities in constructing good barriers for convex sets and cones become now identical.

Keywords: interior-point methods, self-concordant barriers, conic problem, barrier calculus

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

Citation: CORE Discussion Paper 2006/30, March 2006

Download: [PDF]

Entry Submitted: 04/03/2006
Entry Accepted: 04/03/2006
Entry Last Modified: 04/03/2006

Modify/Update this entry