1 Introduction

Let \(\mathcal Q\subset \mathbb {R}^3\) denote the three-dimensional second-order cone (also known as the “ice-cream” cone or the Lorentz cone):

$$\begin{aligned} \mathcal Q= \{ (x,t) \in \mathbb {R}^2 \times \mathbb {R}: \Vert x\Vert \le t \}. \end{aligned}$$

It is known that \(\mathcal Q\) is linearly isomorphic to the cone of \(2\times 2\) real symmetric positive semidefinite matrices. Indeed we have:

$$\begin{aligned} (x_1,x_2,t) \in \mathcal Q\quad \Longleftrightarrow \quad \begin{bmatrix} t-x_1&\quad x_2\\ x_2&\quad t+x_1\end{bmatrix} \succeq 0. \end{aligned}$$
(1)

Despite its apparent simplicity the second-order cone \(\mathcal Q\) has strong expressive abilities and allows us to represent various convex constraints that go beyond “simple quadratic constraints”. For example it can be used to express geometric means (\(x\mapsto \prod _{i=1}^n x_i^{p_i}\) where \(p_i \ge 0\), rational, and \(\sum _{i=1}^n p_i = 1\)), \(\ell _p\)-norm constraints, multifocal ellipses (see e.g., [11, Equation (3.5)]), robust counterparts of linear programs, etc. We refer the reader to [4, Section 3.3] for more details.

Given this strong expressive ability one may wonder whether the general positive semidefinite cone can be represented using \(\mathcal Q\). This question was posed in particular by Adrian Lewis (personal communication) and Glineur, Parrilo and Saunderson [7]. In this paper we show that this is not possible, even for the \(3\times 3\) positive semidefinite cone. To make things precise we use the language of lifts (or extended formulations), see [8]. We denote by \(\mathcal Q^k\) the Cartesian product of k copies of \(\mathcal Q\):

$$\begin{aligned} \mathcal Q^k = \mathcal Q\times \dots \times \mathcal Q\quad \text {({ k} copies)}. \end{aligned}$$

A linear slice of \(\mathcal Q^k\) is an intersection of \(\mathcal Q^k\) with a linear subspace. We say that a convex cone \(K \subset \mathbb {R}^m\) has a second-order cone lift of size k (or simply \(\mathcal Q^k\)-lift) if it can be written as the projection of a slice of \(\mathcal Q^k\), i.e.:

$$\begin{aligned} K = \pi \left( \mathcal Q^k \cap L\right) \end{aligned}$$
(2)

where \(\pi :\mathbb {R}^{3k} \rightarrow \mathbb {R}^m\) is a linear map and L is a linear subspace of \(\mathbb {R}^{3k}\). Let \(\mathbf {S}^n_+\) be the cone of \(n\times n\) real symmetric positive semidefinite matrices. In this paper we prove:

Theorem 1

The cone \(\mathbf {S}^3_+\) does not admit any \(\mathcal Q^k\)-lift for any finite k.

Actually our proof allows us to show that the slice of \(\mathbf {S}^3_+\) consisting of Hankel matrices does not admit any second-order representation (see Sect. 4 for details). Note that higher-dimensional second order cones of the form

$$\begin{aligned} \{(x,t) \in \mathbb {R}^{n} \times t : \Vert x\Vert \le t\} \end{aligned}$$

where \(n \ge 3\) can be represented using the three-dimensional cone \(\mathcal Q\), see e.g., [5, Section 2]. Thus Theorem 1 also rules out any representation of \(\mathbf {S}^3_+\) using the higher-dimensional second-order cones. Moreover since \(\mathbf {S}^3_+\) appears as a slice of higher-order positive semidefinite cones Theorem 1 also shows that one cannot represent \(\mathbf {S}^n_+\), for \(n \ge 3\) using second-order cones.

2 Preliminaries

