Minimal hyperbolic polynomials and ranks of homogeneous cones

Hyperbolic polynomials are intrinsically connected with many important classes of optimization problems such as linear programs, semidefinite programs and, more generally, symmetric cone programming. In particular, we have the following inclusions:

We recall that if $p:\mathcal{V}\to\mathbb{R}$ is a homogeneous polynomial of degree $d$ over a real finite-dimensional Euclidean space $\mathcal{V}$, then we say that it is hyperbolic along $e$ if $p(e)>0$ and for every $x\in\mathcal{V}$ the one-variable polynomial $t\mapsto p(x-te)$ only has real roots. With that, the corresponding hyperbolicity cone is

For example, if $p:\mathbb{R}^{n}\to\mathbb{R}$ is such that $p(x_{1},\ldots,x_{n})=\Pi_{i=1}^{n}x_{i}$ and $e=(1,\ldots,1)$ then $\Lambda_{+}(p,e)=\mathbb{R}^{n}_{+}$. Similarly, over the real symmetric matrices $\mathcal{S}^{n}$, we have $\Lambda_{+}(\det,I_{n})=\mathcal{S}_{+}^{n}$, where $I_{n}$ is the $n\times n$ identity matrix, $\det:\mathcal{S}^{n}\to\mathbb{R}$ is the determinant polynomial and $\mathcal{S}_{+}^{n}$ is the cone of $n\times n$ real symmetric positive semidefinite matrices.

Homogeneous cones and symmetric cones are hyperbolicity cones, but that is not the end of the story. One key point is that if a given ${\mathcal{K}}$ can be written as a hyperbolicity cone $\Lambda_{+}(p,e)$, there could be multiple hyperbolic polynomials that generate ${\mathcal{K}}$. For example, we have $\mathbb{R}^{3}_{+}=\Lambda_{+}(p^{*},e)$, where $p^{*}(x_{1},x_{2},x_{3})=x_{1}^{2}x_{2}x_{3}$ even though $\mathbb{R}^{3}$ is generated by the degree $3$ polynomial $x_{1}x_{2}x_{3}$.

Given ${\mathcal{K}}$, a natural question then is how to find a minimal degree polynomial that generates ${\mathcal{K}}$. Fortunately, such a question is well-defined, because two minimal degree polynomials for the same hyperbolicity cone must differ by a constant, see [HV07, Lemma 2.1]. Unfortunately, such a question is also notoriously hard to answer, see Section 2.1 where we overview some facts on this topic.

At first glance, finding minimal degree polynomials might seem an esoteric task, but it is actually filled with practical implications. Güler proved that $-\log p$ is a logarithmically homogeneous self-concordant barrier for the interior of $\Lambda_{+}(p,e)$ with barrier parameter $d=\deg p$, see [Gül97, Section 4]. By its turn, the barrier parameter controls the computational complexity of interior point methods. The summary is that we can potentially make an interior point method faster by using a polynomial of smaller degree.

While the minimal degree polynomials of symmetric cones are known, there seems to be several gaps in our knowledge of minimal polynomials of homogeneous cones and general hyperbolicity cones.

Given a homogeneous cone ${\mathcal{K}}$, Güler showed in [Gül97, Section 8] how to construct a hyperbolic polynomial $p$ such that ${\mathcal{K}}=\Lambda_{+}(p,e)$ holds for some $e$. Unfortunately, his construction (which was based on results of Gindikin [Gin92]) does not produce minimal polynomials even when ${\mathcal{K}}=\mathcal{S}_{+}^{n}$.

As mentioned previously, part of the difficulty is that it is hard to attest that a given hyperbolic polynomial is of minimal degree. However, there is one important exception to this: the so-called rank-one generated (ROG) hyperbolicity cones, which were studied in [IL23]. A hyperbolicity cone $\Lambda_{+}(p,e)$ is ROG if its extreme rays are generated by rank-$1$ elements, where the rank of a given $x$ is the number of nonzero roots of the polynomial $t\mapsto p(x-te)$.

If a pointed full-dimensional hyperbolicity cone $\Lambda_{+}(p,e)$ is ROG (with respect to $p$) then $p$ must be a minimal degree polynomial for $\Lambda_{+}(p,e)$, see [IL23, Proposition 3.5]. This helps to bring some geometry in what was an otherwise purely algebraic question. With that, the following question was formulated in [IL23, Section 5].

Can homogeneous cones be realized as ROG hyperbolicity cones?

Unfortunately, as we will see in this paper the answer is no. We will exhibit a homogeneous cone that cannot be realized as a ROG hyperbolicity cone.

