∎

11institutetext: Lea Kapelevich 22institutetext: Operations Research Center,
MIT
22email<EMAIL_ADDRESS>33institutetext: Chris Coey 44institutetext: Operations
Research Center, MIT
44email<EMAIL_ADDRESS>55institutetext: Juan Pablo Vielma 66institutetext:
Google Research and
Sloan School of Management, MIT
66email<EMAIL_ADDRESS>66email<EMAIL_ADDRESS>
# Sum of squares generalizations for conic sets††thanks: This work has been
partially funded by the National Science Foundation under grant OAC-1835443
and the Office of Naval Research under grant N00014-18-1-2079.

Lea Kapelevich  Chris Coey  Juan Pablo Vielma

###### Abstract

In polynomial optimization problems, nonnegativity constraints are typically
handled using the _sum of squares_ condition. This can be efficiently enforced
using semidefinite programming formulations, or as more recently proposed by
Papp and Yildiz (2019), using the sum of squares cone directly in a
nonsymmetric interior point algorithm. Beyond nonnegativity, more complicated
polynomial constraints (in particular, generalizations of the positive
semidefinite, second order and $\ell_{1}$-norm cones) can also be modeled
through structured sum of squares programs. We take a different approach and
propose using more specialized polynomial cones instead. This can result in
lower dimensional formulations, more efficient oracles for interior point
methods, or self-concordant barriers with lower parameters. In most cases,
these algorithmic advantages also translate to faster solving times in
practice.

###### Keywords:

Polynomial optimization Sum of squares Interior point Non-symmetric conic
optimization

###### MSC:

90-08 90C25 90C51

##  1 Introduction

The _sum of squares_ (_SOS_) condition is commonly used as a tractable
restriction of polynomial nonnegativity. While SOS programs have traditionally
been formulated and solved using semidefinite programming (SDP), Papp and
Yildiz (2019) recently demonstrated the effectiveness of a nonsymmetric
interior point algorithm in solving SOS programs without SDP formulations. In
this note, we focus on structured SOS constraints that can be modeled using
more specialized cones. We describe and give barrier functions for three
related cones useful for modeling functions of dense polynomials, which we
hope will become useful modeling primitives.

The first is the cone of _SOS matrices_ , which was described by Coey et al.
(2020, Section 3.13) without derivation. We show that this cone can be
computationally favorable to equally low-dimensional SOS formulations.
Characterizations of univariate SOS matrix cones in the context of
optimization algorithms have previously been given by Genin et al. (2003,
Section 6). However, their use of monomial or Chebyshev bases complicates
computations of oracles in an interior point algorithm (Papp and Yildiz, 2019,
Section 3.1) and prevents effective generalizations to the multivariate case.

The second is an _SOS $\ell_{2}$-norm_ (_SOS-L2_) cone, which can be used to
certify pointwise membership in the second order cone for a vector with
polynomial components. The third is an _SOS $\ell_{1}$-norm_ (_SOS-L1_) cone,
which can be used to certify pointwise membership in the epigraph set of the
$\ell_{1}$-norm function. Although it is straightforward to use SOS
representations to approximate these sets, such formulations introduce cones
of higher dimension than the constrained polynomial vector. We believe we are
first to describe how to handle these sets in an interior point algorithm
without introducing auxiliary conic variables or constraints. We suggest new
barriers, with lower barrier parameters than SOS formulations allow.

In what follows, we use $\mathbb{S}^{m}$, $\mathbb{S}_{+}^{m}$, and
$\mathbb{S}_{++}^{m}$ to represent the symmetric, positive semidefinite and
positive definite matrices respectively with side dimension $m$. For sets,
$\operatorname{cl}$ denotes the closure and $\operatorname{int}$ denotes the
interior. $\llbracket a..b\rrbracket$ are the integers in the interval
$[a,b]$. $|A|$ denotes the dimension of a set $A$, and
$\operatorname{sd}(m)=|\mathbb{S}^{m}|=\nicefrac{{m(m+1)}}{{2}}$. We use
$\langle\cdot,\cdot\rangle_{A}$ for the inner product on $A$. For a linear
operator $M:A\to B$, the adjoint $M^{\ast}:B\to A$ is the unique operator
satisfying $\langle x,My\rangle_{A}=\langle y,M^{\ast}x\rangle_{B}$ for all
$x\in A$ and $y\in B$. $\mathbf{I}_{m}$ is the identity in
$\mathbb{R}^{m\times m}$. $\otimes_{K}:\mathbb{R}^{a_{1}\times
a_{2}}\times\mathbb{R}^{b_{1}\times b_{2}}\to\mathbb{R}^{a_{1}b_{1}\times
a_{2}b_{2}}$ is the usual Kronecker product. $\operatorname{diag}$ returns the
diagonal elements of a matrix and $\operatorname{Diag}$ maps a vector to a
matrix with the vector on the diagonal. All vectors, matrices, and higher
order tensors are written in bold font. $s_{i}$ is the $i$th element of a
vector $\mathbf{s}$ and $\mathbf{s}_{i\in\llbracket 1..N\rrbracket}$ is the
set $\\{\mathbf{s}_{1},\ldots,\mathbf{s}_{N}\\}$. If $a,b,c,d$ are scalars,
vectors, or matrices, then we use square brackets, e.g. $\begin{bmatrix}a&b\\\
c&d\end{bmatrix}$, to denote concatenation into a matrix or vector, or round
parentheses, e.g. $(a,b,c,d)$, for a general Cartesian product. If $A$ is a
vector space then $A^{n}$ is the Cartesian product of $n$ spaces $A$.
$\mathbb{R}[\mathbf{x}]_{n,d}$ is the ring of polynomials in the variables
$\mathbf{x}=(x_{1},\ldots,x_{n})$ with maximum degree $d$. Following the
notation of Papp and Yildiz (2019), we use $L=\binom{n+d}{n}$ and
$U=\binom{n+2d}{n}$ to denote the dimensions of $\mathbb{R}[\mathbf{x}]_{n,d}$
and $\mathbb{R}[\mathbf{x}]_{n,2d}$ respectively, when $n$ and $d$ are given
in the surrounding context.

In the remainder of this section we provide background on SOS polynomials and
implementation details of interior point algorithms that are required for
later sections. In Section 2 we describe the constraints we wish to model
using each new cone, and suggest alternative SOS formulations for comparison.
In Section 3 we outline how ideas introduced by Papp and Alizadeh (2013) can
be used to characterize the cone of SOS matrices and the SOS-L2 cone. Section
4 is focused on improving the parameter of the barriers for the SOS-L2 and
SOS-L1 cones. In Section 5 we outline implementation advantages of the new
cones. In Section 6 we compare various formulations using a numerical example
and conclude in Section 7.

###  1.1 The SOS polynomials cone and generic interior point algorithms

A polynomial $p(\mathbf{x})\in\mathbb{R}[\mathbf{x}]_{n,2d}$ is SOS if it can
be expressed in the form $p(\mathbf{x})=\sum_{i\in\llbracket
1..N\rrbracket}q_{i}(\mathbf{x})^{2}$ for some $N\in\mathbb{N}$ and
$q_{i\in\llbracket
1..N\rrbracket}(\mathbf{x})\in\mathbb{R}[\mathbf{x}]_{n,d}$. We denote the set
of SOS polynomials in $\mathbb{R}[\mathbf{x}]_{n,2d}$ by
${K}_{\operatorname{SOS}}$, which is a proper cone in
$\mathbb{R}[\mathbf{x}]_{n,2d}$ (Nesterov, 2000).

We also say that $\mathbf{s}\in{K}_{\operatorname{SOS}}$ for
$\mathbf{s}\in\mathbb{R}^{U}$ if $\mathbf{s}$ represents a vector of
coefficients of an SOS polynomial under a given basis. We use such
_vectorized_ definitions interchangeably with functional definitions of
polynomial cones. To construct a vectorized definition for
${K}_{\operatorname{SOS}}$, suppose we have a fixed basis for
$\mathbb{R}[\mathbf{x}]_{n,2d}$, and let $p_{i\in\llbracket
1..L\rrbracket}(\mathbf{x})$ be basis polynomials for
$\mathbb{R}[\mathbf{x}]_{n,d}$. Let $\lambda:\llbracket
1..L\rrbracket^{2}\to\mathbb{R}^{U}$ be a function such that $\lambda(i,j)$
returns the vector of coefficients of the polynomial
$p_{i}(\mathbf{x})p_{j}(\mathbf{x})$ using the fixed basis for
$\mathbb{R}[\mathbf{x}]_{n,2d}$. Define the _lifting operator_
$\mathsf{\Lambda}:\mathbb{R}^{U}\to\mathbb{S}^{L}$, introduced by Nesterov
(2000), as:

$\displaystyle\mathsf{\Lambda}(\mathbf{s})_{i,j}=\langle\lambda(i,j),\mathbf{s}\rangle_{\mathbb{R}^{U}}\quad\forall
i,j\in\llbracket 1..L\rrbracket,$ (1)

where $\mathsf{\Lambda}(\mathbf{s})_{ij}$ is a component in row $i$ and column
$j$. Now the cones ${K}_{\operatorname{SOS}}$ and
${K}_{\operatorname{SOS}}^{\ast}$ admit the characterization (Nesterov, 2000,
Theorem 7.1):

$\displaystyle{K}_{\operatorname{SOS}}$
$\displaystyle=\\{\mathbf{s}\in\mathbb{R}^{U}:\exists\mathbf{S}\in\mathbb{S}_{+}^{L},\mathbf{s}=\mathsf{\Lambda}^{\ast}(\mathbf{S})\\},$
(2a) $\displaystyle{K}_{\operatorname{SOS}}^{\ast}$
$\displaystyle=\\{\mathbf{s}\in\mathbb{R}^{U}:\mathsf{\Lambda}(\mathbf{s})\in\mathbb{S}_{+}^{L}\\}.$
(2b)

Equation 2 shows that the dual cone ${K}_{\operatorname{SOS}}^{\ast}$ is an
inverse linear image of the positive semidefinite (PSD) cone, and therefore
has an efficiently computable _logarithmically homogeneous self-concordant
barrier_ (LHSCB) (see (Nesterov and Nemirovskii, 1994, Definitions 2.3.1,
2.3.2)). In particular, by linearity of $\mathsf{\Lambda}$, the function
$\mathbf{s}\mapsto-\operatorname{logdet}(\mathsf{\Lambda}(\mathbf{s}))$ is an
LHSCB for ${K}_{\operatorname{SOS}}^{\ast}$ (Nesterov and Nemirovskii, 1994,
Proposition 5.1.1) with parameter $L$ (an $L$-LHSCB for short). This makes it
possible to solve optimization problems over ${K}_{\operatorname{SOS}}$ or
${K}_{\operatorname{SOS}}^{\ast}$ with a _generic_ primal-dual interior point
algorithm in polynomial time (Skajaa and Ye, 2015).

In a generic primal-dual interior point algorithm, very few oracles are needed
for each cone in the optimization problem. For example, the algorithm
described by Coey et al. (2020) only requires a membership check, an initial
interior point, and evaluations of derivatives of an LHSCB for each cone _or_
its dual. Optimizing over ${K}_{\operatorname{SOS}}$ directly instead of
building SDP formulations is appealing because the dimension of
${K}_{\operatorname{SOS}}$ is generally much smaller than the cone dimension
in SDP formulations that are amenable to more specialized algorithms (Papp and
Yildiz, 2019; Coey et al., 2020). In later sections we describe efficient
LHSCBs and membership checks for each cone we introduce.

The output of the lifting operator depends on the polynomial basis chosen for
$\mathbb{R}[\mathbf{x}]_{n,d}$ as well as the basis for
$\mathbb{R}[\mathbf{x}]_{n,2d}$. Following Papp and Yildiz (2019), we use a
set of Lagrange polynomials that are interpolant on some points
$\mathbf{t}_{i\in\llbracket 1..U\rrbracket}$ as the basis for
$\mathbb{R}_{n,2d}[\mathbf{x}]$ and the multivariate Chebyshev polynomials
(Hoffman and Withers, 1988) as the basis in $\mathbb{R}_{n,d}[\mathbf{x}]$.
These choices give the particular lifting operator we implement,
$\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s})$:

