Hyperbolic Polynomials and Interior Point Methods for Convex Programming

doi:10.1287/moor.22.2.350

Hyperbolic Polynomials and Interior Point Methods for Convex Programming

1997-05-01

0

PRE

AI

DOI：10.1287/moor.22.2.350

原文链接

原文求助

摘要

En 中文

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. We give an explicit representation of this cone in terms of polynomial inequalities. 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.

Hyperbolic Polynomials and Interior Point Methods for Convex Programming

摘要

期刊

机构

引用论文