The paper [8] introduced a general methodology to prove existence or nonexistence of lifts in terms of the slack matrix of a cone. In this section we review some of the definitions and results from this paper, and introduce the notion of a second-order cone factorization and the second-order cone rank.

Let E be a Euclidean space with inner product \(\langle \cdot , \cdot \rangle \) and let \(K \subseteq E\) be a cone. The dual cone \(K^*\) is defined as:

$$\begin{aligned} K^* = \{x \in E: \langle x, y \rangle \ge 0 \quad \forall y \in K \}. \end{aligned}$$

We also denote by \({{\mathrm{ext}}}(K)\) the extreme rays of a cone K. The notion of slack matrix plays a fundamental role in the study of lifts.

Definition 1

(Slack matrix) The slack matrix of a cone K, denoted \(S_K\), is a (potentially infinite) matrix where columns are indexed by extreme rays of K, and rows are indexed by extreme rays of \(K^*\) (the dual of K) and where the (x, y) entry is given by:

$$\begin{aligned} S_K[x,y] = \langle x,y \rangle \quad \forall (x,y) \in {{\mathrm{ext}}}(K^*) \times {{\mathrm{ext}}}(K). \end{aligned}$$
(3)

Note that, by definition of dual cone, all the entries of \(S_K\) are nonnegative. Also note that an element \(x \in {{\mathrm{ext}}}(K^*)\) (and similarly \(y \in {{\mathrm{ext}}}(K)\)) is only defined up to a positive multiple. Any choice of scaling gives a valid slack matrix of K and the properties of \(S_K\) that we are interested in will be independent of the scaling chosen.

The existence/nonexistence of a second-order cone lift for a convex cone K will depend on whether \(S_K\) admits a certain second-order cone factorization which we now define.

Definition 2

(\(\mathcal Q^k\)-factorization and second-order cone rank) Let \(S \in \mathbb {R}^{|I|\times |J|}\) be a matrix with nonnegative entries. We say that S has a \(\mathcal Q^k\)-factorization if there exist vectors \(a_i \in \mathcal Q^k\) for \(i\in I\) and \(b_j \in \mathcal Q^k\) for \(j \in J\) such that \(S[i,j] = \langle a_i, b_j \rangle \) for all \(i \in I\) and \(j \in J\). The smallest k for which such a factorization exists will be denoted \({{\mathrm{{{\mathrm{rank}}}_{soc}}}}(S)\).

Remark 1

Recall that for any \(a,b \in \mathcal Q\) we have \(\langle a, b \rangle \ge 0\). This means that any matrix with a second-order cone factorization is elementwise nonnegative.

Remark 2

It is important to note that the second-order cone rank of any matrix S can be equivalently expressed as the smallest k such that S admits a decomposition

$$\begin{aligned} S = M_1 + \dots + M_k \end{aligned}$$
(4)

where \({{\mathrm{{{\mathrm{rank}}}_{soc}}}}(M_l) = 1\) for each \(l=1,\dots ,k\) (i.e., each \(M_l\) has a factorization \(M_l[i,j] = \langle a_i, b_j \rangle \) where \(a_i,b_j \in \mathcal Q\)). This simply follows from the fact that \(\mathcal Q^k\) is the Cartesian product of k copies of \(\mathcal Q\).

We now state the result from [8] that we will need.

Theorem 2

(Existence of a lift, special case of [8]) Let K be a convex cone. If K has a \(\mathcal Q^k\)-lift then its slack matrix \(S_K\) has a \(\mathcal Q^k\)-factorization.

This theorem can actually be turned into an if and only if condition under mild conditions on K (e.g., K is proper), see [8], but we have only stated here the direction that we will need.

The cone \(\mathbf {S}^3_+\) In this paper we are interested in the cone \(K = \mathbf {S}^3_+\) of real symmetric \(3\times 3\) positive semidefinite matrices. The extreme rays of \(\mathbf {S}^3_+\) are rank-one matrices of the form \(xx^T\) where \(x \in \mathbb {R}^3\). Also \(\mathbf {S}^3_+\) is self-dual, i.e., \((\mathbf {S}^3_+)^* = \mathbf {S}^3_+\). The slack matrix of \(\mathbf {S}^3_+\) thus has its rows and columns indexed by three-dimensional vectors and