$\displaystyle\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s})_{i,j}={\textstyle\sum_{u\in\llbracket
1..U\rrbracket}}p_{i}(\mathbf{t}_{u})p_{j}(\mathbf{t}_{u})s_{u}$
$\displaystyle\quad\forall i,j\in\llbracket 1..L\rrbracket.$ (3)

Equivalently,
$\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s})=\mathbf{P}^{\top}\operatorname{Diag}(\mathbf{s})\mathbf{P}$,
where $P_{u,\ell}=p_{\ell}(\mathbf{t}_{u})$ for all $u\in\llbracket
1..U\rrbracket,\ell\in\llbracket 1..L\rrbracket$. The adjoint
$\mathsf{\Lambda}_{\operatorname{SOS}}^{\ast}:\mathbb{S}^{L}\to\mathbb{R}^{U}$
is given by
$\mathsf{\Lambda}_{\operatorname{SOS}}^{\ast}(\mathbf{S})=\operatorname{diag}(\mathbf{P}\mathbf{S}\mathbf{P}^{\top})$.
Papp and Yildiz (2019) show that the Lagrange basis gives rise to expressions
for the gradient and Hessian of the barrier for
${K}_{\operatorname{SOS}}^{\ast}$ that are computable in $\mathcal{O}(LU^{2})$
time for any $d,n\geq 1$.

##  2 Polynomial generalizations for three conic sets

The first set we consider are the polynomial matrices
$\mathbf{Q}(\mathbf{x})\in\mathbb{R}[\mathbf{x}]_{n,2d}^{m\times m}$ (i.e.
$m\times m$ matrices with components that are polynomials in $n$ variables of
maximum degree $2d$111 We assume that polynomial components in vectors and
matrices involve the same variables and have the same maximum degree, to avoid
detracting from the key ideas in this paper. This assumption could be removed
at the expense of more cumbersome notation. ) satisfying the constraint:

$\displaystyle\mathbf{Q}(\mathbf{x})\succeq 0\quad\forall\mathbf{x}.$ (4)

This constraint has various applications in statistics, control, and
engineering (Aylward et al., 2007, 2008; Doherty et al., 2004; Hol and
Scherer, 2004; Hall, 2019). A tractable restriction for Equation 4 is given by
the SOS formulation:

$\displaystyle\mathbf{y}^{\top}\mathbf{Q}(\mathbf{x})\mathbf{y}\in{K}_{\operatorname{SOS}}\quad\forall{\mathbf{y}}\in\mathbb{R}^{m}.$
(5)

This formulation is sometimes implemented in practice (e.g. (Legat et al.,
2017)) and requires an SOS cone of dimension $U\operatorname{sd}(m)$ (by
exploiting the fact that all terms are bilinear in the $\mathbf{y}$
variables). It is well known that Equation 5 is equivalent to restricting
$\mathbf{Q}(\mathbf{x})$ to be an _SOS matrix_ of the form
$\mathbf{Q}(\mathbf{x})=\mathbf{M}(\mathbf{x})^{\top}\mathbf{M}(\mathbf{x})$
for some $N\in\mathbb{N}$ and
$\mathbf{M}(\mathbf{x})\in\mathbb{R}[\mathbf{x}]_{n,d}^{N\times m}$
(Blekherman et al., 2012, Definition 3.76). To be consistent in terminology
with the other cones we introduce, we refer to SOS matrices as _SOS-PSD_
matrices, or belonging to ${K}_{\operatorname{SOSPSD}}$. We show how to
characterize ${K}_{\operatorname{SOSPSD}}$ and use it directly in an interior
point algorithm in Section 3.

The second set we consider are the polynomial vectors
$\mathbf{q(x)}\in\mathbb{R}[\mathbf{x}]_{n,2d}^{m}$ satisfying:

$\displaystyle{q}_{1}(\mathbf{x})\geq\sqrt{{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}\left({q}_{i}(\mathbf{x})\right)^{2}}\quad\forall\mathbf{x},$
(6)

and hence requiring $\mathbf{q(x)}$ to be in the epigraph set of the
$\ell_{2}$-norm function (second order cone) pointwise (cf. Equation 4
requiring the polynomial matrix to be in the PSD cone). A tractable
restriction for this constraint is given by the SOS formulation:

$\displaystyle\mathbf{y}^{\top}\operatorname{{Arw}}(\mathbf{q(\mathbf{x})})\mathbf{y}\in{K}_{\operatorname{SOS}}\quad\forall{\mathbf{y}}\in\mathbb{R}^{m},$
(7)

where
$\operatorname{{Arw}}:\mathbb{R}[\mathbf{x}]_{n,2d}^{m}\to\mathbb{R}[\mathbf{x}]_{n,2d}^{m\times
m}$ is defined by:

$\displaystyle\operatorname{{Arw}}(\mathbf{p}(\mathbf{x}))=\begin{bmatrix}p_{1}(\mathbf{x})&\bar{\mathbf{p}}(\mathbf{x})^{\top}\\\
\bar{\mathbf{p}}(\mathbf{x})&p_{1}(\mathbf{x})\mathbf{I}_{m-1}\end{bmatrix},\quad\mathbf{p}(\mathbf{x})=\left(p_{1}(\mathbf{x}),\bar{\mathbf{p}}(\mathbf{x})\right)\in\mathbb{R}[\mathbf{x}]_{n,2d}\times\mathbb{R}[\mathbf{x}]_{n,2d}^{m-1}.$
(8)

Due to the equivalence between Equation 5 and membership in
${K}_{\operatorname{SOSPSD}}$, Equation 7 is equivalent to requiring that
$\mathbf{q}(\mathbf{x})$ belongs to the cone we denote
${K}_{\operatorname{{Arw}}\operatorname{SOSPSD}}$ defined by:

$\displaystyle{K}_{\operatorname{{Arw}}\operatorname{SOSPSD}}=\\{\mathbf{q}(\mathbf{x})\in\mathbb{R}[\mathbf{x}]_{n,2d}^{m}:\operatorname{{Arw}}({\mathbf{q}(\mathbf{x})})\in{K}_{\operatorname{SOSPSD}}\\}.$
(9)

Membership in ${K}_{\operatorname{{Arw}}\operatorname{SOSPSD}}$ ensures
Equation 6 holds due to the SDP representation of the second order cone
(Alizadeh and Goldfarb, 2003), and the fact that the SOS-PSD condition
certifies pointwise positive semidefiniteness. An alternative restriction of
Equation 6 is described by the set we denote
${K}_{\operatorname{SOS}\ell_{2}}$, which is not representable by SOS cones in
general:

$\displaystyle{K}_{\operatorname{SOS}\ell_{2}}=\left\\{\begin{aligned}
\mathbf{q}(\mathbf{x})\in\mathbb{R}[\mathbf{x}]_{n,2d}^{m}:\exists
N\in\mathbb{N},\mathbf{p}_{i\in\llbracket
1..N\rrbracket}(\mathbf{x})\in\mathbb{R}[\mathbf{x}]_{n,d}^{m},\\\
\mathbf{q}(\mathbf{x})={\textstyle\sum_{i\in\llbracket
1..N\rrbracket}}\mathbf{p}_{i}(\mathbf{x})\circ\mathbf{p}_{i}(\mathbf{x})\end{aligned}\right\\},$
(10)

where $\circ:\mathbb{R}^{m}\times\mathbb{R}^{m}\to\mathbb{R}^{m}$ is defined
by:

$\displaystyle\mathbf{x}\circ\mathbf{y}=\begin{bmatrix}\mathbf{x}^{\top}\mathbf{y}\\\
x_{1}\bar{\mathbf{y}}+y_{1}\bar{\mathbf{x}}\end{bmatrix},\mathbf{x}=\left(x_{1},\bar{\mathbf{x}}\right),\mathbf{y}=\left(y_{1},\bar{\mathbf{y}}\right)\in\mathbb{R}\times\mathbb{R}^{m-1},$
(11)

and
$\circ:\mathbb{R}[\mathbf{x}]^{m}_{n,d}\times\mathbb{R}[\mathbf{x}]^{m}_{n,d}\to\mathbb{R}[\mathbf{x}]^{m}_{n,2d}$
on polynomial vectors is defined analogously. This set was also studied by
Kojima and Muramatsu with a focus on extending Positivstellensatz results
(Kojima and Muramatsu, 2007). The validity of
${K}_{\operatorname{SOS}\ell_{2}}$ as a restriction of Equation 6 follows from
the the characterization of the second order cone as a _cone of squares_
(Alizadeh and Goldfarb, 2003, Section 4). For this reason we will refer to the
elements of ${K}_{\operatorname{SOS}\ell_{2}}$ as the _SOS-L $2$_ polynomials.
For a polynomial vector in $\mathbb{R}[\mathbf{x}]_{n,2d}^{m}$, the dimension
of ${K}_{\operatorname{SOS}\ell_{2}}$ is $Um$, which is favorable to the
dimension $U\operatorname{sd}(m)$ of ${K}_{\operatorname{SOS}}$ required for
Equation 7 or ${K}_{\operatorname{SOSPSD}}$ in Equation 9. In addition, we
show in Section 4.1 that ${K}_{\operatorname{SOS}\ell_{2}}$ admits an LHSCB
with lower parameter than ${K}_{\operatorname{{Arw}}\operatorname{SOSPSD}}$.
However, we conjecture that for general $n$ and $d$,
${K}_{\operatorname{SOS}\ell_{2}}$ yields an approximation of Equation 6 that
is more conservative than that provided by Equation 9 (for example, consider
the vector $[1+x^{2},1-x^{2},2x]$, which belongs to
${K}_{\operatorname{{Arw}}\operatorname{SOSPSD}}$ but not
${K}_{\operatorname{SOS}\ell_{2}}$). A third formulation can be obtained by
modifying the SDP formulation for
${K}_{\operatorname{{Arw}}\operatorname{SOSPSD}}$ to account for all sparsity
in the $\mathbf{y}$ monomials (by introducing a specialized cone for the Gram
matrix of
$\mathbf{y}^{\top}\operatorname{{Arw}}(\mathbf{q}(\mathbf{x}))\mathbf{y}$).
However, this approach suffers from requiring $\mathcal{O}(L^{2})$ conic
variables for each polynomial in $\mathbf{q}(\mathbf{x})$, so we choose to
focus on ${K}_{\operatorname{SOS}}$ and ${K}_{\operatorname{SOSPSD}}$
formulations for ${K}_{\operatorname{{Arw}}\operatorname{SOSPSD}}$ instead.

The third and final set we consider is also described through a constraint on
a polynomial vector
$\mathbf{q}(\mathbf{x})\in\mathbb{R}[\mathbf{x}]_{n,2d}^{m}$. This constraint
is given by:

${q}_{1}(\mathbf{x})\geq{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}|{q}_{i}(\mathbf{x})|\quad\forall\mathbf{x},$ (12)

and hence requires the polynomial vector to be in the epigraph set of the
$\ell_{1}$-norm function (_$\ell_{1}$ -norm cone_) pointwise. A tractable
restriction for this constraint is given by the SOS formulation:

$\displaystyle q_{1}(\mathbf{x})-{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}\left(p_{i}(\mathbf{x})^{+}+p_{i}(\mathbf{x})^{-}\right)$
$\displaystyle\in{K}_{\operatorname{SOS}},$ (13a) $\displaystyle
q_{i}(\mathbf{x})$ $\displaystyle=p_{i}(\mathbf{x})^{+}-p_{i}(\mathbf{x})^{-}$
$\displaystyle\forall i\in\llbracket 2..m\rrbracket,$ (13b) $\displaystyle
p_{i}(\mathbf{x})^{+},p_{i}(\mathbf{x})^{-}$
$\displaystyle\in{K}_{\operatorname{SOS}}$ $\displaystyle\forall
i\in\llbracket 2..m\rrbracket,$ (13c)

