Optimization Online


Constructing self-concordant barriers for convex cones

Yurii Nesterov (nesterov***at***core.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

  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 Programming Society