$$\begin{aligned} S_{\mathbf {S}^3_+}[x,y] = \langle xx^T, yy^T \rangle = \left( x^T y\right) ^2 \quad \forall (x,y) \in \mathbb {R}^3 \times \mathbb {R}^3. \end{aligned}$$
(5)

In order to prove that \(\mathbf {S}^3_+\) does not admit a second-order representation, we will show that its slack matrix does not admit any \(\mathcal Q^k\)-factorization for any finite k. In fact we will exhibit a sequence \((A_n)\) of submatrices of \(S_{\mathbf {S}^3_+}\) where \({{\mathrm{{{\mathrm{rank}}}_{soc}}}}(A_n)\) grows to \(+\infty \) as \(n\rightarrow +\infty \).

Before introducing this sequence of matrices we record the following simple (known) proposition concerning orthogonal vectors in the cone \(\mathcal Q\) which will be useful later.

Proposition 1

Let \(a,b_1,b_2 \in \mathcal Q\) nonzero and assume that \(\langle a,b_1 \rangle = \langle a,b_2 \rangle = 0\). Then \(b_1\) and \(b_2\) are collinear.

Proof

This is easy to see geometrically by visualizing the “ice cream” cone. We include a proof for completeness: let \(a = (a',t) \in \mathbb {R}^2 \times \mathbb {R}\) and \(b_i = (b'_i,s_i) \in \mathbb {R}^2 \times \mathbb {R}\) where \(\Vert a'\Vert \le t\) and \(\Vert b'_i\Vert \le s_i\). Note that for \(i=1,2\) we have \(0 = \langle a, b_i \rangle = \langle a', b'_i \rangle + t s_i \ge - \Vert a'\Vert \Vert b'_i\Vert + t s_i \ge 0\) where in the first inequality we used Cauchy-Schwarz and in the second inequality we used the definition of the second-order cone. It thus follows that all the inequalities must be equalities: by the equality case in Cauchy-Schwarz we must have that \(b'_i = \alpha _i a'\) for some constant \(\alpha _i < 0\) and we must also have \(t = \Vert a'\Vert \) and \(s_i = \Vert b'_i\Vert \). Thus we get that \(b_i = (\alpha _i a', |\alpha _i| \Vert a'\Vert ) = |\alpha _i| (-a',\Vert a'\Vert )\). This shows that \(b_1\) and \(b_2\) are both collinear to the same vector \((-a',\Vert a'\Vert )\) and thus completes the proof. \(\square \)

3 Proof of Theorem 1

A sequence of matrices We now define our sequence \(A_n\) of submatrices of the slack matrix of \(\mathbf {S}^3_+\). For any integer i define the vector

$$\begin{aligned} v_i = (1,i,i^2) \in \mathbb {R}^3. \end{aligned}$$
(6)

Note that this sequence of vectors satisfies the following:

$$\begin{aligned} \text {For all distinct integers } i_1,i_2,i_3 \; \det (v_{i_1},v_{i_2},v_{i_3}) \ne 0. \end{aligned}$$
(7)

Our matrix \(A_n\) has size \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) \times n\) and is defined as follows (rows are indexed by 2-subsets of [n] and columns are indexed by [n]):

$$\begin{aligned} A_n[\{i_1,i_2\},j] := & {} \left( ( v_{i_1} \times v_{i_2})^T v_j \right) ^2 \nonumber \\= & {} \det (v_{i_1},v_{i_2},v_j)^2 \quad \forall \{i_1,i_2\} \in \left( {\begin{array}{c}[n]\\ 2\end{array}}\right) , \; \forall j \in [n] \end{aligned}$$
(8)