which uses auxiliary polynomial variables $p_{i\in\llbracket
2..m\rrbracket}^{+}(\mathbf{x})\in\mathbb{R}[\mathbf{x}]_{n,2d}$ and
$p_{i\in\llbracket
2..m\rrbracket}^{-}(\mathbf{x})\in\mathbb{R}[\mathbf{x}]_{n,2d}$. We refer to
the projection of Equation 13 onto
$\mathbf{q(x)}\in\mathbb{R}[\mathbf{x}]_{n,2d}^{m}$ as
${K}_{\operatorname{SOS}\ell_{1}}$ and to its elements as the _SOS-L $1$_
polynomials. Note that the dimension of ${K}_{\operatorname{SOS}\ell_{1}}$ is
$Um$, while Equation 13 requires $2m-1$ SOS cones of dimension $U$ and
$U(m-1)$ additional equality constraints. In Section 4.2 we derive an
$Lm$-LHSCB that allows us to optimize over ${K}_{\operatorname{SOS}\ell_{1}}$
directly, while Equation 13 would require an LHSCB with parameter $L(2m-1)$.

We summarize some key properties of the new cones and SOS formulations in
Table 1: the total dimension of cones involved, the parameter of an LHSCB for
the conic sets, the time complexity to calculate the Hessian of the LHSCB
(discussed in Section 5), the level of conservatism of each new conic set
compared to its alternative SOS formulation, and the number of auxiliary
equality constraints and variables that need to be added in an optimization
problem.

| SOS-PSD | SOS-L2 | SOS-L1
---|---|---|---
| ${K}_{\operatorname{SOSPSD}}$ | (5) | ${K}_{\operatorname{SOS}\ell_{2}}$ | (7) | ${K}_{\operatorname{SOS}\ell_{1}}$ | (13)
cone dim. | $U\operatorname{sd}(m)$ | $U\operatorname{sd}(m)$ | $Um$ | $U\operatorname{sd}(m)$ | $Um$ | $U(2m-1)$
parameter | $Lm$ | $Lm$ | $2L$ | $Lm$ | $Lm$ | $L(2m-1)$
Hessian flops | $\mathcal{O}(LU^{2}m^{3})$ | $\mathcal{O}(LU^{2}m^{5})$ | $\mathcal{O}(LU^{2}m^{2})$ | $\mathcal{O}(LU^{2}m^{5})$ | $\mathcal{O}(LU^{2}m)$ | $\mathcal{O}(LU^{2}m)$
conservatism | equal | - | greater | - | equal | -
equalities | 0 | 0 | 0 | 0 | 0 | $U(m-1)$
variables | 0 | 0 | 0 | 0 | 0 | $2U(m-1)$
Table 1: Properties of new cones compared to SOS formulations.

##  3 SOS-PSD and SOS-L2 cones from general algebras

The ideas introduced by Papp and Alizadeh (2013) relating to SOS cones in
_general algebras_ allow us to characterize ${K}_{\operatorname{SOSPSD}}$ and
${K}_{\operatorname{SOS}\ell_{2}}$ without auxiliary SOS polynomial
constraints. As in Papp and Alizadeh (2013), let us define $(A,B,\diamond)$ as
a general algebra if $A,B$ are vector spaces and $\diamond:A\times A\to B$ is
a bilinear product that satisfies the distributive property. For a general
algebra $(A,B,\diamond)$, Papp and Alizadeh (2013) define the SOS cone
${K}_{\diamond}$:

$\displaystyle{K}_{\diamond}=\left\\{b\in B:\exists
N\in\mathbb{N},a_{i\in\llbracket 1..N\rrbracket}\in
A,b={\textstyle\sum_{i\in\llbracket 1..N\rrbracket}}a_{i}\diamond
a_{i}\right\\}.$ (14)

For instance, $\mathbb{S}_{+}$ is equal to the SOS cone of
$(\mathbb{R}^{m},\mathbb{S}^{m},\overline{\diamond})$ for
$\overline{\diamond}$ given by
$\mathbf{x}\overline{\diamond}\mathbf{y}=\tfrac{1}{2}(\mathbf{x}\mathbf{y}^{\top}+\mathbf{y}\mathbf{x}^{\top})$.
The second order cone is equal to the SOS cone of
$(\mathbb{R}^{m},\mathbb{R}^{m},\circ)$. ${K}_{\operatorname{SOS}}$ is equal
to the SOS cone of
$(\mathbb{R}[\mathbf{x}]_{n,d},\mathbb{R}[\mathbf{x}]_{n,2d},\cdot)$ where
$\cdot$ is the product of polynomials. To obtain our vectorized representation
of ${K}_{\operatorname{SOS}}$ we can redefine the function
$\lambda:\mathbb{R}^{L}\times\mathbb{R}^{L}\to\mathbb{R}^{U}$ so that for
$\mathbf{p}_{i},\mathbf{p}_{j}\in\mathbb{R}^{L}$ representing coefficients of
any polynomials in $\mathbb{R}[\mathbf{x}]_{n,d}$,
$\lambda(\mathbf{p}_{i},\mathbf{p}_{j})$ returns the vector of coefficients of
the product of the polynomials. Then ${K}_{\operatorname{SOS}}$ is equal to
the SOS cone of $(\mathbb{R}^{L},\mathbb{R}^{U},\lambda)$.

As we describe in Section 3.1, Papp and Alizadeh (2013) also show how to build
lifting operators for general algebras. This allows us to construct membership
checks and easily computable LHSCBs for ${K}_{\operatorname{SOSPSD}}^{\ast}$
and ${K}_{\operatorname{SOS}\ell_{2}}^{\ast}$ once we represent them as SOS
cones of _tensor products_ of algebras.

The tensor product of two algebras $(A_{1},B_{1},\diamond_{1})$ and
$(A_{2},B_{2},\diamond_{2})$ is a new algebra $(A_{1}\otimes
A_{2},B_{1}\otimes B_{2},\diamond_{1}\otimes\diamond_{2})$, where
$\diamond_{1}\otimes\diamond_{2}$ is defined via its action on _elementary
tensors_. For $\mathbf{u}_{1},\mathbf{v}_{1}\in A_{1}$ and
$\mathbf{u}_{2},\mathbf{v}_{2}\in A_{2}$:

$\displaystyle(\mathbf{u}_{1}\otimes\mathbf{u}_{2})\diamond_{1}\otimes\diamond_{2}(\mathbf{v}_{1}\otimes\mathbf{v}_{2})=(\mathbf{u}_{1}\diamond_{1}\mathbf{v}_{1})\otimes(\mathbf{u}_{2}\diamond_{2}\mathbf{v}_{2}).$
(15)

The algebra we are interested in for a functional representation of
${K}_{\operatorname{SOSPSD}}$ is the tensor product of
$(\mathbb{R}[\mathbf{x}]_{n,d},\mathbb{R}[\mathbf{x}]_{n,2d},\cdot)$ with
$(\mathbb{R}^{m},\mathbb{S}^{m},\bar{\diamond})$. We can think of elements in
$\mathbb{R}[\mathbf{x}]_{n,d}\otimes\mathbb{R}^{m}$ as polynomial vectors in
$\mathbb{R}[\mathbf{x}]_{n,d}^{m}$, and
$\mathbb{R}[\mathbf{x}]_{n,2d}\otimes\mathbb{S}^{m}$ as the symmetric
polynomial matrices in $\mathbb{R}[\mathbf{x}]_{n,2d}^{m\times m}$. The SOS
cone of
$(\mathbb{R}[\mathbf{x}]_{n,d}\otimes\mathbb{R}^{m},\mathbb{R}[\mathbf{x}]_{n,2d}\otimes\mathbb{S}^{m},\cdot\otimes\bar{\diamond})$
corresponds to the polynomial matrices that can be written as
${\textstyle\sum_{i\in\llbracket
1..N\rrbracket}}\mathbf{m}_{i}(\mathbf{x})\mathbf{m}_{i}(\mathbf{x})^{\top}$
with $\mathbf{m}_{i}(\mathbf{x})\in\mathbb{R}[\mathbf{x}]^{m}$ for all
$i\in\llbracket 1..N\rrbracket$ (Papp and Alizadeh, 2013, Section 4.3), which
is exactly ${K}_{\operatorname{SOSPSD}}$. Equivalently, a vectorized
representation of ${K}_{\operatorname{SOSPSD}}$ can be characterized as the
SOS cone of
$(\mathbb{R}^{L}\otimes\mathbb{R}^{m},\mathbb{R}^{U}\otimes\mathbb{S}^{m},\lambda\otimes\bar{\diamond})$.
We can think of $\mathbb{R}^{L}\otimes\mathbb{R}^{m}$ as $\mathbb{R}^{L\times
m}$ and we can think of $\mathbb{R}^{U}\otimes\mathbb{S}^{m}$ as a subspace of
$\mathbb{R}^{U\times m\times m}$ that represents the coefficients of symmetric
polynomial matrices.

Likewise, the algebra we are interested in for a functional representation of
${K}_{\operatorname{SOS}\ell_{2}}$ is the tensor product of
$(\mathbb{R}[\mathbf{x}]_{n,d},\mathbb{R}[\mathbf{x}]_{n,2d},\cdot)$ with
$(\mathbb{R}^{m},\mathbb{R}^{m},\circ)$. We can think of
$\mathbb{R}[\mathbf{x}]_{n,d}\otimes\mathbb{R}^{m}$ and
$\mathbb{R}[\mathbf{x}]_{n,2d}\otimes\mathbb{R}^{m}$ as
$\mathbb{R}[\mathbf{x}]_{n,d}^{m}$ and $\mathbb{R}[\mathbf{x}]_{n,2d}^{m}$
respectively. The SOS cone of the tensor product of these algebras then
corresponds to ${K}_{\operatorname{SOS}\ell_{2}}$ due to Equation 10. A
vectorized representation of ${K}_{\operatorname{SOS}\ell_{2}}$ may be
characterized as the SOS cone of
$(\mathbb{R}^{L}\otimes\mathbb{R}^{m},\mathbb{R}^{U}\otimes\mathbb{R}^{m},\lambda\otimes\circ)$.
We can think of $\mathbb{R}^{U}\otimes\mathbb{R}^{m}$ as the coefficients of
polynomial vectors, represented in $\mathbb{R}^{U\times m}$.

###  3.1 Lifting operators for SOS-PSD and SOS-L2

The lifting operator of $(A,B,\diamond)$, when $A$ and $B$ are finite
dimensional, is defined by Papp and Alizadeh (2013) as the function
$\mathsf{\Lambda}_{\diamond}:B\to\mathbb{S}^{|A|}$ satisfying $\langle
a_{1},\mathsf{\Lambda}_{\diamond}(b)a_{2}\rangle_{A}=\langle b,a_{1}\diamond
a_{2}\rangle_{B}$ for all $a_{1},a_{2}\in A$, $b\in B$. This leads to the
following descriptions of ${K}_{\diamond}$ and ${K}_{\diamond}^{\ast}$ (Papp
and Alizadeh, 2013, Theorem 3.2):

$\displaystyle{K}_{\diamond}$ $\displaystyle=\\{\mathbf{s}\in
B:\exists\mathbf{S}\succeq
0,\mathbf{s}=\mathsf{\Lambda}_{\diamond}^{\ast}(\mathbf{S})\\},$ (16a)
$\displaystyle{K}_{\diamond}^{\ast}$ $\displaystyle=\\{\mathbf{s}\in
B:\mathsf{\Lambda}_{\diamond}(\mathbf{s})\succeq 0\\}.$ (16b)

Recall that in order to use either ${K}_{\diamond}$ or ${K}_{\diamond}^{\ast}$
in a generic interior point algorithm, we require efficient oracles for a
membership check and derivatives of an LHSCB of ${K}_{\diamond}$ or
${K}_{\diamond}^{\ast}$. If $\mathsf{\Lambda}_{\diamond}(\mathbf{s})$ is
efficiently computable, Equation 16b provides a membership check for
${K}_{\diamond}^{\ast}$. Furthermore, an LHSCB for ${K}_{\diamond}^{\ast}$ is
given by
$\mathbf{s}\mapsto-\operatorname{logdet}({\mathsf{\Lambda}}_{\diamond}(\mathbf{s}))$
with barrier parameter $|A|$ due to the linearity of
${\mathsf{\Lambda}}_{\diamond}$ (Nesterov and Nemirovskii, 1994, Proposition
5.1.1). The following lemma describes how to compute
$\mathsf{\Lambda}_{\diamond}(\mathbf{s})$ for a tensor product algebra.

###### Lemma 1

(Papp and Alizadeh, 2013, Lemma 4.1): If $\mathbf{w}_{1}\in B_{1}$ and
$\mathbf{w}_{2}\in B_{2}$, then:

$\displaystyle\mathsf{\Lambda}_{\diamond_{1}\otimes\diamond_{2}}(\mathbf{w}_{1}\otimes\mathbf{w}_{2})=\mathsf{\Lambda}_{\diamond_{1}}(\mathbf{w}_{1})\otimes_{K}\mathsf{\Lambda}_{\diamond_{2}}(\mathbf{w}_{2}).$
(17)

Let us define
$\otimes:\mathbb{R}^{U}\times\mathbb{S}^{m}\to\mathbb{R}^{U\times m\times m}$
such that $(\mathbf{u}\otimes\mathbf{V})_{i,j,k}=u_{i}V_{j,k}$ and let us
represent the coefficients of a polynomial matrix by a tensor
$\mathbf{S}\in\mathbb{R}^{U\times m\times m}$. Then we may write
$\mathbf{S}={\textstyle\sum_{i\in\llbracket 1..m\rrbracket,j\in\llbracket
1..i\rrbracket}}\mathbf{S}_{i,j}\otimes\mathbf{E}_{i,j}$, where
$\mathbf{E}_{i,j}\in\mathbb{R}^{m\times m}$ is a matrix of zeros with
$E_{i,j}=E_{j,i}=1$ and $\mathbf{S}_{i,j}\in\mathbb{R}^{U}$ are the
coefficients of the polynomial in row $i$ and column $j$. Applying Lemma 1,
the lifting operator for ${K}_{\operatorname{SOSPSD}}$,
$\mathsf{\Lambda}_{\operatorname{SOSPSD}}:\mathbb{R}^{U\times m\times
m}\to\mathbb{S}^{Lm}$ is:

$\displaystyle\mathsf{\Lambda}_{\operatorname{SOSPSD}}(\mathbf{S})=\mathsf{\Lambda}_{\lambda\otimes\bar{\diamond}}(\mathbf{S})$
$\displaystyle=\mathsf{\Lambda}_{\lambda\otimes\bar{\diamond}}({\textstyle\sum_{i\in\llbracket
1..m\rrbracket,j\in\llbracket
1..i\rrbracket}}\mathbf{S}_{i,j}\otimes\mathbf{E}_{i,j})$ (18a)
$\displaystyle={\textstyle\sum_{i\in\llbracket 1..m\rrbracket,j\in\llbracket
1..i\rrbracket}}\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{S}_{i,j})\otimes_{K}\mathbf{E}_{i,j}.$
(18b)

The output is a block matrix, where each $L\times L$ submatrix in the $i$th
group of rows and $j$th group of columns is
$\mathsf{\Lambda}_{\operatorname{SOSPSD}}(\mathbf{S})_{i,j}=\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{S}_{i,j})$
for all $i,j\in\llbracket 1..m\rrbracket$. The adjoint operator
$\mathsf{\Lambda}_{\operatorname{SOSPSD}}^{\ast}:\mathbb{S}^{Lm}\to\mathbb{R}^{U\times
m\times m}$ may also be defined blockwise,
$\mathsf{\Lambda}_{\operatorname{SOSPSD}}^{\ast}(\mathbf{S})_{i,j}=\mathsf{\Lambda}_{\operatorname{SOS}}^{\ast}(\mathbf{S}_{i,j})$
for all $i,j\in\llbracket 1..m\rrbracket$ where
$\mathbf{S}_{i,j}\in\mathbb{R}^{L\times L}$ is the $(i,j)$th submatrix in
$\mathbf{S}$.

Likewise, we use a tensor $\mathbf{s}\in\mathbb{R}^{U\times m}$ to describe
the coefficients of a polynomial vector, and write
$\mathbf{s}_{i}\in\mathbb{R}^{U}$ to denote the vector of coefficients of the
polynomial in component $i$. Applying Lemma 1 again, we obtain the (blockwise)
definition of the lifting operator for ${K}_{\operatorname{SOS}\ell_{2}}$,
$\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}:\mathbb{R}^{U\times
m}\to\mathbb{S}^{Lm}$:

$\displaystyle\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}(\mathbf{s})_{i,j}=\begin{cases}\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1})&i=j\\\
\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{j})&i=1,j\neq 1\\\
\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{i})&i\neq 1,j=1\\\
0&\text{otherwise}\end{cases}$ $\displaystyle\quad\forall i,j\in\llbracket
1..m\rrbracket,$ (19)

where
$\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}(\mathbf{s})_{i,j}\in\mathbb{S}^{L}$
is the $(i,j)$th submatrix of
$\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}(\mathbf{s})$. Thus
$\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}(\mathbf{s})$ has a block
arrowhead structure. The output of the adjoint operator
$\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}^{\ast}:\mathbb{S}^{Lm}\to\mathbb{R}^{U\times
m}$ may be defined as:

$\displaystyle\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}^{\ast}(\mathbf{S})_{i}=\begin{cases}{\textstyle\sum_{j\in\llbracket
1..m\rrbracket}}\mathsf{\Lambda}_{\operatorname{SOS}}^{\ast}(\mathbf{S}_{j,j})&i=1\\\
\mathsf{\Lambda}_{\operatorname{SOS}}^{\ast}(\mathbf{S}_{1,i})+\mathsf{\Lambda}_{\operatorname{SOS}}^{\ast}(\mathbf{S}_{i,1})&i\neq
1\end{cases}$ $\displaystyle\quad\forall i\in\llbracket 1..m\rrbracket,$ (20)

where
$\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}^{\ast}(\mathbf{S})_{i}\in\mathbb{R}^{U}$
is the $i$th slice of
$\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}^{\ast}(\mathbf{S})$ and
$\mathbf{S}_{i,j}\in\mathbb{R}^{L\times L}$ is the $(i,j)$th block in
$\mathbf{S}$ for all $i,j\in\llbracket 1..m\rrbracket$.

##  4 Efficient barriers for SOS-L2 and SOS-L1

As for ${K}_{\operatorname{SOSPSD}}^{\ast}$ and
${K}_{\operatorname{SOS}\ell_{2}}^{\ast}$, we show that a barrier for
${K}_{\operatorname{SOS}\ell_{1}}^{\ast}$ can be obtained by composing a
linear lifting operator with the $\operatorname{logdet}$ barrier. This is
sufficient to optimize over ${K}_{\operatorname{SOSPSD}}$,
${K}_{\operatorname{SOS}\ell_{2}}$ and ${K}_{\operatorname{SOS}\ell_{1}}$
without high dimensional SDP formulations. However, for
${K}_{\operatorname{SOS}\ell_{2}}^{\ast}$ and
${K}_{\operatorname{SOS}\ell_{1}}^{\ast}$ we can derive improved barriers by
composing nonlinear functions with the $\operatorname{logdet}$ barrier
instead. We show that these compositions are indeed LHSCBs.

###  4.1 SOS-L2

Recall Equation 16b suggests that checking membership in
${K}_{\operatorname{SOS}\ell_{2}}^{\ast}$ amounts to checking positive
definiteness of $\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}(\mathbf{s})$
with side dimension $Lm$. This membership check corresponds to a
_straightforward_ LHSCB with parameter $Lm$ given by
$\mathbf{s}\mapsto-\operatorname{logdet}(\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}(\mathbf{s}))$.
We now show that by working with a Schur complement of
$\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}(\mathbf{s})$, we obtain a
membership check for ${K}_{\operatorname{SOS}\ell_{2}}^{\ast}$ that requires
factorizations of only two matrices with side dimension $L$ and implies an
LHSCB with parameter $2L$.

Let $\mathsf{\Pi}:\mathbb{R}^{U\times m}\to\mathbb{S}^{L}$ return the Schur
complement:

$\displaystyle\mathsf{\Pi}(\mathbf{s})={\mathsf{\Lambda}_{\operatorname{SOS}}}(\mathbf{s}_{1})-{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}{\mathsf{\Lambda}_{\operatorname{SOS}}}(\mathbf{s}_{i}){\mathsf{\Lambda}_{\operatorname{SOS}}}(\mathbf{s}_{1})^{-1}{\mathsf{\Lambda}_{\operatorname{SOS}}}(\mathbf{s}_{i}).$
(21)

By Equations 16b and 21:

$\displaystyle{K}_{\operatorname{SOS}\ell_{2}}^{\ast}$
$\displaystyle=\\{\mathbf{s}\in\mathbb{R}^{U\times
m}:\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}(\mathbf{s})\succeq 0\\}$
(22a) $\displaystyle=\operatorname{cl}\\{\mathbf{s}\in\mathbb{R}^{U\times
m}:\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}(\mathbf{s})\succ 0\\}$ (22b)
$\displaystyle=\operatorname{cl}\left\\{\mathbf{s}\in\mathbb{R}^{U\times
m}:{\mathsf{\Lambda}_{\operatorname{SOS}}}(\mathbf{s}_{1})\succ
0,\mathsf{\Pi}(\mathbf{s})\succ 0\right\\}.$ (22c)

Equation 22c describes a simple membership check. Furthermore, the function
$F:\mathbb{R}^{U\times m}\to\mathbb{R}$ defined by:

$\displaystyle F(\mathbf{s})$
$\displaystyle=-\operatorname{logdet}\left(\mathsf{\Pi}(\mathbf{s})\right)-\operatorname{logdet}({\mathsf{\Lambda}_{\operatorname{SOS}}}(\mathbf{s}_{1}))$
(23a)
$\displaystyle=-\operatorname{logdet}(\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}(\mathbf{s}))+(m-2)\operatorname{logdet}(\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1})),$
(23b)

is a $2L$-LHSCB barrier for ${K}_{\operatorname{SOS}\ell_{2}}$.

###### Theorem 4.1

The function $F$ defined by Equation 23 is a $2L$-LHSCB for
${K}_{\operatorname{SOS}\ell_{2}}^{\ast}$.

###### Proof

It is easy to verify that $F$ is a logarithmically homogeneous barrier, so we
show it is a $2L$-self-concordant barrier for
${K}_{\operatorname{SOS}\ell_{2}}^{\ast}$. We first show that
$\hat{F}:\mathbb{S}_{++}^{L}\times(\mathbb{R}^{L\times L})^{m-1}\to\mathbb{R}$
defined as
$\hat{F}(\mathbf{X}_{1},\ldots,\mathbf{X}_{m})=-\operatorname{logdet}(\mathbf{X}_{1}-{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}\mathbf{X}_{i}\mathbf{X}_{1}^{-1}\mathbf{X}_{i}^{\top})-\operatorname{logdet}(\mathbf{X}_{1})$,
is a $2L$-self-concordant barrier for the cone:

$\displaystyle{K}_{\ell_{2}}^{m}=\operatorname{cl}\left\\{(\mathbf{X}_{1},\ldots,\mathbf{X}_{m})\in\mathbb{S}^{L}_{++}\times(\mathbb{R}^{L\times
L})^{m-1}:\mathbf{X}_{1}-{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}\mathbf{X}_{i}\mathbf{X}_{1}^{-1}\mathbf{X}_{i}^{\top}\succ
0\right\\}.$ (24)

We then argue that $F$ is a composition of $\hat{F}$ with the linear map
$(\mathbf{s}_{1},\ldots,\mathbf{s}_{m})\mapsto(\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1}),\ldots,\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{m}))$
and ${K}_{\operatorname{SOS}\ell_{2}}^{\ast}$ is an inverse image of
${K}_{\ell_{2}}^{m}$ under the same map. Then by Nesterov and Nemirovskii
(1994, Proposition 5.1.1) $F$ is self-concordant.

Let $\Gamma=\mathbb{S}^{L}_{+}\times(\mathbb{R}^{L\times L})^{m-1}$ and
$\mathbf{G}:\operatorname{int}(\Gamma)\to\mathbb{S}^{L}$ be defined as:

$\displaystyle\mathbf{G}(\mathbf{X}_{1},\ldots,\mathbf{X}_{m})=\mathbf{X}_{1}-{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}\mathbf{X}_{i}\mathbf{X}_{1}^{-1}\mathbf{X}_{i}^{\top}.$ (25)