We also recall that there is a notion of rank for homogeneous cone. Although it is known that a symmetric cone has a minimal degree polynomial equal to its rank, we will also observe that this is no longer true for homogeneous cones. Indeed, there exists a homogeneous cone of rank $3$ whose minimal degree polynomial is $4$, see Section 4.2. More generally, we will present a result on the degrees of the minimal polynomials for cones arising as duals of PSD cones with chordal sparsity patterns.

Here is a summary of our results.

• •

  We provide minimal degree polynomials for the duals of PSD cones with chordal sparsity patterns, see Theorem 3.1. Then, based on this result, we furnish several consequences for hyperbolicity and homogeneous cones. Among the PSD cones with chordal sparsity patterns, if an additional condition is satisfied, these cones become homogeneous. In combination with Theorem 3.1, this allow us to find several examples of homogeneous cones that cannot be realized as ROG hyperbolicity cones, see Theorem 4.1 and Section 4.1.

• •

  We present a discussion on the connection of homogenous cone rank and the degree of minimal polynomials for homogeneous cones. In particular, if the ${\mathcal{K}}$ is the dual of a cone that arises from a homogeneous chordal sparsity pattern, then the degree of minimal polynomials is no more than $O(n^{2})$ where $n$ is the homogeneous cone rank. We also present some results for general homogeneous cones, but they are more limited in scope. For example, we discuss an exponential bound for general homogeneous cones, see Proposition 4.5.

This work is organized as follows. In Section 2 we recall some basic facts about semialgebraic and hyperbolicity cones. In Section 3, we present a discussion on the dual of cones arising from chordal sparsity patterns. Finally, in Section 4 we have results on ROG hyperbolicity cones and minimal degree polynomials of homogeneous cones.

We recall some basic nomenclature on convex sets that will be needed in the sequel, see [Roc97] for more details. Let ${\mathcal{K}}$ be a closed convex cone ${\mathcal{K}}$ contained in a finite dimensional Euclidean space $\mathcal{V}$. ${\mathcal{K}}$ is said to be pointed if ${\mathcal{K}}\cap-{\mathcal{K}}=\{0\}$ and it is said to be full-dimensional if the linear span of ${\mathcal{K}}$ is $\mathcal{V}$. We denote the relative interior of ${\mathcal{K}}$ by $\mathrm{ri}\,{\mathcal{K}}$.

Of special interest to us is the example of chordal cones and their duals. Given a graph $G$ with nodes $V=\{1,...,n\}$ and edges $E$, we associate to it a convex cone $S_{+}(G)\subseteq S_{+}^{n}$ given by

Denote by $S(G)$ the set of symmetric matrices with the same support, i.e., the span of $S_{+}(G)$. A cone that is related to $S_{+}(G)$ is

where $A_{C}$ is the submatrix indexed by the vertices of $C$. The cone $S^{*}(G)$ is a hyperbolicity cone since it is the intersection of the symmetric cones $\{A\in S(G)~{}|~{}A_{C}\succeq 0\}$ among $G$-cliques $C$. By the classic result of [GJSW84, Theorem 7] we have $S^{*}(G)=S_{+}(G)^{*}$ if and only if $G$ is chordal, in which case we can also say by [AHMR88, Theorem 3.3] that

We observe that the interior of $S^{*}(G)$ is given by

Let $I_{n}$ denote the $n\times n$ identity matrix, (3.2) holds because $(I_{n})_{C}\succ 0$ for all $G$-cliques $C$, so $\mathrm{int}\,(S^{*}(G))=\{A\in S(G)\,|\,A_{C}\succ 0\textrm{ for all }G\textrm{-cliques }C\}$, by [Roc97, Theorem 6.5]. Since every $G$-clique is contained in some maximal clique and principal submatrices of positive definite matrices are positive definite, we obtain (3.2).

It follows that the degree of the minimal polynomial of $S^{*}(G)$ is the sum of the sizes of its maximal cliques. While general graphs can have exponentially many cliques with respect to the number of vertices, chordal graphs admit no such behavior. In fact, since every chordal graph has an elimination order, there are at most $n$ maximal cliques in a chordal graph with $n$ vertices (see [BP93] for more details on chordal graphs). Since the size of each clique has a trivial bound of $n$, this tells us that the degree of the minimal polynomial of $S^{*}(G)$ is $O(|V(G)|^{2})$, where $V(G)$ is the set of vertices of $G$. While $|V(G)|^{2}$ can never be attained, the degree can in fact grow quadratically as illustrated in the following example.