where \(\times \) denotes the cross-product of three-dimensional vectors. It is clear from the definition of \(A_n\) that it is a submatrix of the slack matrix of \(\mathbf {S}^3_+\). Note that the sparsity pattern of \(A_n\) satisfies the following:

$$\begin{aligned} \begin{aligned}&A_n[e,j] = 0\quad \text {if } j \in e\\&A_n[e,j] > 0\quad \text {otherwise} \end{aligned} \qquad e \in \left( {\begin{array}{c}[n]\\ 2\end{array}}\right) , \; j \in [n]. \end{aligned}$$
(9)

Also note that \(A_n\) satisfies the following important recursive property: for any subset C of [n] of size \(n_0\) the submatrix \(A_n[\left( {\begin{array}{c}C\\ 2\end{array}}\right) ,C]\) has the same sparsity pattern as \(A_{n_0}\) (up to relabeling of rows and columns). In our main theorem we will show that the second-order cone rank of \(A_n\) grows to infinity with n.

Remark 3

(Geometric interpretation of (9)) The property (9) of the matrices \(A_n\) will be the key to prove a lower bound on their second-order cone rank. Geometrically, the property (9) reflects a certain 2-neighborliness property of the extreme raysFootnote 1\({{\mathrm{ext}}}(\mathbf {S}^3_+)\) of \(\mathbf {S}^3_+\) : for any two distinct extreme rays \(xx^T\) and \(yy^T\) of \(\mathbf {S}^3_+\), there is a supporting hyperplane H to \(\mathbf {S}^3_+\) that touches \({{\mathrm{ext}}}(\mathbf {S}^3_+)\) precisely at \(xx^T\) and \(yy^T\). This 2-neighborliness property turns out to be the key geometric obstruction for the existence of second-order cone lifts for \(\mathbf {S}^3_+\).

Covering numbers Our analysis of the matrix \(A_n\) will only rely on its sparsity pattern. Given two matrices A and B of the same size we write \(A \overset{supp}{=}B\) if A and B have the same support (i.e., \(A_{ij} = 0\) if and only if \(B_{ij} = 0\) for all i, j). We now define a combinatorial analogue of the second-order cone rank:

Definition 3

Given a nonnegative matrix A, we define the \(soc\)-covering number of A, denoted \({{\mathrm{cov_{soc}}}}(A)\) to be the smallest number k of matrices \(M_1,\dots ,M_k\) with \({{\mathrm{{{\mathrm{rank}}}_{soc}}}}(M_l) = 1\) for \(l=1,\dots ,k\) that are needed to cover the nonzero entries of A, i.e., such that

$$\begin{aligned} A \overset{supp}{=}M_1+\dots +M_k. \end{aligned}$$
(10)

Proposition 2

For any nonnegative matrix A we have \({{\mathrm{{{\mathrm{rank}}}_{soc}}}}(A) \ge {{\mathrm{cov_{soc}}}}(A)\).

Proof

This follows immediately from Remark 2 concerning \({{\mathrm{{{\mathrm{rank}}}_{soc}}}}\) and the definition of \({{\mathrm{cov_{soc}}}}\). \(\square \)

A simple but crucial fact concerning \(soc\)-coverings that we will use is the following: in any \(soc\)-covering of A of the form (10), each matrix \(M_l\) must satisfy \(M_l[i,j] = 0\) whenever \(A[i,j] = 0\). This is because the matrices \(M_1,\dots ,M_k\) are all entrywise nonnegative.

We are now ready to state our main result.

Theorem 3

Consider a sequence \((A_n)\) of matrices of sparsity pattern given in (9). Then for any \(n_0 \ge 2\) we have \({{\mathrm{cov_{soc}}}}(A_{3n_0^2}) \ge {{\mathrm{cov_{soc}}}}(A_{n_0})+1\). As a consequence \({{\mathrm{cov_{soc}}}}(A_{n})\rightarrow +\infty \) when \(n\rightarrow +\infty \).