Let us check that $\mathbf{G}$ is $(\mathbb{S}_{+}^{L},1)$-compatible with the
domain $\Gamma$ in the sense of (Nesterov and Nemirovskii, 1994, Definition
5.1.1). This requires that $\mathbf{G}$ is $C^{3}$-smooth on
$\operatorname{int}(\Gamma)$, $\mathbf{G}$ is concave with respect to
$\mathbb{S}_{+}^{L}$, and at each point
$\mathbf{X}=(\mathbf{X}_{1},\ldots,\mathbf{X}_{m})\in\operatorname{int}(\Gamma)$
and any direction
$\mathbf{V}=(\mathbf{V}_{1},\ldots,\mathbf{V}_{m})\in\mathbb{S}^{L}\times(\mathbb{R}^{L\times
L})^{m-1}$ such that
$-\mathbf{X}_{1}\preceq\mathbf{V}_{1}\preceq\mathbf{X}_{1}$, the directional
derivatives of $\mathbf{G}$ satisfy:

$\displaystyle\tfrac{d^{3}\mathbf{G}}{d\mathbf{X}^{3}}[\mathbf{V},\mathbf{V},\mathbf{V}]\preceq-3\tfrac{d^{2}\mathbf{G}}{d\mathbf{X}^{2}}[\mathbf{V},\mathbf{V}].$
(26)

Let $\mathbf{V}\in\mathbb{S}^{L}\times(\mathbb{R}^{L\times L})^{m-1}$. It can
be checked that $\tfrac{d^{3}\mathbf{G}}{d\mathbf{X}^{3}}$ is continuous on
the domain of $\mathbf{G}$ and we have the directional derivatives:

$\displaystyle\tfrac{d^{2}\mathbf{G}}{d\mathbf{X}^{2}}[\mathbf{V},\mathbf{V}]$
$\displaystyle=-2{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}(\mathbf{X}_{i}\mathbf{X}_{1}^{-1}\mathbf{V}_{1}-\mathbf{V}_{i})\mathbf{X}_{1}^{-1}(\mathbf{X}_{i}\mathbf{X}_{1}^{-1}\mathbf{V}_{1}-\mathbf{V}_{i})^{\top},$
(27)
$\displaystyle\tfrac{d^{3}\mathbf{G}}{d\mathbf{X}^{3}}[\mathbf{V},\mathbf{V},\mathbf{V}]$
$\displaystyle=6{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}(\mathbf{X}_{i}\mathbf{X}_{1}^{-1}\mathbf{V}_{1}-\mathbf{V}_{i})\mathbf{X}_{1}^{-1}\mathbf{V}_{1}\mathbf{X}_{1}^{-1}(\mathbf{X}_{i}\mathbf{X}_{1}^{-1}\mathbf{V}_{1}-\mathbf{V}_{i})^{\top}.$
(28)

Since $\mathbf{X}_{1}\succ 0$ in $\operatorname{int}(\Gamma)$,
$-\tfrac{d^{2}\mathbf{G}}{d\mathbf{X}^{2}}[\mathbf{V},\mathbf{V}]\succeq 0$
and so by Nesterov and Nemirovskii (1994, Lemma 5.1.2), $\mathbf{G}$ is
concave with respect to $\mathbb{S}_{+}^{L}$. It remains to show that Equation
26 is satisfied. Since the directional derivatives decouple by each index $i$
in the sum, it is sufficient to show that the inequality is satisfied for each
$i\in\llbracket 2..m\rrbracket$. For this, it is sufficient that:

$\displaystyle
6\mathbf{X}_{1}^{-1}\mathbf{V}_{1}\mathbf{X}_{1}^{-1}\preceq-3\times-2\mathbf{X}_{1}^{-1},$
(29)

for all $-\mathbf{X}_{1}\preceq\mathbf{V}_{1}\preceq\mathbf{X}_{1}$, which
follows since $\mathbf{X}_{1}$ is positive definite on
$\operatorname{int}(\Gamma)$. Now by (Nesterov and Nemirovskii, 1994,
proposition 5.1.7), $\hat{F}$ is a $2L$-LHSCB. The same is true for $F$ by
composing $\hat{F}$ with a linear map. ∎

###  4.2 SOS-L1

By combining Equation 2 and Equation 13, the
${K}_{\operatorname{SOS}\ell_{1}}$ cone admits the semidefinite
representation:

$\displaystyle{K}_{\operatorname{SOS}\ell_{1}}=\left\\{\begin{aligned}
(\mathbf{s}_{1},\ldots,\mathbf{s}_{m})\in\mathbb{R}^{U\times
m}:\exists\mathbf{S}_{1},\mathbf{S}_{2,+},\mathbf{S}_{2,-}\ldots,\mathbf{S}_{m,+},\mathbf{S}_{m,-}\in\mathbb{S}_{+}^{L},\\\
\mathbf{s}_{1}=\mathsf{\Lambda}_{\operatorname{SOS}}^{\ast}(\mathbf{S}_{1})+{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}\mathsf{\Lambda}_{\operatorname{SOS}}^{\ast}(\mathbf{S}_{i,+}+\mathbf{S}_{i,-}),\\\
\mathbf{s}_{i}=\mathsf{\Lambda}_{\operatorname{SOS}}^{\ast}(\mathbf{S}_{i,+})-\mathsf{\Lambda}_{\operatorname{SOS}}^{\ast}(\mathbf{S}_{i,-})\
\forall i\in\llbracket 2..m\rrbracket\end{aligned}\right\\}.$ (30)

Its dual cone is:

$\displaystyle{K}_{\operatorname{SOS}\ell_{1}}^{\ast}=\left\\{(\mathbf{s}_{1},\ldots,\mathbf{s}_{m})\in\mathbb{R}^{U\times
m}:\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1}+\mathbf{s}_{i})\succeq
0,\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1}-\mathbf{s}_{i})\succeq
0\ \forall i\in\llbracket 2..m\rrbracket\right\\}.$ (31)

Equation 31 suggests that checking membership in
${K}_{\operatorname{SOS}\ell_{1}}^{\ast}$ amounts to checking positive
definiteness of $2(m-1)$ matrices of side dimension $L$. This membership check
corresponds to a _straightforward_ LHSCB with parameter $2L(m-1)$ that is
given by
$(\mathbf{s}_{1},\ldots,\mathbf{s}_{m})\mapsto-{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}\operatorname{logdet}(\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1}+\mathbf{s}_{i})\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1}-\mathbf{s}_{i}))$.
We now describe a membership check for
${K}_{\operatorname{SOS}\ell_{1}}^{\ast}$ that requires factorizations of only
$m$ matrices, and implies an LHSCB with parameter $Lm$.

###### Lemma 2

The set
$\\{\mathbf{X}\in\mathbb{S}_{+}^{L},\mathbf{Y}\in\mathbb{S}^{L}:-\mathbf{X}\preceq\mathbf{Y}\preceq\mathbf{X}\\}$
is equal to
${K}_{\ell_{2}}^{2}=\operatorname{cl}\\{\mathbf{X}\in\mathbb{S}_{++}^{L},\mathbf{Y}\in\mathbb{S}^{L}:\mathbf{X}-\mathbf{Y}\mathbf{X}^{-1}\mathbf{Y}\succ
0\\}$.

###### Proof

For inclusion in one direction:

$\displaystyle\operatorname{cl}\left\\{\mathbf{X}\in\mathbb{S}_{++}^{L},\mathbf{Y}\in\mathbb{S}^{L}:\mathbf{X}-\mathbf{Y}\mathbf{X}^{-1}\mathbf{Y}\succ
0\right\\}$ (32a)
$\displaystyle=\left\\{\mathbf{X}\in\mathbb{S}_{+}^{L},\mathbf{Y}\in\mathbb{S}^{L}:\begin{pmatrix}\mathbf{X}&\mathbf{Y}\\\
\mathbf{Y}&\mathbf{X}\end{pmatrix}\succeq 0,\
\begin{pmatrix}\mathbf{X}&-\mathbf{Y}\\\
-\mathbf{Y}&\mathbf{X}\end{pmatrix}\succeq 0\right\\}$ (32b)
$\displaystyle\subseteq\\{\mathbf{X}\in\mathbb{S}_{+}^{L},\mathbf{Y}\in\mathbb{S}^{L}:2\mathbf{v}^{\top}\mathbf{X}\mathbf{v}+2\mathbf{v}^{\top}\mathbf{Y}\mathbf{v}\geq
0,\
2\mathbf{v}^{\top}\mathbf{X}\mathbf{v}-2\mathbf{v}^{\top}\mathbf{Y}\mathbf{v}\geq
0\quad\forall\mathbf{v}\in\mathbb{R}^{L}\\}$ (32c)
$\displaystyle=\\{\mathbf{X}\in\mathbb{S}_{+}^{L},\mathbf{Y}\in\mathbb{S}^{L}:\mathbf{X}+\mathbf{Y}\succeq
0,\mathbf{X}-\mathbf{Y}\succeq 0\\}.$ (32d)

For the other direction, suppose $-\mathbf{X}\prec\mathbf{Y}\prec\mathbf{X}$.
Then $\mathbf{X}\succ 0$, $\mathbf{Y}+\mathbf{X}\succ 0$,
$\mathbf{X}-\mathbf{Y}\succ 0$. Note that
$(\mathbf{Y}+\mathbf{X})\mathbf{X}^{-1}(\mathbf{X}-\mathbf{Y})=\mathbf{X}-\mathbf{Y}\mathbf{X}^{-1}\mathbf{Y}$
is symmetric. Due to Subramanian and Bhagwat (1979, Corollary 1), this product
of three matrices also has nonnegative eigenvalues. We conclude that
$-\mathbf{X}\prec\mathbf{Y}\prec\mathbf{X}$ implies $\mathbf{X}\succ 0$ and
$\mathbf{X}-\mathbf{Y}\mathbf{X}^{-1}\mathbf{Y}\succeq 0$. Since
$-\mathbf{X}\preceq\mathbf{Y}\preceq\mathbf{X}=\operatorname{cl}\left\\{-\mathbf{X}\prec\mathbf{Y}\prec\mathbf{X}\right\\}$,
taking closures gives the result.

∎

By Lemma 2 we can write the dual cone as:

$\displaystyle{K}_{\operatorname{SOS}\ell_{1}}^{\ast}=\operatorname{cl}\left\\{\begin{aligned}
(\mathbf{s}_{1},\ldots,\mathbf{s}_{m})\in\mathbb{R}^{U\times
m}:\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1})\succ 0,\\\
\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1})-\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{i})\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1})^{-1}\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{i})\succ
0,\forall i\in\llbracket 2..m\rrbracket\end{aligned}\right\\}.$ (33)

###### Theorem 4.2

The function $F:\mathbb{R}^{U\times m}\to\mathbb{R}$ given by:

$\displaystyle\begin{split}F(\mathbf{s})&=-{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}\operatorname{logdet}(\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1})-\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{i})\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1})^{-1}\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{i}))-{}\\\
&\hphantom{{}={}}\operatorname{logdet}(\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1}))\end{split}$
(34)

is an $Lm$-LHSCB for ${K}_{\operatorname{SOS}\ell_{1}}^{\ast}$.

###### Proof

It is easy to verify that $F$ is a logarithmically homogeneous barrier, and we
show it is an $Lm$-self-concordant barrier. As in Theorem 4.1, we define an
auxiliary cone:

$\displaystyle{K}_{\ell_{\infty}}^{m}$
$\displaystyle=\\{(\mathbf{X}_{1},\ldots,\mathbf{X}_{m})\in\mathbb{S}_{+}^{L}\times(\mathbb{R}^{L\times
L})^{m-1}:(\mathbf{X}_{1},\mathbf{X}_{i})\in{K}_{\ell_{2}}^{2}\forall
i\in\llbracket 2..m\rrbracket\\}.$ (35)

Let $\hat{F}:\mathbb{S}_{++}^{L}\times(\mathbb{R}^{L\times
L})^{m-1}\to\mathbb{R}$ be defined as
$\hat{F}(\mathbf{X}_{1},\ldots,\mathbf{X}_{m})=-{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}\operatorname{logdet}(\mathbf{X}_{1}-\mathbf{X}_{i}\mathbf{X}_{1}^{-1}\mathbf{X}_{i}^{\top})-\operatorname{logdet}(\mathbf{X}_{1})$.
We argue that $\hat{F}$ is an $Lm$-self-concordant barrier for
${K}_{\ell_{\infty}}^{m}$. $F$ is a composition of $\hat{F}$ with the same
linear map used in Theorem 4.1 and self-concordance of $F$ then follows by the
same reasoning.