Before we proceed, we recall that a closed convex cone ${\mathcal{K}}\subseteq\mathcal{V}$ is said to be homogeneous if its group of automorphisms acts transitively on its relative interior, i.e., $\forall x,y\in\mathrm{ri}\,{\mathcal{K}}$, there exists $A\in\operatorname{Aut}({\mathcal{K}})$ such that $Ax=y$. Then, a cone ${\mathcal{K}}$ is said to be self-dual if there exists some inner product $\langle\cdot,\cdot\rangle$ over $\mathcal{V}$ for which ${\mathcal{K}}$ coincides with its dual cone ${\mathcal{K}}^{*}\coloneqq\{y\mid\langle x,y\rangle\geq 0,\forall x\in{\mathcal{K}}\}$. With that a symmetric cone is a self-dual homogeneous cone. Examples of symmetric cones are the $n\times n$ positive semidefinite matrices over the real numbers $\mathcal{S}_{+}^{n}$, the nonnegative orthant $\mathbb{R}^{n}_{+}$ and the second-order cone ${\mathcal{L}^{n+1}_{2}}\coloneqq\{(x,t)\mid t\geq\lVert{x}\rVert_{2}\}$, where $\lVert{\cdot}\rVert_{2}$ indicates the $2$-norm.

Symmetric cones have a natural notion of rank that comes from its Jordan algebraic structure. Fortunately, we will not need to discuss the details of that and it suffices to recall that the ranks of $\mathcal{S}_{+}^{n}$, $\mathbb{R}^{n}_{+}$ and ${\mathcal{L}^{n+1}_{2}}$ are $n$, $n$ and $2$, respectively.

We also recall that given a hyperbolic polynomial $p:\mathcal{V}\to\mathbb{R}$ along a hyperbolicity direction $e$, we define the rank of $x\in\mathcal{V}$ as

A hyperbolicity cone $\Lambda_{+}(p,e)$ is said to be rank-one generated (ROG) if its extreme rays are generated by rank-$1$ elements. More generally, a given closed convex cone ${\mathcal{K}}$ is said to be realizable as a ROG hyperbolicity cone if there exists $p$ and $e$ such that ${\mathcal{K}}=\Lambda_{+}(p,e)$ and $\Lambda_{+}(p,e)$ is ROG. The subtlety here is that even if $\Lambda_{+}(p,e)=\Lambda_{+}(\hat{p},e)$ holds for a certain cone, the rank function induced by $p$ and $\hat{p}$ may still be different, so ROGness depends on the choice of $p$. However, if $\Lambda_{+}(p,e)$ is ROG, then $p$ must be a minimal polynomial for $\Lambda_{+}(p,e)$, see [IL23, Proposition 3.5].

All symmetric cones are realizable as ROG hyperbolicity cones, see [IL23, Proposition 3.8]. For example, we have $\mathcal{S}_{+}^{n}=\Lambda_{+}(\det,I_{n})$. The extreme rays of $\mathcal{S}_{+}^{n}$ correspond to rank-$1$ matrices (in the usual linear algebraic sense). They also correspond to rank-$1$ elements in the hyperbolic sense, since the matrix rank of $X\in\mathcal{S}_{+}^{n}$ is the number of nonzero roots of $t\mapsto\det(tI_{n}-X)$. In this way, a minimal degree polynomial of $\mathcal{S}_{+}^{n}$ is indeed the determinant polynomial, which has degree $n$. For $\mathbb{R}^{n}_{+}$ and ${\mathcal{L}^{n+1}_{2}}$, minimal degree polynomials have degrees $n$ and $2$, respectively. More generally, a symmetric cone has a minimal degree polynomial of degree equal to its rank¹¹1The precise proof of this statement comes from the fact a symmetric cone admits a generalized notion of determinant, which is a polynomial of degree equal to its rank. With respect to this determinant, a symmetric cone can be realized as a ROG hyperbolicity cone, see the discussion in [IL23, Section 3.1.1]..

If $G$ is chordal, then $S_{+}(G)$ (see (3.1)) is a ROG hyperbolicity cone with respect to the usual determinant polynomial and $I_{n}$, since every $X\in S_{+}({G})$ has a decomposition in rank-$1$ matrices that respects the sparsity pattern defined by $G$. $S^{*}(G)$ is also a hyperbolicity cone, but, in contrast, it is rarely ROG as we will see in the next result.

We would like to thank Hideto Nakashima for helpful comments. The support of the Institute of Statistical Mathematics in the form of a visiting professorship for the first author is gratefully acknowledged.