The proof of our theorem rests on a key lemma concerning the sparsity pattern of any term in a \(soc\)-covering of \(A_n\).

Lemma 1

(Main) Let n be such that \(n \ge 3n_0^2\) for some \(n_0 \ge 2\). Assume \(M \in \mathbb {R}^{\left( {\begin{array}{c}n\\ 2\end{array}}\right) \times n}\) satisfies \({{\mathrm{{{\mathrm{rank}}}_{soc}}}}(M) = 1\) and \(M[e,j] = 0\) for all \(e\in \left( {\begin{array}{c}n\\ 2\end{array}}\right) \) and \(j \in [n]\) such that \(j \in e\). Then there is a subset C of [n] of size at least \(n_0\) such that the submatrix \(M[\left( {\begin{array}{c}C\\ 2\end{array}}\right) ,C]\) is identically zero.

Before proving this lemma, we show how this lemma can be used to easily prove Theorem 3.

Proof of Theorem 3

Let \(n = 3n_0^2\) and consider a \(soc\)-covering of \(A_n \overset{supp}{=}M_1 + \dots + M_r\) of size \(r = {{\mathrm{cov_{soc}}}}(A_n)\) (note that we have of course \(r \ge 1\) since \(A_n\) is not identically zero). By Lemma 1 there is a subset C of [n] of size \(n_0\) such that \(M_1[\left( {\begin{array}{c}C\\ 2\end{array}}\right) ,C] = 0\). It thus follows that we have \(A_n[\left( {\begin{array}{c}C\\ 2\end{array}}\right) ,C] \overset{supp}{=}M_2[\left( {\begin{array}{c}C\\ 2\end{array}}\right) ,C] + \dots + M_r[\left( {\begin{array}{c}C\\ 2\end{array}}\right) ,C]\). Also note that \(A_n[\left( {\begin{array}{c}C\\ 2\end{array}}\right) ,C] \overset{supp}{=}A_{n_0}\). It thus follows that \(A_{n_0}\) has a \(soc\)-covering of size \(r-1\) and thus \({{\mathrm{cov_{soc}}}}(A_{n_0}) \le {{\mathrm{cov_{soc}}}}(A_{3n_0^2})-1\). This completes the proof. \(\square \)

For completeness we show how Theorem 1 follows directly from Theorem 3.

Proof of Theorem 1

Since for any \(n \ge 1\), \(A_n\) is a submatrix of the slack matrix of \(\mathbf {S}^3_+\), Theorem 3 shows that the slack matrix of \(\mathbf {S}^3_+\) does not admit any \(\mathcal Q^k\)-factorization for finite k. This shows, via Theorem 2, that \(\mathbf {S}^3_+\) does not have a \(\mathcal Q^k\)-lift for any finite k. \(\square \)

The rest of the section is devoted to the proof of Lemma 1.

Proof of Lemma 1

Let \(M \in \mathbb {R}^{\left( {\begin{array}{c}n\\ 2\end{array}}\right) \times n}\) and assume that M has a factorization \(M_{e,j} = \langle a_e, b_j \rangle \) where \(a_e, b_j \in \mathcal Q\) for all \(e \in \left( {\begin{array}{c}[n]\\ 2\end{array}}\right) \) and \(j \in [n]\), and that \(M_{e,j} = 0\) whenever \(j \in e\).

Let \(E_0 := \{e \in \left( {\begin{array}{c}[n]\\ 2\end{array}}\right) : a_e = 0\}\) be the set of rows of M that are identically zero and let \(E_1 = \left( {\begin{array}{c}[n]\\ 2\end{array}}\right) \setminus E_0\). Similarly for the columns we let \(S_0 := \{j \in [n] : b_j = 0\}\) and \(S_1 = [n] \setminus S_0\).

In the next lemma we use the sparsity pattern of \(A_n\) together with Proposition 1 to infer additional properties on the sparsity pattern of M.