Let $\Gamma=\mathbb{S}_{+}^{L}\times(\mathbb{R}^{L\times L})^{m-1}$ and
$\mathbf{H}:\operatorname{int}(\Gamma)\to(\mathbb{S}_{+}^{L})^{m-1}$ be
defined by:

$\displaystyle\mathbf{H}(\mathbf{X}_{1},\ldots,\mathbf{X}_{m})=\left(\mathbf{X}_{1}-\mathbf{X}_{2}\mathbf{X}_{1}^{-1}\mathbf{X}_{2}^{\top},\ldots,\mathbf{X}_{1}-\mathbf{X}_{m}\mathbf{X}_{1}^{-1}\mathbf{X}_{m}^{\top}\right).$
(36)

We claim that $\mathbf{H}$ is $((\mathbb{S}_{+}^{L})^{m-1},1)$-compatible with
the domain $\Gamma$. This amounts to showing that for all $i\in\llbracket
2..m\rrbracket$, the mapping
$\mathbf{H}_{i}:\mathbb{S}_{++}^{L}\times\mathbb{R}^{L\times
L}\to\mathbb{S}^{L}$,
$\mathbf{H}_{i}(\mathbf{X})=\mathbf{X}_{1}-\mathbf{X}_{i}\mathbf{X}_{1}^{-1}\mathbf{X}_{i}^{\top}$
is $(\mathbb{S}_{+}^{L},1)$-compatible with the domain
$\mathbb{S}_{+}^{L}\times\mathbb{R}^{L\times L}$ (the requirements for
compatibility decouple for each $i$). The latter holds since $\mathbf{H}_{i}$
is equivalent to the function $\mathbf{G}$ from Theorem 4.1 with $m=2$. Then
by Nesterov and Nemirovskii (1994, Lemma 5.1.7), $\hat{F}$ is an $Lm$-self-
concordant barrier. ∎

##  5 Implementation details

###  5.1 SOS-PSD

To draw comparisons between ${K}_{\operatorname{SOSPSD}}$ and its SOS
representation Equation 5, let us outline how we modify the representation of
${K}_{\operatorname{SOS}}$ from Section 1.1 to account for sparsity in a
polynomial of the form $\mathbf{y}^{\top}\mathbf{Q}(\mathbf{x})\mathbf{y}$.

Suppose we have interpolation points $\mathbf{t}_{i\in\llbracket
1..U\rrbracket}$ to represent ${K}_{\operatorname{SOS}}$ in
$\mathbb{R}[\mathbf{x}]_{n,2d}$. Let $\underline{\mathbf{t}}_{i\in\llbracket
1..\operatorname{sd}(m)\rrbracket}$ represent distinct points in
$\mathbb{R}^{m}$, where at most two components in $\underline{\mathbf{t}}_{i}$
equal one and the rest equal zero, for all $i\in\llbracket
1..\operatorname{sd}(m)\rrbracket$. We can check that the Cartesian product of
$\mathbf{t}_{i\in\llbracket 1..U\rrbracket}$ and
$\underline{\mathbf{t}}_{i\in\llbracket 1..\operatorname{sd}(m)\rrbracket}$,
given by
$\\{(\mathbf{t}_{1},\underline{\mathbf{t}}_{1}),\ldots,(\mathbf{t}_{U},\underline{\mathbf{t}}_{\operatorname{sd}(m)})\\}$
gives $U\operatorname{sd}(m)$ unisolvent points. The polynomial
$\mathbf{y}^{\top}\mathbf{Q}(\mathbf{x})\mathbf{y}$ from Equation 5 is then
characterized by its evaluation at these these points.

Now let $\underline{p}_{i\in\llbracket 1..m\rrbracket}$ be polynomials in
$\mathbb{R}[\mathbf{y}]_{m,1}$ such that
$\underline{p}_{i}(y_{1},\ldots,y_{m})=y_{i}$ for all $i\in\llbracket
1..m\rrbracket$. Recall that for ${K}_{\operatorname{SOS}}$ in
$\mathbb{R}[\mathbf{x}]_{n,2d}$, $\mathbf{P}$ is defined by
$P_{u,\ell}=p_{\ell}(\mathbf{t}_{u})$ for all $u\in\llbracket
1..U\rrbracket,\ell\in\llbracket 1..L\rrbracket$. The new matrix
$\underline{\mathbf{P}}$ for the $U\operatorname{sd}(m)$-dimensional SOS cone
is given by $\underline{\mathbf{P}}=\mathbf{Y}\otimes_{K}\mathbf{P}$, where
$\mathbf{Y}\in\mathbb{R}^{\operatorname{sd}(m)\times m}$, is a Vandermonde
matrix of the polynomials $\underline{p}_{i\in\llbracket 1..m\rrbracket}$ and
points $\underline{\mathbf{t}}_{i\in\llbracket
1..\operatorname{sd}{(m)}\rrbracket}$. Finally, the lifting operator
$\underline{\mathsf{\Lambda}_{\operatorname{SOS}}}(\mathbf{s})=\underline{\mathbf{P}}^{\top}\operatorname{diag}(\mathbf{s})\underline{\mathbf{P}}$
is of the same form as $\mathsf{\Lambda}_{\operatorname{SOS}}$.

###### Lemma 3

Computing the Hessian of the LHSCB of ${K}_{\operatorname{SOSPSD}}$ requires
$\mathcal{O}(LU^{2}m^{3})$ time while the Hessian of the LHSCB in the SOS
formulation requires $\mathcal{O}(LU^{2}m^{5})$ time if $m<L<U$.

###### Proof

Define $\mathbf{T}_{i,j}:\mathbb{R}^{U\times m\times m}\to\mathbb{R}^{U\times
U}$ for all $i,j\in\llbracket 1..m\rrbracket$:

$\displaystyle\mathbf{T}_{i,j}(\mathbf{S})=\mathbf{P}\left(\mathsf{\Lambda}_{\operatorname{SOSPSD}}(\mathbf{S})^{-1}\right)_{i,j}\mathbf{P}^{\top}=\left((\mathbf{I}_{m}\otimes_{K}\mathbf{P})\mathsf{\Lambda}_{\operatorname{SOSPSD}}(\mathbf{S})^{-1}(\mathbf{I}_{m}\otimes_{K}\mathbf{P})^{\top}\right)_{i,j},$
(37)

where the indices ${i,j}$ reference a $U\times U$ submatrix. For all
$i,i^{\prime},j,j^{\prime}\in\llbracket 1..m\rrbracket$,
$u,u^{\prime}\in\llbracket 1..U\rrbracket$, the gradient and Hessian of the
barrier are:222In practice we only store coefficients from the lower triangle
of a polynomial matrix and account for this in the derivatives.

$\displaystyle\frac{dF}{dS_{i,j,u}}$
$\displaystyle=-\mathbf{T}_{i,j}(\mathbf{S})_{u,u},$ (38)
$\displaystyle\frac{d^{2}F}{dS_{i,j,u}dS_{i^{\prime},j^{\prime},u^{\prime}}}$
$\displaystyle=\mathbf{T}_{i,j^{\prime}}(\mathbf{S})_{u,u^{\prime}}\mathbf{T}_{j,i^{\prime}}(\mathbf{S})_{u,u^{\prime}},$
(39)

The lifting operator $\mathsf{\Lambda}_{\operatorname{SOSPSD}}$ can be
computed blockwise in $\mathcal{O}(L^{2}Um^{2})$ operations, while
$\underline{\mathsf{\Lambda}_{\operatorname{SOS}}}$ requires
$\mathcal{O}(L^{2}Um^{4})$ operations. To avoid computing the explicit inverse
$\mathsf{\Lambda}_{\operatorname{SOSPSD}}(\mathbf{s})^{-1}$, we use a Cholesky
factorization
$\mathsf{\Lambda}_{\operatorname{SOSPSD}}=\mathbf{L}\mathbf{L}^{\top}$ to form
a block triangular matrix
$\mathbf{V}=\mathbf{L}^{-1}(\mathbf{I}_{m}\otimes_{K}\mathbf{P})$ in
$\mathcal{O}(L^{2}Um^{2})$ operations, while computing the larger
$\underline{\mathbf{V}}=\underline{\mathbf{L}}^{-1}\underline{\mathbf{P}}$
where
$\underline{\mathsf{\Lambda}_{\operatorname{SOS}}}(\mathbf{s})=\underline{\mathbf{L}}\underline{\mathbf{L}}^{\top}$
for the ${K}_{\operatorname{SOS}}$ formulation requires
$\mathcal{O}(L^{2}Um^{4})$ operations. We use the product
$\mathbf{V}\mathbf{V}^{\top}$ to build $\mathbf{T}_{i,j}$ for all
$i,j\in\llbracket 1..m\rrbracket$ in $\mathcal{O}(LU^{2}m^{3})$ operations,
while calculating $\underline{\mathbf{V}}\underline{\mathbf{V}}^{\top}$
requires $\mathcal{O}(LU^{2}m^{5})$ operations. Once the blocks
$\mathbf{T}_{i,j}$ are built, the time complexity to compute the gradient and
Hessian are the same for ${K}_{\operatorname{SOSPSD}}$ as for
${K}_{\operatorname{SOS}}$. ∎

###  5.2 SOS-L2

###### Lemma 4

The Hessian of the LHSCB of ${K}_{\operatorname{SOS}\ell_{2}}$ requires
$\mathcal{O}(LU^{2}m^{2})$ time while the Hessian of the LHSCB in the SOS
formulation requires $\mathcal{O}(LU^{2}m^{5})$ time if $m<L<U$.

###### Proof

Let $\mathbf{T}_{i,j}:\mathbb{R}^{U\times m}\to\mathbb{R}^{U\times U}$ be
defined as in Equation 37 for all $i,j\in\llbracket 1..m\rrbracket$, but
replacing $\mathsf{\Lambda}_{\operatorname{SOSPSD}}$ with
$\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}$. Let
$\mathbf{R}=\mathbf{P}(\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1}))^{-1}\mathbf{P}^{\top}$.
For all $i,i^{\prime}\in\llbracket 1..m\rrbracket$, $u,u^{\prime}\in\llbracket
1..U\rrbracket$, the gradient and Hessian of the barrier are:

$\displaystyle\frac{dF}{ds_{i,u}}$
$\displaystyle=\begin{cases}-{\textstyle\sum_{j\in\llbracket
1..m\rrbracket}}\mathbf{T}_{j,j}(\mathbf{s})_{u,u}+(m-2)\mathbf{R}_{u,u}&i=1\\\
-2\mathbf{T}_{i,1}(\mathbf{s})_{u,u}&i\neq 1,\end{cases}$ (40)
$\displaystyle\begin{split}\frac{d^{2}F}{ds_{i,u}ds_{i^{\prime},u^{\prime}}}&=\begin{cases}{\textstyle\sum_{j\in\llbracket
1..m\rrbracket,k\in\llbracket
1..m\rrbracket}}\left(\mathbf{T}_{j,k}(\mathbf{s})_{u,u^{\prime}}\right)^{2}-(m-2)\left(\mathbf{R}_{u,u^{\prime}}\right)^{2}&i=i^{\prime}=1\\\
2{\textstyle\sum_{j\in\llbracket
1..m\rrbracket}}\mathbf{T}_{j,1}(\mathbf{s})_{u,u^{\prime}}\mathbf{T}_{j,i^{\prime}}(\mathbf{s})_{u,u^{\prime}}&i=1,i^{\prime}\neq
1\\\ 2{\textstyle\sum_{j\in\llbracket
1..m\rrbracket}}\mathbf{T}_{1,j}(\mathbf{s})_{u,u^{\prime}}\mathbf{T}_{i,j}(\mathbf{s})_{u,u^{\prime}}&i\neq
1,i^{\prime}=1\\\
2\left(\mathbf{T}_{1,1}(\mathbf{s})_{u,u^{\prime}}\mathbf{T}_{i,i^{\prime}}(\mathbf{s})_{u,u^{\prime}}+\mathbf{T}_{i,1}(\mathbf{s})_{u,u^{\prime}}\mathbf{T}_{1,i^{\prime}}(\mathbf{s})_{u,u^{\prime}}\right)&i\neq
1,i^{\prime}\neq 1.\end{cases}\end{split}$ (41)

To compute the blocks $\mathbf{T}_{i,j}(\mathbf{s})$ we require an inverse of
the matrix $\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}(\mathbf{s})$. It can
be verified that:

$\displaystyle\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}(\mathbf{s})^{-1}=\begin{bmatrix}\mathbf{0}&\\\
&\mathbf{I}_{m-1}\otimes_{K}\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1})^{-1}\end{bmatrix}+\mathbf{U}{\mathsf{\Pi}}(\mathbf{s})^{-1}\mathbf{U}^{\top},$
(42)

where,

$\displaystyle\mathbf{U}^{\top}$
$\displaystyle=\begin{bmatrix}-\mathbf{I}_{L}&\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{2})\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1})^{-1}&\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{3})\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1})^{-1}&\ldots&\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{m})\mathsf{\Lambda}_{\operatorname{SOS}}(\mathbf{s}_{1})^{-1}\end{bmatrix}.$

Computing $\mathbf{T}_{i,j}$ for all $i,j\in\llbracket 1..m\rrbracket$ is the
most expensive step in obtaining the Hessian and we do this in
$\mathcal{O}(LU^{2}m^{2})$ operations. The complexity of computing the Hessian
in the SOS formulation of ${K}_{\operatorname{{Arw}}\operatorname{SOSPSD}}$ is
the same as in the SOS formulation of ${K}_{\operatorname{SOSPSD}}$ since the
cones have the same dimension. ∎

###  5.3 SOS-L1

###### Lemma 5

The Hessians of the LHSCBs of ${K}_{\operatorname{SOS}\ell_{1}}$ and its SOS
formulation require $\mathcal{O}(LU^{2}m)$ time if $m<L<U$.

###### Proof

Let $\mathbf{T}_{i,j}(\mathbf{s}):\mathbb{R}^{U\times m}\to\mathbb{S}^{U}$ for
all $i\in\llbracket 2..m\rrbracket,j\in\\{1,2\\}$ be defined by:

$\displaystyle\mathbf{T}_{i,j}(\mathbf{s})$
$\displaystyle=\mathbf{P}\left(\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}((s_{1},s_{i}))^{-1}\right)_{1,j}\mathbf{P}^{\top}$
(43)
$\displaystyle=\left((\mathbf{I}_{m}\otimes_{K}\mathbf{P})\mathsf{\Lambda}_{\operatorname{SOS}\ell_{2}}((s_{1},s_{i}))^{-1}(\mathbf{I}_{m}\otimes_{K}\mathbf{P})^{\top}\right)_{1,j}.$
(44)

For all $i,i^{\prime}\in\llbracket 1..m\rrbracket$, $u,u^{\prime}\in\llbracket
1..U\rrbracket$, the gradient and Hessian of the barrier are:

$\displaystyle\frac{dF}{ds_{i,u}}$
$\displaystyle=\begin{cases}-2{\textstyle\sum_{j\in\llbracket
2..m\rrbracket}}\mathbf{T}_{j,1}(\mathbf{s})_{u,u}+(m-2)\mathbf{R}_{u,u}&i=1\\\
-2\mathbf{T}_{i,2}(\mathbf{s})_{u,u}&i\neq 1,\end{cases}$ (45)
$\displaystyle\frac{d^{2}F}{ds_{i,u}ds_{i^{\prime},u^{\prime}}}$
$\displaystyle=\begin{cases}2{\textstyle\sum_{j\in\llbracket
2..m\rrbracket,k\in\\{1,2\\}}}\left(\mathbf{T}_{j,k}(\mathbf{s})_{u,u^{\prime}}\right)^{2}-(m-2)(\mathbf{R}_{u,u^{\prime}})^{2}&i=i^{\prime}=1\\\
4\mathbf{T}_{i,1}(\mathbf{s})_{u,u^{\prime}}\mathbf{T}_{i,2}(\mathbf{s})_{u,u^{\prime}}&i\neq
1,i^{\prime}=1\\\
4\mathbf{T}_{i^{\prime},1}(\mathbf{s})_{u,u^{\prime}}\mathbf{T}_{i^{\prime},2}(\mathbf{s})_{u,u^{\prime}}&i=1,i^{\prime}\neq
1\\\
2{\textstyle\sum_{k\in\\{1,2\\}}}(\mathbf{T}_{i,k}(\mathbf{s})_{u,u^{\prime}})^{2}&i=i^{\prime}\neq
1\\\ 0&\text{otherwise}.\end{cases}$ (46)

Calculating $\mathbf{T}_{i,j}(\mathbf{s})$ for all $i\in\llbracket
2..m\rrbracket,j\in\\{1,2\\}$ can be done in $\mathcal{O}(LU^{2}m)$
operations. The Hessian of the SOS formulation requires computing
$\mathcal{O}(m)$ Hessians of SOS cones that require $\mathcal{O}(LU^{2})$
time. We use the block arrowhead structure of the Hessian when applying its
inverse similarly to Equation 42. ∎

##  6 Numerical example

For each cone
$({K}_{\operatorname{SOSPSD}},{K}_{\operatorname{SOS}\ell_{2}},{K}_{\operatorname{SOS}\ell_{1}})$
we compare the computational time to solve a simple example with its SOS
formulation from Section 2. We use an example analogous to the polynomial
envelope problem from (Papp and Yildiz, 2019, Section 7.2), but replace the
nonnegativity constraint by a conic inequality. Let $q_{i\in\llbracket
2..m\rrbracket}(\mathbf{x})$ be randomly generated polynomials in
$\mathbb{R}_{n,2d_{r}}[\mathbf{x}]$. We seek a polynomial that gives the
tightest approximation to the $\ell_{1}$ or $\ell_{2}$ norm of
$\left(q_{2}(\mathbf{x}),\ldots,q_{m}(\mathbf{x})\right)$ for all
$\mathbf{x}\in[-1,1]^{n}$:

$\displaystyle\min_{q_{1}(\mathbf{x})\in\mathbb{R}_{n,2d}[\mathbf{x}]}\int_{[-1,1]^{n}}q_{1}(\mathbf{x})d\mathbf{x}$
$\displaystyle:$ (47a) $\displaystyle q_{1}(\mathbf{x})$
$\displaystyle\geq||(q_{2}(\mathbf{x}),\ldots,q_{m}(\mathbf{x}))||_{p}$
$\displaystyle\forall\mathbf{x}\in[-1,1]^{n},$ (47b)

with $p\in\\{1,2\\}$ in Equation 47b.

To restrict Equation 47b over $[-1,1]^{n}$, we use _weighted sum of squares_
(WSOS) formulations. A polynomial $q(\mathbf{x})$ is WSOS with respect to
weights $g_{i\in\llbracket 1..K\rrbracket}(\mathbf{x})$ if it can be expressed
in the form of $q(\mathbf{x})={\textstyle\sum_{i\in\llbracket
1..K\rrbracket}}g_{i}(\mathbf{x})p_{i}(\mathbf{x})$, where $p_{i\in\llbracket
1..K\rrbracket}(\mathbf{x})$ are SOS. Papp and Yildiz (2019, Section 6) show
that the dual WSOS cone (we will write ${K}_{\operatorname{WSOS}}^{\ast}$) may
be represented by an intersection of ${K}_{\operatorname{SOS}}^{\ast}$ cones.
We represent the dual _weighted_ cones ${K}_{\operatorname{WSOSPSD}}^{\ast}$,
${K}_{\operatorname{WSOS}\ell_{2}}^{\ast}$ and
${K}_{\operatorname{WSOS}\ell_{1}}^{\ast}$ analogously using intersections of
${K}_{\operatorname{SOSPSD}}^{\ast}$,
${K}_{\operatorname{SOS}\ell_{2}}^{\ast}$ and
${K}_{\operatorname{SOS}\ell_{1}}^{\ast}$ respectively.

Let $\mathbf{f}_{i\in\llbracket 1..m\rrbracket}$ denote the coefficients of
$q_{i\in\llbracket 1..m\rrbracket}(\mathbf{x})$ and let
$\mathbf{w}\in\mathbb{R}^{U}$ be a vector of quadrature weights on
$[-1,1]^{n}$. A low dimensional representation of Equation 47 may be written
as:

$\displaystyle\min_{\mathbf{f}_{1}\in\mathbb{R}^{U}}\mathbf{w}^{\top}\mathbf{f}_{1}$
$\displaystyle:$ (48a) $\displaystyle(\mathbf{f}_{1},\ldots,\mathbf{f}_{m})$
$\displaystyle\in{K},$ (48b)

where ${K}$ is ${K}_{\operatorname{WSOS}\ell_{2}}$ or
${K}_{\operatorname{WSOS}\ell_{1}}$. If $p=2$, we compare the
${K}_{\operatorname{WSOS}\ell_{2}}$ formulation with two alternative
formulations involving ${K}_{\operatorname{{Arw}}\operatorname{SOSPSD}}$. We
use either ${K}_{\operatorname{WSOSPSD}}$ to model
${K}_{\operatorname{{Arw}}\operatorname{SOSPSD}}$ as implied in Equation 9, or
${K}_{\operatorname{WSOS}}$ as in Equation 7. For $p=1$, we build an SOS
formulation by replacing Equation 48 with:

$\displaystyle\min_{\mathbf{f}_{1},\mathbf{g}_{2},\ldots,\mathbf{g}_{m},\mathbf{h}_{2},\ldots,\mathbf{h}_{m}\in\mathbb{R}^{U}}\mathbf{w}^{\top}\mathbf{f}_{1}$
$\displaystyle:$ (49a)
$\displaystyle\mathbf{f}_{1}-{\textstyle\sum_{i\in\llbracket
2..m\rrbracket}}\mathbf{g}_{i}-\mathbf{h}_{i}$
$\displaystyle\in{K}_{\operatorname{WSOS}},$ (49b)
$\displaystyle\mathbf{f}_{i}-\mathbf{g}_{i}+\mathbf{h}_{i}$ $\displaystyle=0$
$\displaystyle\forall i\in\llbracket 2..m\rrbracket,$ (49c)
$\displaystyle\mathbf{g}_{i},\mathbf{h}_{i}$
$\displaystyle\in{K}_{\operatorname{WSOS}}$ $\displaystyle\forall
i\in\llbracket 2..m\rrbracket.$ (49d)

We select interpolation points using a heuristic adapted from (Papp and
Yildiz, 2019; Sommariva and Vianello, 2009). We uniformly sample $N$
interpolation points, where $N\gg U$. We form a Vandermonde matrix of the same
structure as the matrix $\mathbf{P}$ used to construct the lifting operator,
but using the $N$ sampled points for rows. We perform a QR factorization and
use the first $U$ indices from the permutation vector of the factorization to
select $U$ out of $N$ rows to keep.

All experiments are performed on hardware with an AMD Ryzen 9 3950X 16-Core
Processor (32 threads) and 128GB of RAM, running Ubuntu 20.10, and Julia 1.6
(Bezanson et al., 2017). Optimization models are built using JuMP (Lubin and
Dunning, 2015) and solved with Hypatia 0.20 (Coey et al., 2020). We use
default settings in Hypatia and set relative optimality and feasibility
tolerances to $10^{-7}$. The termination status (_st_) columns of the tables
use the following codes to classify solve runs:

co

the solver claims the primal-dual certificate returned is optimal given its
numerical tolerances,

tl

a limit of 1800 seconds is reached,

rl

a limit of approximately $120$GB of RAM is reached,

sp

the solver terminates due to slow progress during iterations,

er

the solver reports a different numerical error,

sk

we skip the instance because the solver reached a time or RAM limit on a
smaller instance.

In Tables 2 and 3, we show results for $n\in\\{1,4\\}$ and varying values of
$d_{r}$ and $m$. If $p=1$, we let $d=d_{r}$, where the maximum degree of
$q_{1}(\mathbf{x})$ is $2d$. If $p=2$, we vary $d\in\\{d_{r},2d_{r}\\}$ and
add an additional column _obj_ in Table 2 to show the ratio of the objective
value under the ${K}_{\operatorname{WSOS}}$ (or equivalently
${K}_{\operatorname{WSOSPSD}}$) formulation divided by the objective value
under the ${K}_{\operatorname{WSOS}\ell_{2}}$ formulation. Note that in our
setup, the dimension of ${K}_{\operatorname{WSOS}\ell_{2}}$ only depends on
$d$. A more flexible implementation could allow polynomial components to have
different degrees in ${K}_{\operatorname{WSOS}\ell_{2}}$ for the $d=2d_{r}$
case.

