Hyperbolic Polynomials and Interior Point Methods for Convex Programming
Osman Guler
Hyperbolic polynomials have their origins in partial differential
equations. We show in this paper that they have applications in
interior point methods for convex programming. Each homogeneous
hyperbolic polynomial $p$ has an associated open and convex cone
called its hyperbolicity cone. The function $F(x)=-\log p(x)$ is
a logarithmically homogeneous self-concordant barrier function
for the hyperbolicity cone with barrier parameter equal to the
degree of $p$. The function $F(x)$ possesses striking additional
properties that are useful in designing long-step interior point
methods. For example, we show that the long-step primal potential
reduction methods of Nesterov and Todd and the surface-following
methods of Nesterov and Nemirovskii extend to hyperbolic barrier
functions. We also show that there exists a hyperbolic barrier
function on every homogeneous cone.
Technical Report TR95-40,
Department of Mathematics and Statistics,
University of Maryland Baltimore County,
Baltimore, MD 21228-5398.