Lemma 2

Let C be a connected component of the graph with vertex set \(S_1\) and edge set \(E_1(S_1)\) (where \(E_1(S_1)\) consists of elements in \(E_1\) that connect only elements of \(S_1\)). Then necessarily \(M[\left( {\begin{array}{c}C\\ 2\end{array}}\right) ,C] = 0\).

Proof

We first show using Proposition 1 that all the vectors \(\{b_j\}_{j \in C}\) are necessarily collinear. Let \(j_1,j_2 \in S_1\) such that \(e = \{j_1,j_2\} \in E_1\). Note that since \(M_{e,j_1} = M_{e,j_2} = 0\) then we have, by Proposition 1 that \(b_{j_1}\) and \(b_{j_2}\) are collinear. It is easy to see thus now that if \(j_1\) and \(j_2\) are connected by a path in the graph \((S_1,E_1(S_1))\) then \(b_{j_1}\) and \(b_{j_2}\) must be collinear.

We thus get that all the columns of M indexed by C must be proportional to each other, and so they must have the same sparsity pattern. Now let \(e \in \left( {\begin{array}{c}C\\ 2\end{array}}\right) \). If \(a_e = 0\) then \(M[e,C] = 0\) since the entire row indexed by e is zero. Otherwise if \(a_e \ne 0\) let \(e=\{j_1,j_2\}\) with \(j_1,j_2 \in C\). Since, by assumption, \(M_{e,j_1} = 0\) it follows that for any \(j \in C\) we must have \(M_{e,j} = 0\), i.e., \(M[e,C] = 0\). This is true for any \(e \in \left( {\begin{array}{c}C\\ 2\end{array}}\right) \) thus we get that \(M[\left( {\begin{array}{c}C\\ 2\end{array}}\right) ,C] = 0\). \(\square \)

To complete the proof of Lemma 1 assume that \(n \ge 3n_0^2\) for some \(n_0 \ge 2\). We need to show that there is a subset C of [n] of size at least \(n_0\) such that \(M[\left( {\begin{array}{c}C\\ 2\end{array}}\right) ,C] = 0\).

First note that if the graph \((S_1,E_1(S_1))\) has a connected component of size at least \(n_0\) then we are done by Lemma 2. Also note that if \(S_0\) has size at least \(n_0\) we are also done because all the columns indexed by \(S_0\) are identically zero by definition.

In the rest of the proof we will thus assume that \(|S_0| < n_0\) and that the connected components of \((S_1,E_1(S_1))\) all have size \( < n_0\). We will show in this case that \(E_0\) necessarily contains a clique of size at least \(n_0\) (i.e., a subset of the form \(\left( {\begin{array}{c}C\\ 2\end{array}}\right) \) where \(|C| \ge n_0\)) and this will prove our claim since all the rows in \(E_0\) are identically zero by definition. The intuition is as follows: the assumption that \(|S_0| < n_0\) and that the connected components of \((S_1,E_1(S_1))\) have size \(< n_0\) mean that the graph \((S_1,E_1(S_1))\) is very sparse. In particular this means that \(E_1\) has to be small which means that \(E_0 = E_1^c\) must be large and thus it must contain a large clique.

More precisely, to show that \(E_1\) is small note that it consists of those edges that are either in \(E_1(S_1)\) or, otherwise, they must have at least one node in \(S_1^c = S_0\). Thus we get that

$$\begin{aligned} |E_1| \le |E_1(S_1)| + |S_0|(n-1) \le |E_1(S_1)| + (n_0-1) (n-1). \end{aligned}$$

where in the second inequality we used the fact that \(|S_0| < n_0\). Also since the connected components of \((S_1,E_1(S_1))\) all have size \(<n_0\) it is not difficult to show that \(|E_1(S_1)| < n_0 n/2\) (indeed if we let \(x_1,\dots ,x_k\) be the size of each connected component we have \(|E_1(S_1)| \le \frac{1}{2} \sum _{i=1}^k x_i^2 < \frac{1}{2} \sum _{i=1}^k n_0 x_i \le \frac{1}{2} n_0 n\)). Thus we get that