For $p=2$ and $d=2d_{r}$, the difference in objective values between
${K}_{\operatorname{WSOS}\ell_{2}}$ and alternative formulations is less than
$1\%$ across all converged instances. For $p=2$ and $d=d_{r}$, the difference
in the objective values is around $10$–$43\%$ across converged instances.
However, the solving times for ${K}_{\operatorname{WSOS}\ell_{2}}$ with
$d=2d_{r}$ are sometimes faster than the solving times of alternative
formulations with $d=d_{r}$ and equal values of $n$, $m$, and $d_{r}$. This
suggests that it may be beneficial to use ${K}_{\operatorname{WSOS}\ell_{2}}$
in place of SOS formulations, but with higher maximum degree in the
${K}_{\operatorname{WSOS}\ell_{2}}$ cone. The solving times using
${K}_{\operatorname{WSOSPSD}}$ are slightly faster than the solving times
using ${K}_{\operatorname{WSOS}}$. For the case where $p=1$, the
${K}_{\operatorname{WSOS}\ell_{1}}$ formulation is faster than the
${K}_{\operatorname{WSOS}}$ formulation, particularly for larger values of
$m$. We also observe that the number of iterations the algorithm takes for
${K}_{\operatorname{WSOS}\ell_{2}}$ compared to alternative formulations
varies, but larger for ${K}_{\operatorname{WSOS}\ell_{1}}$ compared to the
alternative SOS formulation.

|  |  |  | ${K}_{\operatorname{SOS}\ell_{2}}$ | ${K}_{\operatorname{SOS}}$ | ${K}_{\operatorname{SOSPSD}}$ |
---|---|---|---|---|---|---|---
$n$ | $d_{r}$ | $m$ | $d$ | st | iter | time | st | iter | time | st | iter | time | obj
1 | 20 | 4 | 20 | co | 17 | .17 | co | 22 | .78 | co | 18 | .59 | .88
40 | co | 25 | .77 | co | 27 | 4.7 | co | 22 | 3.8 | .99
8 | 20 | co | 18 | .42 | co | 27 | 9.2 | co | 21 | 6.9 | .83
40 | co | 28 | 2.7 | co | 28 | 43. | co | 22 | 30. | 1.0
16 | 20 | co | 19 | 1.5 | co | 26 | 111. | co | 20 | 77. | .79
40 | co | 30 | 12. | co | 32 | 812. | co | 25 | 555. | 1.0
32 | 20 | co | 20 | 5.9 | tl | 18 | 1829. | tl | 18 | 1870. | $\ast$
40 | co | 31 | 50. | tl | 2 | 2147. | tl | $\ast$ | $\ast$ | $\ast$
64 | 20 | co | 21 | 26. | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | $\ast$
40 | co | 32 | 205. | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | $\ast$
40 | 4 | 40 | co | 21 | .62 | co | 27 | 4.5 | co | 22 | 3.6 | .85
80 | co | 31 | 4.1 | co | 33 | 26. | co | 27 | 25. | .99
8 | 40 | co | 21 | 2.0 | co | 28 | 41. | co | 22 | 27. | .82
80 | co | 34 | 15. | co | 34 | 282. | co | 28 | 218. | .99
16 | 40 | co | 23 | 8.1 | co | 29 | 664. | co | 23 | 464. | .78
80 | co | 37 | 60. | tl | 12 | 1864. | tl | 12 | 1811. | $\ast$
32 | 40 | co | 24 | 33. | tl | 2 | 2142. | tl | $\ast$ | $\ast$ | $\ast$
80 | co | 38 | 252. | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | $\ast$
64 | 40 | co | 26 | 155. | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | $\ast$
80 | co | 38 | 1441. | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | $\ast$
4 | 2 | 4 | 2 | co | 18 | .46 | co | 27 | 3.2 | co | 23 | 2.8 | .75
4 | co | 38 | 87. | co | 54 | 480. | co | 48 | 404. | 1.0
8 | 2 | co | 18 | 1.7 | co | 32 | 40. | co | 28 | 35. | .63
4 | co | 28 | 168. | tl | 13 | 1894. | tl | 14 | 1936. | $\ast$
16 | 2 | co | 17 | 6.5 | co | 41 | 830. | co | 35 | 785. | .57
4 | co | 27 | 644. | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | $\ast$
32 | 2 | co | 17 | 27. | tl | 5 | 2029. | tl | 3 | 1808. | $\ast$
4 | tl | 15 | 1838. | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | $\ast$
4 | 4 | 4 | co | 28 | 79. | co | 44 | 441. | co | 38 | 369. | .69
8 | tl | $\ast$ | $\ast$ | rl | $\ast$ | $\ast$ | rl | $\ast$ | $\ast$ | $\ast$
8 | 4 | co | 28 | 263. | tl | 13 | 1872. | tl | 14 | 1850. | $\ast$
4 | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | $\ast$
16 | 4 | co | 28 | 1095. | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | $\ast$
4 | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | $\ast$
32 | 4 | tl | 9 | 1868. | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | $\ast$
4 | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | sk | $\ast$ | $\ast$ | $\ast$
Table 2: Solve time in seconds and number of iterations (iter) for instances with $p=2$. |  |  | ${K}_{\operatorname{SOS}\ell_{1}}$ | ${K}_{\operatorname{SOS}}$
---|---|---|---|---
$n$ | $d$ | $m$ | st | iter | time | st | iter | time
1 | 40 | 8 | co | 25 | 1.3 | co | 18 | .63
16 | co | 32 | 3.4 | co | 23 | 2.9
32 | co | 38 | 8.0 | co | 23 | 17.
64 | co | 44 | 18. | co | 23 | 106.
128 | co | 52 | 46. | co | 24 | 708.
80 | 8 | co | 33 | 6.5 | co | 24 | 3.9
16 | co | 39 | 16. | co | 24 | 18.
32 | co | 46 | 36. | co | 25 | 110.
64 | co | 54 | 93. | co | 25 | 699.
128 | co | 63 | 232. | tl | $\ast$ | $\ast$
4 | 2 | 8 | co | 23 | .95 | co | 21 | .50
16 | co | 26 | 2.1 | co | 21 | 1.9
32 | co | 29 | 5.2 | co | 22 | 12.
64 | co | 36 | 13. | co | 23 | 71.
128 | sp | 51 | 49. | co | 24 | 480.
4 | 4 | co | 35 | 40. | co | 29 | 18.
8 | co | 40 | 91. | co | 29 | 72.
16 | co | 46 | 251. | co | 30 | 388.
32 | co | 54 | 589. | tl | 9 | 1826.
64 | co | 63 | 1504. | sk | $\ast$ | $\ast$
Table 3: Solve time in seconds and number of iterations (iter) for instances
with $p=1$.

##  7 Conclusions

SOS generalizations of PSD, $\ell_{2}$-norm and $\ell_{1}$-norm constraints
can be modeled using specialized cones that are simple to use in a generic
interior point algorithm. The characterizations of
${K}_{\operatorname{SOSPSD}}$ and ${K}_{\operatorname{SOS}\ell_{2}}$ rely on
ideas from Papp and Alizadeh (2013) as well as the use of a Lagrange
polynomial basis for efficient oracles in the multivariate case. For the
${K}_{\operatorname{SOSPSD}}$ barrier, the complexity of evaluating the
Hessian is reduced by a factor of $\mathcal{O}(m^{2})$ from the SOS
formulation barrier. This does not result in significant speed improvements
since Hessian evaluations are not the bottleneck in an interior point
algorithm. In contrast, the dimension and barrier parameter of the
${K}_{\operatorname{SOS}\ell_{2}}$ and ${K}_{\operatorname{SOS}\ell_{1}}$
cones are lower compared to their SOS formulations, and the complexity of
evaluating the Hessian of the ${K}_{\operatorname{SOS}\ell_{2}}$ barrier is
reduced by a factor of $\mathcal{O}(m^{3})$ from its SOS formulation. Although
we did not see the number of iterations decrease in practice for both
${K}_{\operatorname{SOS}\ell_{2}}$ and ${K}_{\operatorname{SOS}\ell_{1}}$
compared to their SOS formulations, the total solving time was generally lower
in both cases. While there is no penalty in using lower dimensional
representations of SOS-L1 constraints, SOS-L2 formulations give rise to more
conservative restrictions than higher dimensional SOS formulations, which is
observable in practice.

## References

  * Alizadeh and Goldfarb (2003) Alizadeh F, Goldfarb D (2003) Second-order cone programming. Mathematical programming 95(1):3–51
  * Aylward et al. (2007) Aylward EM, Itani SM, Parrilo PA (2007) Explicit SOS decompositions of univariate polynomial matrices and the Kalman-Yakubovich-Popov lemma. In: 2007 46th IEEE Conference on Decision and Control, IEEE, pp 5660–5665
  * Aylward et al. (2008) Aylward EM, Parrilo PA, Slotine JJE (2008) Stability and robustness analysis of nonlinear systems via contraction metrics and sos programming. Automatica 44(8):2163–2170
  * Bezanson et al. (2017) Bezanson J, Edelman A, Karpinski S, Shah VB (2017) Julia: A fresh approach to numerical computing. SIAM review 59(1):65–98
  * Blekherman et al. (2012) Blekherman G, Parrilo PA, Thomas RR (2012) Semidefinite optimization and convex algebraic geometry. SIAM
  * Coey et al. (2020) Coey C, Kapelevich L, Vielma JP (2020) Towards practical generic conic optimization. arXiv preprint arXiv:200501136
  * Doherty et al. (2004) Doherty AC, Parrilo PA, Spedalieri FM (2004) Complete family of separability criteria. Physical Review A 69(2):022308
  * Genin et al. (2003) Genin Y, Hachez Y, Nesterov Y, Van Dooren P (2003) Optimization problems over positive pseudopolynomial matrices. SIAM Journal on Matrix Analysis and Applications 25(1):57–79
  * Hall (2019) Hall G (2019) Engineering and business applications of sum of squares polynomials. arXiv preprint arXiv:190607961
  * Hoffman and Withers (1988) Hoffman ME, Withers WD (1988) Generalized Chebyshev polynomials associated with affine Weyl groups. Transactions of the American Mathematical Society 308(1):91–104
  * Hol and Scherer (2004) Hol CW, Scherer CW (2004) Sum of squares relaxations for polynomial semidefinite programming. In: Proc. Symp. on Mathematical Theory of Networks and Systems (MTNS), Leuven, Belgium, Citeseer
  * Kojima and Muramatsu (2007) Kojima M, Muramatsu M (2007) An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones. Mathematical Programming 110(2):315–336
  * Legat et al. (2017) Legat B, Coey C, Deits R, Huchette J, Perry A (2017) Sum-of-squares optimization in Julia
  * Lubin and Dunning (2015) Lubin M, Dunning I (2015) Computing in Operations Research using Julia. INFORMS Journal on Computing 27(2):238–248, DOI 10.1287/ijoc.2014.0623
  * Nesterov (2000) Nesterov Y (2000) Squared functional systems and optimization problems. In: High performance optimization, Springer, pp 405–440
  * Nesterov and Nemirovskii (1994) Nesterov Y, Nemirovskii A (1994) Interior-point polynomial algorithms in convex programming. Studies in Applied Mathematics, SIAM
  * Papp and Alizadeh (2013) Papp D, Alizadeh F (2013) Semidefinite characterization of sum-of-squares cones in algebras. SIAM Journal on Optimization 23(3):1398–1423
  * Papp and Yildiz (2019) Papp D, Yildiz S (2019) Sum-of-squares optimization without semidefinite programming. SIAM Journal on Optimization 29(1):822–851
  * Skajaa and Ye (2015) Skajaa A, Ye Y (2015) A homogeneous interior-point algorithm for nonsymmetric convex conic optimization. Mathematical Programming 150(2):391–422
  * Sommariva and Vianello (2009) Sommariva A, Vianello M (2009) Computing approximate Fekete points by QR factorizations of Vandermonde matrices. Computers & Mathematics with Applications 57(8):1324–1336
  * Subramanian and Bhagwat (1979) Subramanian R, Bhagwat K (1979) On a theorem of Wigner on products of positive matrices. Proceedings of the Indian Academy of Sciences-Section A Part 3, Mathematical Sciences 88(1):31–34