$$\begin{aligned} |E_1| \le \frac{n_0 n}{2} + (n_0 - 1)(n-1) \le \left( \frac{3}{2} n_0 - 1\right) n \end{aligned}$$

Thus this means, since \(E_0 = \left( {\begin{array}{c}[n]\\ 2\end{array}}\right) \setminus E_1\):

$$\begin{aligned} |E_0| \ge \left( {\begin{array}{c}n\\ 2\end{array}}\right) - \left( \frac{3}{2} n_0 - 1\right) n > \frac{n^2}{2} - \frac{3}{2} n_0 n \end{aligned}$$

We now invoke a result of Turán to show that \(E_0\) must contain a clique of size at least \(n_0\):

Theorem 4

(Turán, see e.g., [2]) Any graph on n vertices with more than \(\left( 1-\frac{1}{k}\right) \frac{n^2}{2}\) edges contains a clique of size \(k+1\).

By taking \(k = n_0-1\) we see that \(E_0\) contains a clique of size \(n_0\) if

$$\begin{aligned} \frac{n^2}{2} - \frac{3}{2} n_0 n > \left( 1-\frac{1}{n_0-1}\right) \frac{n^2}{2} \end{aligned}$$

This simplifies into

$$\begin{aligned} n > 3n_0(n_0-1) \end{aligned}$$

which is true for \(n \ge 3n_0^2\). \(\square \)

4 Slices of the \(3\times 3\) positive semidefinite cone

Hankel slice The proof given in the previous section actually shows the following more general statement.

Theorem 5

Let \(\mathcal { H}\) denote the cone of \(3\times 3\) positive semidefinite Hankel matrices:

$$\begin{aligned} \mathcal { H}= \{X \in \mathbf {S}^3_+ : X_{13} = X_{22}\}. \end{aligned}$$

Assume K is a convex cone that is “sandwiched” between \(\mathcal { H}\) and \(\mathbf {S}^3_+\), i.e., \(\mathcal { H}\subseteq K \subseteq \mathbf {S}^3_+\). Then K does not have a second-order cone representation.

Proof

The proof follows from the observation that the matrices \(A_n\) considered in Sect. 3 (see Eq. (8)) are actually submatrices of the generalized slack matrix of the pair of nested cones \((\mathcal { H},\mathbf {S}^3_+)\), the definition of which we now recall (see e.g., [9, Definition 6]): The generalized slack matrix of a pair of convex cones \((K_1,K_2)\) with \(K_1 \subseteq K_2\) is a matrix whose rows are indexed by \({{\mathrm{ext}}}(K_2^*)\) (the valid linear inequalities of \(K_2\)) and its columns indexed by \({{\mathrm{ext}}}(K_1)\) and is defined by

$$\begin{aligned} S_{K_1,K_2}[x,y] = \langle x, y \rangle \quad x \in {{\mathrm{ext}}}(K_2^*), y \in {{\mathrm{ext}}}(K_1). \end{aligned}$$

When \(K_1 = K_2\) this is precisely the slack matrix of \(K_1=K_2\). The following theorem is a generalization of Theorem 2 and can be proved using very similar arguments (see e.g., [9, Proposition 7]).

Theorem 6

(Generalization of Theorem 2 to nested cones) Let \(K_1,K_2\) be two convex cones with \(K_1 \subseteq K_2\), and assume there exists a convex cone K with a \(\mathcal Q^k\)-lift such that \(K_1 \subseteq K \subseteq K_2\). Then \(S_{K_1,K_2}\) has a \(\mathcal Q^k\)-factorization.

The main observation is to see that the vector \(v_i\) defined in (6) satisfies \(v_i v_i^T \in \mathcal { H}\), and so this shows that \(A_n\) defined in Equation (8) is a submatrix of the generalized slack matrix of the pair \((\mathcal { H},\mathbf {S}^3_+)\). Since \({{\mathrm{{{\mathrm{rank}}}_{soc}}}}(A_n)\) grows to infinity with n, this gives the desired result. \(\square \)

The dual cone of \(\mathcal { H}\) is the cone of nonnegative quartic polynomials on the real line (see e.g., [3, Section 3.5]). It thus follows that the latter is also not second-order cone representable using the second-order cone. More generally we can prove:

Corollary 1

Let \(\Sigma _{n,2d}\) be the cone of polynomials in n variables of degree at most 2d that are sums of squares. Then \(\Sigma _{n,2d}\) is not second-order cone representable except in the case \((n,2d)=(1,2)\).

For the proof we recall that in the cases \(n=1\) (univariate polynomials) and \(2d=2\) (quadratic polynomials), nonnegative polynomials are sums of squares.

Proof

For \(2d=2\), \(\Sigma _{n,2d}\) is the cone of nonnegative quadratic polynomials in n variables. By homogenization, this cone is linearly isomorphic to \(\mathbf {S}^{n+1}_+\), the cone of nonnegative quadratic forms in \(n+1\) variables. By Theorem 1, this shows that \(\Sigma _{n,2}\) is not second-order cone representable for \(n \ge 2\). The case \((n,2d)=(1,2)\) is clearly second-order cone representable because \(\mathbf {S}^2_+\) is linearly isomorphic to the second-order cone.

If \(2d \ge 4\) then the cone of nonnegative quartic polynomials on the real line can be obtained as a section of \(\Sigma _{n,2d}\) by setting to zero the coefficients of some appropriate monomials. This shows that \(\Sigma _{n,2d}\) is not second-order cone representable when \(2d \ge 4\). \(\square \)

Other slices of\(\mathbf {S}^3_+\)that are second-order cone representable There are certain slices of \(\mathbf {S}^3_+\) of codimension 1 that are, on the other hand, known to admit a second-order cone representation. For example the following second-order cone representation of the slice \(\{X \in \mathbf {S}^3_+ : X_{11} = X_{22}\}\) appears in [7]:

$$\begin{aligned} \begin{bmatrix} t&\quad a&\quad b\\ a&\quad t&\quad c\\ b&\quad c&\quad s \end{bmatrix} \succeq 0 \quad&\Longleftrightarrow \quad \exists u, v \in \mathbb {R}\text { s.t. } \begin{bmatrix} t+a&\quad b+c\\ b+c&\quad u\end{bmatrix} \succeq 0, \nonumber \\&\quad \quad \quad \quad \begin{bmatrix} t-a&\quad b-c\\ b-c&\quad v\end{bmatrix} \succeq 0, \quad u+v = 2s. \end{aligned}$$
(11)

(The \(2\times 2\) positive semidefinite constraints can be converted to second-order cone constraints using (1)). To see why (11) holds note that by applying a congruence transformation by \(\frac{1}{\sqrt{2}}\left[ {\begin{matrix} 1 &{} 1 &{} 0\\ 1 &{} -1 &{} 0\\ 0 &{} 0 &{} 2\end{matrix}}\right] \) on the \(3\times 3\) matrix on the left-hand side of (11) we get that

$$\begin{aligned} \begin{bmatrix} t&\quad a&\quad b\\ a&\quad t&\quad c\\ b&\quad c&\quad s \end{bmatrix} \succeq 0 \Longleftrightarrow \begin{bmatrix} t+a&\quad 0&\quad b+c\\ 0&\quad t-a&\quad b-c\\ b+c&\quad b-c&\quad 2s \end{bmatrix} \succeq 0. \end{aligned}$$

The latter matrix has an arrow structure and thus using results on the decomposition of matrices with chordal sparsity pattern [1, 6, 10] we get the decomposition (11).