text:
\section{Introduction}\label{sec:intro}
Completely positive (CP) programming (CPP), also called copositive (COP) programming, is a class of conic programming with a CP cone or COP cone. It has received much attention over the last few decades because it can represent many NP-hard problems, such as standard quadratic programming (QP)~\cite{BDde2000}, the quadratic assignment problem~\cite{PR2009}, and nonconvex QP with binary and continuous variables~\cite{Burer2009}, as convex programming in a unified manner.

In recent years, the concept of the CP and COP cones has been generalized in many ways. One example is the generalized CP (GCP) cone $\mathcal{CP}(\mathbb{K})$ and the generalized COP (GCOP) cone $\mathcal{COP}(\mathbb{K})$ over a closed convex cone $\mathbb{K} \subseteq \mathbb{R}^n$, defined as
\begin{align*}
\mathcal{CP}(\mathbb{K}) &\coloneqq \left\{\sum_{i=1}^k\bm{x}_i\bm{x}_i^\top \relmiddle| \bm{x}_i\in\mathbb{K},\ k\ge 1\right\},\\
\mathcal{COP}(\mathbb{K}) &\coloneqq \{\bm{A}\mid \bm{A} \text{ is a symmetric matrix and }\bm{x}^\top \bm{A}\bm{x} \ge 0\text{ for all }\bm{x}\in\mathbb{K}\}.
\end{align*}
(See Sect.~\ref{subsec:notation} for the formal definitions.) Hereafter, ``over $\mathbb{K}$" can be omitted when we need not specify it. An optimization problem equipped with the GCP or GCOP cone is called GCP programming (GCPP). Since GCPP includes CPP, it can express not only the above difficult problems but also many other NP-hard problems as convex programming: for example, nonconvex conic QP with binary and continuous variables~\cite{Burer2012} (e.g., a variable selection problem in linear regression~\cite{MT2015}), rank-constrained semidefinite programming (SDP)~\cite{BMP2016} (e.g., sensor network localization~\cite{NN2021}), $k$-means clustering~\cite{PH2018}, quadratically constrained QP~\cite{BD2012}, and so on. Therefore, solving GCPP is an important issue. However, as we can see from the fact that GCPP can represent such formidable problems equivalently, it is also difficult to solve them directly. In fact, Dickinson and Gijben~\cite{DG2014} proved that membership problems for the CP and COP cone are NP-hard (and so are those for the GCP and GCOP cones).

One solution for solving CPP is to relax the CP or COP cone by using a more tractable one. SDP relaxation, that is, replacing the CP or COP cone with a semidefinite cone, is a representative method to achieve this. Tighter relaxation has also been proposed in recent years. One such approach is doubly nonnegative (DNN) programming (DNNP) relaxation using the DNN cone or its dual cone (cf. \cite{Burer2010}). Since the DNN cone, namely, the set of semidefinite matrices with only nonnegative elements, is included in the semidefinite cone, the DNNP relaxation can give tighter bounds for CPP than SDP relaxation~\cite{PR2009,YM2010}.

It is thus natural to generalize the DNN cone in order to solve GCPP. Burer and Dong~\cite{BD2012} proposed the generalized DNN (GDNN) cone $\mathcal{DNN}_{\rm BD}(\mathbb{K})$, referred to as the BD GDNN cone hereafter, over a closed convex cone $\mathbb{K}$ and showed that it is tractable when $\mathbb{K}$ is a direct product (sum) of a nonnegative orthant and second-order cones. However, it is not yet known whether $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ is also tractable in other cases---for example, the case where $\mathbb{K}$ involves semidefinite cones. Because the main reason for introducing GDNN cones is to make original (NP-hard) problems easier to solve, we wonder whether this is the ``best" GDNN cone and would like to see if it is possible to obtain better GDNN cones.

The main goal of our study is to develop new GDNN cones that provide better relaxation for GCPP. To achieve this, we exploit approximation hierarchies~\cite{Parrilo2000,dP2002,PVZ2007,GL2007,BD2009,Yildirim2012,SBD2012,Dong2013,AM2019,GPS2020,ZVP2006,Lasserre2014,GDFe2014}. An approximation hierarchy, e.g., $\{\mathcal{K}_r\}_r$, approaches the (G)CP or (G)COP cone from the inside or outside gradually as parameter $r$ grows and, in a sense, agrees with the cone in the limit. Each $\mathcal{K}_r$ is tractable and the relaxation problem obtained by replacing the (G)CP or (G)COP cone with $\mathcal{K}_r$ can be solved in a polynomial time. We focus in this work on Parrilo~\cite{Parrilo2000}'s hierarchy, which approximates the COP cone from the inside. In this hierarchy, the dual cone of the zeroth level is known to be the DNN cone, so it seems reasonable to generalize Parrilo's hierarchy and define the dual cone of the zeroth level of the generalized approximation hierarchy as a GDNN cone.

On the basis of the above discussion, as the second purpose of this work, we generalize Parrilo's hierarchy and propose an inner-approximation hierarchy for the GCOP cone over a \textit{symmetric cone}. Typically, the nonnegative orthant, the second-order cone, and the semidefinite cone or their direct product are symmetric cones. A symmetric cone plays an important role in optimization~\cite{Faybusovich1997} and often appears in the modeling of realistic problems. In fact, the problems appearing in the papers~\cite{MT2015,NN2021,BD2012} can be reformulated as GCPP with the GCP cone over some symmetric cone. Therefore, it is worth approximating the GCP cone over a symmetric cone. We exploit the proposed hierarchy as well as Zuluaga et al.~\cite{ZVP2006}'s for the GCP cone over a semialgebraic cone, which is also a generalization of Parrilo's hierarchy, to derive new GDNN cones. The two are hereafter referred to as the NN GDNN cone and the ZVP GDNN cone, respectively. Since they are defined on the basis of the approximation hierarchy, they have an advantage over the BD GDNN cone in that they are always tractable if defined.

We investigate the inclusion relationship between the three GDNN cones over some specific symmetric cones $\mathbb{K}$, as inclusion is a crucial factor in the strength of relaxation. We first study the case where $\mathbb{K}$ is a direct product of a nonnegative orthant and second-order cones (Sects.~\ref{subsec:soc} and \ref{sec:experiment}). We find that the NN GDNN cone is included in the ZVP one theoretically and in the BD one numerically. Although there is no theoretical inclusion relationship between the ZVP and BD GDNN cones in general, the result of solving GDNN programming (GDNNP) relaxation problems of mixed 0--1 second-order cone programming shows that the proposed GDNN cones provide a tighter bound than the BD one in most cases. We also briefly investigate the case where $\mathbb{K}$ is a direct product of a nonnegative orthant and semidefinite cones and prove that the NN GDNN cone is also included in the ZVP one (Sect.~\ref{subsec:sdc}).

In Sect.~\ref{sec:preliminaries} of this paper, we introduce the notation and concepts used in this paper. In Sect.~\ref{sec:inner_approx_COP}, we briefly review previous works on inner-approximation hierarchies for the (G)COP cone and propose an inner-approximation hierarchy for the GCOP cone over a symmetric cone. In Sect.~\ref{sec:DNN}, we propose two new GDNN cones based on the presented hierarchies and describe the BD one. In Sect.~\ref{sec:relationship}, we discuss the theoretical properties of the three GDNN cones. In Sect.~\ref{sec:experiment}, we perform experiments to investigate the numerical properties of these cones. In Sect.~\ref{sec:conclusion}, we present our conclusions and suggest possible future work.

\section{Preliminaries}
\label{sec:preliminaries}
\subsection{Notation}
\label{subsec:notation}
We use $\mathbb{N}$, $\mathbb{R}$, $\mathbb{R}^{n\times m}$, and $\mathbb{S}^n$ to denote the set of nonnegative integers, the set of real numbers, the set of real $n\times m$ matrices, and the space of $n\times n$ symmetric matrices, respectively. For $n\in\mathbb{N}$, let $\tilde{n}\coloneqq n(n+1)/2$.
We use $\bm{e}_i$, $\bm{0}$, and $\bm{1}$ to represent the vector with $i$th element 1 and the others 0, the zero vector, and the vector with all elements 1, respectively. In addition, we use $\bm{O}$ and $\bm{I}$ to represent the zero matrix and the identity matrix, respectively. We sometimes write a subscript such as $\bm{0}_n$ and $\bm{I}_n$ to specify the size. All vectors that appear in this paper are column vectors. However, for notational convenience, the difference between column and row may not be distinguished if it is clear from the context. The $n$-dimensional Euclidean space $\mathbb{R}^n$ is endowed with the usual transpose inner product and $\|\cdot\|$ denotes the induced norm (2-norm).
The space $\mathbb{S}^n$ is endowed with the trace inner product defined by $\langle \bm{X},\bm{Y}\rangle \coloneqq \sum_{i,j=1}^n X_{ij}Y_{ij}$ for $\bm{X},\bm{Y}\in\mathbb{S}^n$. We use $S^n$ to denote the $n$-dimensional unit sphere in $\mathbb{R}^{n+1}$, i.e., $S^n = \{\bm{x}\in\mathbb{R}^{n+1}\mid \|\bm{x}\| = 1\}$.
Let $\bm{A}\in\mathbb{R}^{n\times m}$. The $(i,j)$th element of $\bm{A}$ is written as $A_{ij}$ or $A_{i,j}$.
Moreover, for index sets $\mathcal{I}\subseteq \{1,\dots,n\}$ and $\mathcal{J} \subseteq \{1,\dots,m\}$, $\bm{A}_{\mathcal{IJ}}$ denotes the submatrix obtained by extracting the rows of $\bm{A}$ indexed by $\mathcal{I}$ and the columns indexed by $\mathcal{J}$.
For a matrix $\bm{A}\in\mathbb{S}^n$, $\diag(\bm{A})$ denotes the $n$-dimensional vector with $i$th element $A_{ii}$. In addition, for $\bm{x}\in\mathbb{R}^n$, $\Diag(\bm{x})$ denotes the $n\times n$ diagonal matrix with $(i,i)$th element $x_i$. More generally, for matrices $\bm{X}_i\in\mathbb{S}^{n_i}\ (i = 1,\dots,k)$, $\Diag(\bm{X}_1,\dots,\bm{X}_k)$ denotes the (symmetric) block diagonal matrix with $i$th block $\bm{X}_i$.
For a set $\mathcal{X}$, we use $|\mathcal{X}|$, $\conv(\mathcal{X})$, and $\setint(\mathcal{X})$ to denote the cardinality, the convex hull, and the interior of $\mathcal{X}$, respectively.

The set $\mathcal{K}$ in a finite-dimensional real vector space is called a cone if $\alpha x\in\mathcal{K}$ for all $\alpha>0$ and $x\in\mathcal{K}$. For a cone $\mathcal{K}$, the dual cone $\mathcal{K}^*$ denotes the set of $x$ such that the inner product between $x$ and $y$ is greater than or equal to 0 for all $y\in\mathcal{K}$. A cone $\mathcal{K}$ is said to be pointed if $\mathcal{K}\cap(-\mathcal{K}) = \emptyset$ and solid if $\setint(\mathcal{K}) \neq \emptyset$. For a closed convex cone $\mathcal{K}$, $\Ext(\mathcal{K})$ denotes the union of extreme rays (one-dimensional faces) of $\mathcal{K}$. The following properties of a cone and its dual are well known:
\begin{theorem}[{\cite[Sect.~2.6.1]{BV2004}}]
Let $\mathcal{K}$, $\mathcal{K}_1,\mathcal{K}_2$ be a cone. Then,
\begin{enumerate}[(i)]
\item $\mathcal{K}^*$ is a closed convex cone.
\item If $\mathcal{K}$ is solid, $\mathcal{K}^*$ is pointed. Conversely, if $\mathcal{K}$ is a pointed closed convex cone, $\mathcal{K}^*$ is solid.
\item If $\mathcal{K}$ is a closed convex cone, $(\mathcal{K}^*)^* = \mathcal{K}$.
\item If $\mathcal{K}_1 \subseteq \mathcal{K}_2$, $\mathcal{K}_2^* \subseteq \mathcal{K}_1^*$.
\end{enumerate}
\end{theorem}

We use $\mathbb{R}_+^n$ and $\mathbb{S}_+^n$ to denote the set of $n$-dimensional nonnegative vectors (nonnegative orthant) and the set of $n\times n$ semidefinite matrices (semidefinite cone), respectively. In addition, $\mathbb{L}^n$ denotes the $n$-dimensional second-order cone, i.e.,
\begin{equation*}
\mathbb{L}^n = \begin{cases}
\mathbb{R}_+ & (n = 1),\\
\{\bm{x} = (x_1,\bm{x}_{2:n})\in\mathbb{R}^n \mid x_1 \ge \|\bm{x}_{2:n}\|\} & (n\ge 2).
\end{cases}
\end{equation*}
These sets are examples of a symmetric cone defined in Sect.~\ref{subsec:EJA}. Moreover, for $\bm{S}\in\mathbb{S}^n$, let $\mathbb{R}_+\bm{S} \coloneqq \{\alpha\bm{S}\mid \alpha\ge 0\}$.

Let $H_{n,m}$ be the set of forms in $n$ variables of degree $m$ with real coefficients. For $\bm{\alpha}=(\alpha_1,\dots,\alpha_n)\in\mathbb{N}^n$ and $\bm{x}=(x_1,\dots,x_n) \in \mathbb{R}^n$, we define $|\bm{\alpha}|\coloneqq \sum_{i=1}^n\alpha_i$ and $\bm{x}^{\bm{\alpha}}\coloneqq \prod_{i=1}^n x_i^{\alpha_i}$. Let $I(n,m) \coloneqq \{\bm{\alpha} \in \mathbb{N}^n\mid |\bm{\alpha}|=m\}$. $\mathbb{R}^{I(n,m)}$ and $\mathbb{S}^{I(n,m)}$ denote the $|I(n,m)|$-dimensional Euclidean space with elements indexed by $I(n,m)$ and the space of $|I(n,m)| \times |I(n,m)|$ symmetric matrices with columns and rows indexed by $I(n,m)$, respectively. $\mathbb{S}_+^{I(n,m)}$ denotes the set of semidefinite matrices in $\mathbb{S}^{I(n,m)}$. Every $\theta = \theta(\bm{x}) \in H_{n,m}$ can be written as $\theta(\bm{x}) = \sum_{\bm{\alpha}\in I(n,m)}\theta_{\bm{\alpha}}\bm{x}^{\bm{\alpha}}$ for some $(\theta_{\bm{\alpha}})_{\bm{\alpha}\in I(n,m)}\in\mathbb{R}^{I(n,m)}$. This vector is uniquely determined; in fact, the linear mapping
\begin{equation}
\mathbb{R}^{I(n,m)}\to H_{n,m};\ (\theta_{\bm{\alpha}})_{\bm{\alpha}\in I(n,m)}\mapsto \sum_{\bm{\alpha}\in I(n,m)}\theta_{\bm{\alpha}}\bm{x}^{\bm{\alpha}} \label{eq:RI(n,m)_to_Hnm}
\end{equation}
is a bijection. Using this, we can identify $H_{n,m}$ with $\mathbb{R}^{I(n,m)}$. In addition, when $m=2$, the linear mapping $\mathbb{S}^n\to H_{n,2};\ \bm{A}\mapsto \bm{x}^\top \bm{A}\bm{x}$ is a bijection. We can then also identify $H_{n,2}$ with $\mathbb{S}^n$. $\Sigma_{n,2m}$ denotes the set of sum of squares (SOS) of forms in $H_{n,m}$, i.e., $\Sigma_{n,2m} = \conv\{\theta^2\mid\theta\in H_{n,m}\}$. Since $\Sigma_{n,2m}$ is a subset of $H_{n,2m}$, we may regard $\Sigma_{n,2m}$ as a subset of $\mathbb{R}^{I(n,2m)}$ through the mapping~\eqref{eq:RI(n,m)_to_Hnm}. For $\bm{y}\in\mathbb{R}^{I(n,2m)}$, $\bm{M}_{n,m}(\bm{y})\in\mathbb{S}^{I(n,m)}$ is the matrix with $(\bm{\alpha},\bm{\alpha}')$th element $y_{\bm{\alpha}+\bm{\alpha}'}$ for $\bm{\alpha}$, $\bm{\alpha}'\in I(n,m)$. Then, we define $\mathcal{M}_{n,2m} \coloneqq \{\bm{y}\in \mathbb{R}^{I(n,2m)}\mid \bm{M}_{n,m}(\bm{y})\in \mathbb{S}_+^{I(n,m)}\}$. It is known that $\Sigma_{n,2m}$ and $\mathcal{M}_{n,2m}$ are dual with each other, i.e., $\Sigma_{n,2m}^* = \mathcal{M}_{n,2m}$ and $\mathcal{M}_{n,2m}^* = \Sigma_{n,2m}$ hold~\cite[Lemma~1]{GL2007}. In particular, $\Sigma_{n,2m}$ and $\mathcal{M}_{n,2m}$ are closed convex cones.

For a closed convex cone $\mathbb{K}$ in $\mathbb{R}^n$, we define
\begin{equation*}
\mathcal{COP}^{n,m}(\mathbb{K})\coloneqq\{\theta\in H_{n,m}\mid \theta(\bm{x})\ge 0\ \text{for all $\bm{x}\in \mathbb{K}$}\}.
\end{equation*}
In particular, when $m=2$, identifying $H_{n,2}$ with $\mathbb{S}^n$, we have
\begin{equation*}
\mathcal{COP}^{n,2}(\mathbb{K})= \{\bm{A}\in\mathbb{S}^n\mid \bm{x}^\top \bm{A}\bm{x}\ge 0\ \text{for all $\bm{x}\in \mathbb{K}$}\}.
\end{equation*}
We write $\mathcal{COP}^{n,2}(\mathbb{K})$ as $\mathcal{COP}(\mathbb{K})$ for simplicity and call it the GCOP cone over $\mathbb{K}$. Moreover, we write $\mathcal{COP}^n$ for $\mathcal{COP}(\mathbb{R}_+^n)$ and call it the COP cone. The GCP cone $\mathcal{CP}(\mathbb{K})$ over $\mathbb{K}$ is defined by the convex hull of the rank-1 matrices $\bm{x}\bm{x}^\top$ with $\bm{x}\in \mathbb{K}$, i.e., $\mathcal{CP}(\mathbb{K}) = \conv\{\bm{x}\bm{x}^\top \mid \bm{x}\in \mathbb{K}\}$. Note that the definition of the GCOP and GCP cone mentioned here is consistent with that in Sect.~\ref{sec:intro}~\cite[Proposition~1]{BDde2000}. We write $\mathcal{CP}^n$ for $\mathcal{CP}(\mathbb{R}_+^n)$ and call it the CP cone. We define $\mathcal{N}^n$ as the set of $n\times n$ symmetric matrices with only nonnegative elements and the DNN cone $\mathbb{S}_+^n\cap \mathcal{N}^n$ is denoted by $\mathcal{DNN}^n$. These cones have the following properties:
\begin{theorem}
Let $\mathbb{K}$ be a closed convex cone in $\mathbb{R}^n$. Then,
\begin{enumerate}[(i)]
\item $\mathcal{CP}(\mathbb{K}) \subseteq \mathbb{S}_+^n \subseteq \mathcal{COP}(\mathbb{K})$ holds. In particular, when $\mathbb{K} = \mathbb{R}_+^n$, $\mathcal{CP}^n \subseteq \mathcal{DNN}^n \subseteq \mathbb{S}_+^n \subseteq \mathcal{COP}^n$ holds.
\item $\mathcal{CP}(\mathbb{K})$ and $\mathcal{COP}(\mathbb{K})$ are dual with each other~\cite{SZ2003}.
\item $\mathcal{DNN}^n$ and $\mathbb{S}_+^n + \mathcal{N}^n$ are dual with each other~\cite{YM2010}. In particular, $\mathbb{S}_+^n + \mathcal{N}^n$ is a closed convex cone.
\end{enumerate}
\end{theorem}

\subsection{Euclidean Jordan algebra and symmetric cone}
\label{subsec:EJA}
A Jordan algebra is a finite-dimensional real vector space $\mathbb{E}$ equipped with a bilinear mapping (product) denoted by $\circ$ that has the following properties for all $x$, $y\in\mathbb{E}$:
\begin{enumerate}[(J1)]
\item $x \circ y = y \circ x$,
\item $x\circ ((x\circ x)\circ y) = (x\circ x)\circ(x\circ y)$.
\end{enumerate}
We assume in this paper that $\mathbb{E}$ has a (unique) identity element $e$ for the product. A Jordan algebra is called Euclidean if there exists an associative inner product $\bullet$, i.e., $(x\circ y)\bullet z = x\bullet(y\circ z)$ for all $x$, $y$, $z\in\mathbb{E}$.

We define the symmetric cone $\mathbb{E}_+$ (associated with the Euclidean Jordan algebra $\mathbb{E}$) as $\{x\circ x\mid x\in\mathbb{E}\}$. Symmetric cones are known to be self-dual, i.e., $(\mathbb{E}_+)^* = \mathbb{E}_+$ and so a pointed solid closed convex cone. Specifically, the identity element $e$ of $\mathbb{E}$ is in $\setint(\mathbb{E}_+)$~\cite[Theorem~I\hspace{-1pt}I\hspace{-1pt}I.2.1]{FK1994}.

An element $c\in \mathbb{E}$ is called an idempotent if $c\circ c = c$. Moreover, $c$ is said to be primitive if $c$ is nonzero and cannot be written as the sum of two nonzero idempotents. We write $\mathfrak{J}(\mathbb{E}_+)$ for the set of primitive idempotents of the Euclidean Jordan algebra associated with $\mathbb{E}_+$. The next theorem says that each element of a Euclidean Jordan algebra can be written as the linear combination of primitive idempotents.
\begin{theorem}
[{\cite[Theorem~I\hspace{-1pt}I\hspace{-1pt}I.1.2]{FK1994}}]\label{thm:spectral}
Let $\mathbb{E}$ be a Euclidean Jordan algebra. Then, for each $x\in \mathbb{E}$, there exist $r\in\mathbb{N}$, $\lambda_1,\dots,\lambda_r\in \mathbb{R}$, and $c_1,\dots,c_r\in \mathbb{E}$ such that
\begin{equation}
x = \sum_{i=1}^r\lambda_i c_i. \label{eq:spectral}
\end{equation}
\end{theorem}
Eq.~\eqref{eq:spectral} is called the spectral decomposition of $x$. The number $r$ is called the rank of $\mathbb{E}$ and only depends on $\mathbb{E}$. The system $c_1,\dots,c_r$ forms a Jordan frame, i.e., each $c_i$ is a primitive idempotent, $c_i\circ c_j = 0$ for all $i\neq j$, and $\sum_{i=1}^r c_i = e$. The numbers $\lambda_1,\dots,\lambda_r$ are called the eigenvalues of $x$ and are uniquely determined by $x$. We write $\lambda_{\rm min}(x)$ for the minimum eigenvalue of $x$. Using Theorem~\ref{thm:spectral}, we see that $\lambda_{\rm min}(x)\ge 0$ if and only if $x \in \mathbb{E}_+$.

As described, a symmetric cone is defined as the cone of squares in a Euclidean Jordan algebra. Conversely, for a given symmetric cone, there exists a Euclidean Jordan algebra that is used to construct the cone~\cite[Theorem~\mbox{I\hspace{-1pt}I\hspace{-1pt}I}.3.1]{FK1994}. Therefore, given a symmetric cone, we use the notations defined above, such as $\circ$ and $\lambda_{\rm min}(\cdot)$, to represent the notation about the associated Euclidean Jordan algebra.

Consider the case where the Euclidean Jordan algebra $\mathbb{E}$ is represented as a direct product of some Euclidean Jordan algebras $\mathbb{E}_1,\dots,\mathbb{E}_N$. The symmetric cone $\mathbb{E}_+$ is then $\prod_{i=1}^N(\mathbb{E}_i)_+$, and the direct product of multiple symmetric cones is also a symmetric cone. The next lemma describes the set of primitive idempotents of $\mathbb{E}$ and the eigenvalues of an element in $\mathbb{E}$.
\begin{lemma}\label{lem:direct_sum}
Let $\mathbb{E}_i$ be a Euclidean Jordan algebra with rank $r_i$ for $i = 1,\dots,N$ and $\mathbb{E} \coloneqq \prod_{i=1}^N\mathbb{E}_i$. Then,
\begin{equation*}
\mathfrak{J}(\mathbb{E}_+) = \{(s,0,\dots,0)\mid s\in \mathfrak{J}([\mathbb{E}_1]_+)\}
\cup\cdots\cup \{(0,\dots,0,s)\mid s\in \mathfrak{J}([\mathbb{E}_N]_+)\}.
\end{equation*}
In addition, for any $x = (x_1,\dots,x_N)\in \mathbb{E}$ and for each $i$, let $\lambda_1^{(i)},\dots,\lambda_{r_i}^{(i)}$ be the eigenvalues of $x_i$. $\lambda_{j}^{(i)}\ (i=1,\dots,N,\ j=1,\dots,r_i)$ are then the eigenvalues of $x$.
\end{lemma}

The next three examples are typical Euclidean Jordan algebras that appear frequently in this paper.
\begin{example}
[nonnegative orthant]\label{ex:nno} Consider the $n$-dimensional Euclidean space $\mathbb{R}^n$. If we define $\bm{x}\circ \bm{y} \coloneqq (x_1y_1,\dots,x_ny_n)$ and $\bm{x}\bullet \bm{y} \coloneqq \bm{x}^\top\bm{y}$ for $\bm{x}$, $\bm{y}\in \mathbb{R}^n$, then $(\mathbb{R}^n,\circ,\bullet)$ is a Euclidean Jordan algebra and the symmetric cone $\{\bm{x}\circ\bm{x}\mid \bm{x}\in\mathbb{R}^n\}$ is $\mathbb{R}_+^n$. The identity element of the Euclidean Jordan algebra is $\bm{1}_n$ and the set $\mathfrak{J}(\mathbb{R}_+^n)$ is $\{\bm{e}_1,\dots,\bm{e}_n\}$. For $\bm{x}\in \mathbb{R}^n$, the spectral decomposition of $\bm{x}$ is $\sum_{i=1}^nx_i\bm{e}_i$. Therefore, the eigenvalues of $\bm{x}$ are its elements. We write the minimum eigenvalue of an element in the Euclidean Jordan algebra as $\lambda_{\rm min}^{\rm nno}(\cdot)$, i.e., $\lambda_{\rm min}^{\rm nno}(\bm{x}) = \min_{1\le i\le n}x_i$.
\end{example}

\begin{example}
[second-order cone]\label{ex:soc} Again consider the $n$-dimensional Euclidean space $\mathbb{R}^n$. If we define $\bm{x}\circ \bm{y} \coloneqq (\bm{x}^\top\bm{y},x_1\bm{y}_{2:n} + y_1\bm{x}_{2:n})$ and $\bm{x}\bullet\bm{y} \coloneqq \bm{x}^\top\bm{y}$ for $\bm{x}=(x_1,\bm{x}_{2:n})$, $\bm{y}=(y_1,\bm{y}_{2:n})\in \mathbb{R}^n$, then $(\mathbb{R}^n,\circ,\bullet)$ is a Euclidean Jordan algebra and the symmetric cone $\{\bm{x}\circ\bm{x}\mid \bm{x}\in\mathbb{R}^n\}$ is $\mathbb{L}^n$. The identity element of the Euclidean Jordan algebra is $(1,\bm{0}_{n-1})$ and the set $\mathfrak{J}(\mathbb{L}^n)$ is $\{(1/2,\bm{v}/2)\mid \bm{v}\in S^{n-2}\}$. For $\bm{x}=(x_1,\bm{x}_{2:n})\in \mathbb{R}^n$, the spectral decomposition of $\bm{x}$ is
\begin{equation*}
\begin{cases}
(x_1+\|\bm{x}_{2:n}\|)\frac{1}{2}\left(1,\frac{\bm{x}_{2:n}}{\|\bm{x}_{2:n}\|}\right)
 + (x_1-\|\bm{x}_{2:n}\|)\frac{1}{2}\left(1,-\frac{\bm{x}_{2:n}}{\|\bm{x}_{2:n}\|}\right) & (\text{if $\bm{x}_{2:n} \neq \bm{0}$}),\\
(x_1+\|\bm{x}_{2:n}\|)\frac{1}{2}(1,\bm{v}) + (x_1-\|\bm{x}_{2:n}\|)\frac{1}{2}(1,-\bm{v}) & (\text{if $\bm{x}_{2:n} = \bm{0}$}),
\end{cases}
\end{equation*}
where $\bm{v}$ is an arbitrary element in $S^{n-2}$. Therefore, the eigenvalues of $\bm{x}$ are $x_1 + \|\bm{x}_{2:n}\|$ and $x_1-\|\bm{x}_{2:n}\|$. We write the minimum eigenvalue of an element in the Euclidean Jordan algebra as $\lambda_{\rm min}^{\rm soc}(\cdot)$, i.e., $\lambda_{\rm min}^{\rm soc}(\bm{x}) = x_1-\|\bm{x}_{2:n}\|$.
\end{example}

\begin{example}
[semidefinite cone]\label{ex:sdc} Consider the space $\mathbb{S}^n$ of $n\times n$ symmetric matrices. If we define $\bm{X}\lozenge \bm{Y} \coloneqq (\bm{X}\bm{Y} + \bm{Y}\bm{X})/2$ and $\bm{X}\blacklozenge \bm{Y} \coloneqq \langle \bm{X},\bm{Y}\rangle$ for $\bm{X}$, $\bm{Y}\in \mathbb{S}^n$, then $(\mathbb{S}^n,\lozenge,\blacklozenge)$ is a Euclidean Jordan algebra and the symmetric cone $\{\bm{X}\lozenge \bm{X}\mid \bm{X}\in\mathbb{S}^n\}$ is $\mathbb{S}_+^n$. The identity element of the Euclidean Jordan algebra is $\bm{I}_n$ and the set $\mathfrak{J}(\mathbb{S}_+^n)$ is $\{\bm{v}\bm{v}^\top\mid \bm{v}\in S^{n-1}\}$. For $\bm{X}\in \mathbb{S}^n$, the spectral decomposition of $\bm{X}$ corresponds to that in a matrix sense. Namely, there exist $\bm{\Lambda} = \Diag(\lambda_1,\dots,\lambda_n)$ and an orthogonal matrix $\bm{V} = (\bm{v}_1,\dots,\bm{v}_n)$ such that $\bm{X} = \bm{V}\bm{\Lambda} \bm{V}^\top$. Then, $\bm{X}$ can be written as $\sum_{i=1}^n\lambda_i\bm{v}_i\bm{v}_i^\top$, which is the spectral decomposition of $\bm{X}$.

We focus on the vectorized semidefinite cone in this paper. We define the linear mapping $\svec: \mathbb{S}^n\to\mathbb{R}^{\tilde{n}}$ as
\begin{equation*}
\svec(\bm{X}) \coloneqq (X_{11},\sqrt{2}X_{12},X_{22},\dots,\sqrt{2}X_{1n},\dots,\sqrt{2}X_{n-1,n},X_{nn})\ (\bm{X}\in\mathbb{S}^n).
\end{equation*}
Then, the mapping $\svec(\cdot)$ is an inner product space isomorphism between $\mathbb{S}^n$ and $\mathbb{R}^{\tilde{n}}$, i.e., $\langle \bm{X},\bm{Y}\rangle = \svec(\bm{X})^\top\svec(\bm{Y})$ holds for all $\bm{X}$, $\bm{Y}\in\mathbb{S}^n$. Let $\smat(\cdot)$ denote the inverse mapping of $\svec(\cdot)$. If we define $\bm{x}\circ \bm{y} \coloneqq \svec(\smat(\bm{x})\lozenge\smat(\bm{y}))$ and $\bm{x}\bullet \bm{y} \coloneqq \bm{x}^\top\bm{y}$ for $\bm{x}$, $\bm{y}\in\mathbb{R}^{\tilde{n}}$, then $(\mathbb{R}^{\tilde{n}},\circ,\bullet)$ is a Euclidean Jordan algebra and the symmetric cone $\{\bm{x}\circ\bm{x}\mid \bm{x}\in\mathbb{R}^n\}$ is $\svec(\mathbb{S}_+^n)$. We write the minimum eigenvalue of an element of the Euclidean Jordan algebra as $\lambda_{\rm min}^{\rm sdc}(\cdot)$, i.e., $\lambda_{\rm min}^{\rm sdc}(\bm{x})$ is the minimum eigenvalue of $\smat(\bm{x})$ in a matrix sense.
\end{example}

More generally, any Euclidean Jordan algebra can be transformed into a Euclidean Jordan algebra with the Euclidean space as a finite-dimensional real vector space and the transpose inner product as an associative inner product. Specifically, let $\mathbb{E}$ be an $n$-dimensional real vector space and $(\mathbb{E},\lozenge,\blacklozenge)$ be a Euclidean Jordan algebra. There then exists an inner product space isomorphism $\phi$ between $\mathbb{E}$ and $\mathbb{R}^n$. If we define $\bm{x}\circ\bm{y} \coloneqq \phi(\phi^{-1}(\bm{x})\lozenge\phi^{-1}(\bm{y}))$ and $\bm{x}\bullet\bm{y} \coloneqq \bm{x}^\top\bm{y}$, then $(\mathbb{R}^n,\circ,\bullet)$ is a Euclidean Jordan algebra with the transpose inner product as an associative inner product.

\section{Inner-approximation hierarchies for (generalized) copositive cone}
\label{sec:inner_approx_COP}
In this section, we introduce inner-approximation hierarchies for the (G)COP cone. In Sect.~\ref{subsec:existing_approximation}, we review two existing hierarchies. One is Parrilo's inner-approximation hierarchy for the COP cone~\cite{Parrilo2000}. The other is Zuluaga et al.'s inner-approximation hierarchy for the GCOP cone over a semialgebraic cone~\cite{ZVP2006}. We explain these existing hierarchies in detail because they are crucial to understanding the reasonability of the proposed GDNN cones. In Sect.~\ref{subsec:proposed_approximation}, we propose an inner-approximation hierarchy for the GCOP cone over a symmetric cone.

\subsection{Existing inner-approximation hierarchies for (generalized) copositive cone}
\label{subsec:existing_approximation}
\subsubsection{Parrilo's inner-approximation hierarchy for copositive cone}
\label{subsubsec:Parrilo}
We can observe that $\bm{A}\in \mathcal{COP}^n$ if and only if $P(\bm{x};\bm{A}) \coloneqq \sum_{i,j=1}^nA_{ij}x_i^2x_j^2 \in H_{n,4}$ is nonnegative on $\mathbb{R}^n$. However, it is generally difficult to judge the nonnegativity of a form. In fact, checking whether a matrix belongs to $\mathcal{COP}^n$ is known to be an NP-hard problem~\cite{DG2014}. Therefore, as a sufficient condition for $P(\bm{x};\bm{A})$ to be nonnegative on $\mathbb{R}^n$, we consider the condition that $P(\bm{x};\bm{A})$ can be written as an SOS, i.e., $P(\bm{x};\bm{A}) \in \Sigma_{n,4}$. The problem of checking whether a form can be written as an SOS is characterized by a semidefinite constraint and therefore can be determined in a polynomial time.

To give an inner-approximation hierarchy for $\mathcal{COP}^n$, Parrilo~\cite{Parrilo2000} considered the following condition parametrized by $r\in\mathbb{N}$:
\begin{equation}
P_r(\bm{x};\bm{A}) \coloneqq \left(\sum_{i=1}^nx_i^2\right)^rP(\bm{x};\bm{A}) \in \Sigma_{n,2r+4}. \label{eq:Parrilo_SOS}
\end{equation}
For each $r$, let $\mathcal{K}_{{\rm P},r}^n$ denote the set of $\bm{A}\in \mathbb{S}^n$ satisfying condition~\eqref{eq:Parrilo_SOS}. The sequence $\{\mathcal{K}_{{\rm P},r}^n\}_r$ gives an inner-approximation hierarchy for $\mathcal{COP}^n$. Roughly speaking, ``$\mathcal{K}_{{\rm P},0}^n\subseteq\cdots\subseteq\mathcal{K}_{{\rm P},r}^n\subseteq\cdots\to \mathcal{COP}^n\ (r\to\infty)$'' holds. To be more precise, the following theorem holds.

\begin{theorem}[{\cite[Sect.~5.3]{Parrilo2000}}]\label{thm:Parrilo}
The sequence $\{\mathcal{K}_{{\rm P},r}^n\}_r$ satisfies $\mathcal{K}_{{\rm P},r}^n \subseteq \mathcal{K}_{{\rm P},r+1}^n \subseteq \mathcal{COP}^n$ for all $r \in \mathbb{N}$. Moreover, there exists some $r_0\in\mathbb{N}$ such that $\setint(\mathcal{COP}^n) \subseteq\mathcal{K}_{{\rm P},r_0}^n$.
\end{theorem}

In what follows, we write the properties mentioned in Theorem~\ref{thm:Parrilo} as ``$\mathcal{K}_{{\rm P},r}^n\uparrow \mathcal{COP}^n$'' (but the notation is not limited to $\mathcal{K}_{{\rm P},r}^n$). Parrilo~\cite[Sect.~5.3]{Parrilo2000} also showed that $\mathcal{K}_{{\rm P},0}^n = \mathbb{S}_+^n + \mathcal{N}^n$. Therefore, from the duality between $\mathcal{DNN}^n$ and $\mathbb{S}_+^n + \mathcal{N}^n$, we have $(\mathcal{K}_{{\rm P},0}^n)^* = \mathcal{DNN}^n$.

\subsubsection{Zuluaga et al.'s inner-approximation hierarchy for generalized copositive cone}
\label{subsubsec:Zuluaga}
Zuluaga et al.~\cite{ZVP2006} gave an inner-approximation hierarchy for $\mathcal{COP}^{n,m}(\mathbb{K})$, where $\mathbb{K}$ is a semialgebraic pointed closed convex cone. Specifically, we suppose that $\mathbb{K}$ is expressed as
\begin{equation}
\{\bm{x}\in \mathbb{R}^n\mid \phi_i(\bm{x})\ge 0\ (i = 1,\dots,q)\}, \label{eq:K_semialg}
\end{equation}
where $\phi_i\in H_{n,m_i}\ (i=1,\dots,q)$. The closedness of $\mathbb{K}$ is clear from the expression of $\mathbb{K}$. Assume that $\mathbb{K}$ is a pointed convex cone. Then, there exists some $\bm{a}\in \mathbb{R}^n\setminus\{\bm{0}\}$ such that the following holds (see \cite[Sect.~6]{ZVP2006}):
\begin{align}
&\mathbb{K}\subseteq \{\bm{x}\mid \bm{a}^\top\bm{x}\ge 0\}, \label{eq:exposed_face_1}\\
&\mathbb{K} \cap \{\bm{x}\mid \bm{a}^\top\bm{x} = 0\} = \{\bm{0}\}. \label{eq:exposed_face_2}
\end{align}
In fact, the set of $\bm{a}$ satisfying Eqs.~\eqref{eq:exposed_face_1} and \eqref{eq:exposed_face_2} is exactly $\setint(\mathbb{K}^*)$, which is nonempty since $\mathbb{K}^*$ is solid. From Eq.~\eqref{eq:exposed_face_1}, the geometric property of $\mathbb{K}$ does not change even if we add the linear inequality $\bm{a}^\top\bm{x}\ge 0$ with $\bm{a}\in \setint(\mathbb{K}^*)$ into the definition of $\mathbb{K}$. Thus, we may assume that there is some $i$ such that $\phi_i(\bm{x}) = \bm{a}^\top\bm{x}$. Note that the different choice of $\bm{a}$ could yield a different hierarchy even if the geometric property of $\mathbb{K}$ does not change. Namely, the hierarchy depends on the algebraic description of $\mathbb{K}$. Therefore, we may use the notation $(\mathbb{K};\bm{a})$ to emphasize the choice of $\bm{a}$.

Under the assumption on $\mathbb{K}$, the inner-approximation hierarchy for $\mathcal{COP}^{n,m}(\mathbb{K})$ given by Zuluaga et al.~\cite{ZVP2006} is described as follows:

\begin{theorem}[{\cite[Proposition~17]{ZVP2006}}]\label{thm:ZVP_inner_approx_COP}
Let
\begin{equation*}
E^{n,m}(\mathbb{K}) \coloneqq \conv\left\{\psi^2\prod_{j=1}^k\phi_{i_j}\relmiddle|
\begin{array}{l}
k\in \mathbb{N},\ m-\sum_{j=1}^km_{i_j}\in \mathbb{N}\text{ is even},\\
\psi\in H_{n,(m-\sum_{j=1}^km_{i_j})/2},\\
i_j\in \{1,\dots,q\}\ (j=1,\dots,k)
\end{array}
\right\}\\
\end{equation*}
and $\mathcal{K}_{{\rm ZVP},r}^{n,m}(\mathbb{K}) \coloneqq \{\theta\in H_{n,m}\mid (\bm{a}^\top\bm{x})^r\theta(\bm{x})\in E^{n,m+r}(\mathbb{K})\}$. The sequence $\{\mathcal{K}_{{\rm ZVP},r}^{n,m}(\mathbb{K})\}_r$ then satisfies $\mathcal{K}_{{\rm ZVP},r}^{n,m}(\mathbb{K}) \uparrow \mathcal{COP}^{n,m}(\mathbb{K})$.
\end{theorem}

Zuluaga et al.'s inner-approximation hierarchy for $\mathcal{COP}^{n,m}(\mathbb{K})$ is a generalization of Parrilo's for $\mathcal{COP}^n$. Consider the case of $m=2$. For convenience, we write $\mathcal{K}_{{\rm ZVP},r}^{n,2}(\mathbb{K})$ as $\mathcal{K}_{{\rm ZVP},r}(\mathbb{K})$. Let $\mathbb{K} = \mathbb{R}_+^n = \{\bm{x}\in\mathbb{R}^n \mid \bm{e}_i^\top\bm{x} \ge 0\ (i = 1,\dots,n)\}$ and $\bm{a} = \bm{1}_n\in \setint(\mathbb{K}^*)$. If we regard each $\mathcal{K}_{{\rm ZVP},r}(\mathbb{R}_+^n;\bm{1}_n)$ as a subset of $\mathbb{S}^n$ through the identification of $H_{n,2}$ with $\mathbb{S}^n$, then the sequence $\{\mathcal{K}_{{\rm ZVP},r}(\mathbb{R}_+^n;\bm{1}_n)\}_r$ agrees with $\{\mathcal{K}_{{\rm P},r}^n\}_r$ \cite[Remark~2]{ZVP2006}.

\subsection{Proposed inner-approximation hierarchy for generalized copositive cone}
\label{subsec:proposed_approximation}
Let $\mathbb{R}^n$ be a Euclidean Jordan algebra with a product $\circ$ and the transpose inner product as an associative inner product. As explained in Sect.~\ref{subsec:EJA}, this assumption is without loss of generality. To emphasize that $\mathbb{R}^n$ is a Euclidean Jordan algebra, we may write it as $\mathbb{E}$ in this subsection. Here, we derive an inner-approximation hierarchy for $\mathcal{COP}^{n,m}(\mathbb{E}_+)$.

The next lemma shows that the copositivity of a form on the symmetric cone $\mathbb{E}_+$ can be represented as the nonnegativity of a form with a higher degree. Note that this is an analogy to the observation that the copositivity of a matrix $\bm{A}$ is equivalent to the nonnegativity of $P(\bm{x};\bm{A})$ mentioned in Sect.~\ref{subsubsec:Parrilo}.

\begin{lemma}\label{lem:in_COP}
Let $\mathscr{S}:H_{n,m}\to H_{n,2m}$ be the mapping such that $(\mathscr{S}\theta)(\bm{x})\coloneqq \theta(\bm{x}\circ\bm{x})$ for $\theta\in H_{n,m}$. Then, for a given $\theta \in H_{n,m}$, $\theta\in \mathcal{COP}^{n,m}(\mathbb{E}_+)$ if and only if $\mathscr{S}\theta \in \mathcal{COP}^{n,2m}(\mathbb{R}^n)$, i.e., $\mathscr{S}\theta$ is nonnegative on $\mathbb{R}^n$. Moreover, $\theta\in \setint(\mathcal{COP}^{n,m}(\mathbb{E}_+))$ if and only if $\mathscr{S}\theta\in\setint(\mathcal{COP}^{n,2m}(\mathbb{R}^n))$.
\end{lemma}

The proof of the latter claim of Lemma~\ref{lem:in_COP} relies on the following fact:

\begin{lemma}[{\cite[Observation~1]{ZVP2006}}]\label{lem:characterization_in_COP}
Let $\mathbb{K}\subseteq \mathbb{R}^n$ be a closed cone. Then, for each $\theta\in H_{n,m}$, $\theta \in \setint(\mathcal{COP}^{n,m}(\mathbb{K}))$ if and only if $\theta(\bm{x})>0$ for all $\bm{x}\in \mathbb{K}\setminus\{\bm{0}\}$. (Such $\theta$ is said to be strictly copositive on $\mathbb{K}$ hereafter.)
\end{lemma}

\begin{proof}
[Proof of Lemma~\ref{lem:in_COP}] Note that the bilinearity of the product $\circ$ of the Euclidean Jordan algebra implies that each element of $\bm{x}\circ \bm{x}$ is a quadratic form for each $\bm{x}\in\mathbb{R}^n$. Therefore, the mapping $\mathscr{S}$ is well-defined.

Suppose that $\theta\in\mathcal{COP}^{n,m}(\mathbb{E}_+)$. For any $\bm{x}\in \mathbb{R}^n$, let $\bm{y}\coloneqq \bm{x}\circ\bm{x}$. Then, we see that $\bm{y}\in\mathbb{E}_+$ and $(\mathscr{S}\theta)(\bm{x})=\theta(\bm{y}) \ge 0$. Conversely, suppose that $\mathscr{S}\theta$ is nonnegative on $\mathbb{R}^n$. Let $\bm{y}\in\mathbb{E}_+$ and consider the spectral decomposition of $\bm{y}$. Let $r$ be the rank of the Euclidean Jordan algebra $\mathbb{E}$. Then, there exist a Jordan frame $\bm{c}_1,\dots,\bm{c}_r$ and nonnegative eigenvalues $\lambda_1\dots,\lambda_r$ such that $\bm{y} = \sum_{i=1}^r\lambda_i\bm{c}_i$. Let $\bm{x}\coloneqq \sum_{i=1}^r\sqrt{\lambda_i}\bm{c}_i$, then $\bm{x}\circ\bm{x}=\bm{y}$. Therefore, we obtain $\theta(\bm{y}) = (\mathscr{S}\theta)(\bm{x}) \ge 0$.

We next prove the ``int" version. Note that $\mathbb{R}^n$ and $\mathbb{E}_+$ are closed cones. Then, from Lemma~\ref{lem:characterization_in_COP}, it suffices to show that the strict copositivity of $\theta$ on $\mathbb{E}_+$ is equivalent to the strict copositivity of $\mathscr{S}\theta$ on $\mathbb{R}^n$. This can be shown in the same way as the first statement.
\end{proof}

Since it is difficult to check whether $\mathscr{S}\theta$ is nonnegative or not, as a sufficient condition of it, we consider the set of forms $\theta\in H_{n,m}$ such that $(\sum_{i=1}^nx_i^2)^r\mathscr{S}\theta(\bm{x})$ can be represented as an SOS for $r\in\mathbb{N}$. The sequence gives an inner-approximation hierarchy for $\mathcal{COP}^{n,m}(\mathbb{E}_+)$:

\begin{theorem}\label{thm:inner_approx_COP}
For each $r\in\mathbb{N}$, we define
\begin{align*}
\mathcal{K}^{n,2m}_{r} &\coloneqq \left\{\theta\in H_{n,2m}\relmiddle| \left(\sum_{i=1}^nx_i^2\right)^r\theta(\bm{x})\in\Sigma_{n,2(m+r)}\right\},\\
\mathcal{K}^{n,m}_{{\rm NN},r}(\mathbb{E}_+)&\coloneqq \{\theta\in H_{n,m}\mid \mathscr{S}\theta\in \mathcal{K}^{n,2m}_{r}\}\\
&=\left\{\theta\in H_{n,m}\relmiddle| \left(\sum_{i=1}^nx_i^2\right)^r\theta(\bm{x}\circ\bm{x})\in\Sigma_{n,2(m+r)}\right\}.
\end{align*}
Then, $\mathcal{K}^{n,m}_{{\rm NN},r}(\mathbb{E}_+)$ is a closed convex cone for each $r\in\mathbb{N}$ and the sequence $\{\mathcal{K}_{{\rm NN},r}^{n,m}(\mathbb{E}_+)\}_r$ satisfies $\mathcal{K}_{{\rm NN},r}^{n,m}(\mathbb{E}_+) \uparrow \mathcal{COP}^{n,m}(\mathbb{E}_+)$.
\end{theorem}

\begin{proof}
It is easy to see that $\mathcal{K}^{n,m}_{{\rm NN},r}(\mathbb{E}_+)$ is a convex cone. The closedness of $\mathcal{K}^{n,m}_{{\rm NN},r}(\mathbb{E}_+)$ can be shown by the closedness of $\Sigma_{n,2(m+r)}$. In what follows, we prove ``$\mathcal{K}_{{\rm NN},r}^{n,m}(\mathbb{E}_+) \uparrow \mathcal{COP}^{n,m}(\mathbb{E}_+)$." The key of the proof is
\begin{equation}
\mathcal{K}_{r}^{n,2m} \uparrow \mathcal{COP}^{n,2m}(\mathbb{R}^n) \label{eq:ZVP2006_prop5}
\end{equation}
proved by \cite[Proposition~5]{ZVP2006}. Firstly, it follows from \eqref{eq:ZVP2006_prop5} that $\{\mathcal{K}_{{\rm NN},r}^{n,m}(\mathbb{E}_+)\}_r$ is nondecreasing. Secondly, for each $r\in\mathbb{N}$ and $\theta\in\mathcal{K}_{{\rm NN},r}^{n,m}(\mathbb{E}_+)$, we have $\mathscr{S}\theta\in\mathcal{K}_{r}^{n,2m}$ by definition. It follows from \eqref{eq:ZVP2006_prop5} that $\mathscr{S}\theta$ is nonnegative on $\mathbb{R}^n$. From Lemma~\ref{lem:in_COP}, we see that $\theta\in\mathcal{COP}^{n,m}(\mathbb{E}_+)$. Thus, $\mathcal{K}_{{\rm NN},0}^{n,m}(\mathbb{E}_+) \subseteq \mathcal{COP}^{n,m}(\mathbb{E}_+)$ holds. Thirdly, let $\theta\in\setint(\mathcal{COP}^{n,m}(\mathbb{E}_+))$, then Lemma~\ref{lem:in_COP} implies that $\mathscr{S}\theta\in\setint(\mathcal{COP}^{n,2m}(\mathbb{R}^n))$. By \eqref{eq:ZVP2006_prop5}, there exists $r_0\in\mathbb{N}$ such that $\mathscr{S}\theta\in \mathcal{K}_{r_0}^{n,2m}$. Therefore, by definition, we obtain $\theta \in \mathcal{K}_{{\rm NN},r_0}^{n,m}(\mathbb{E}_+)$. This completes the proof.
\end{proof}

The case of $m=2$ is described below.

\begin{corollary}\label{cor:inner_approx_COP}
We define
\begin{equation*}
\mathcal{K}_{{\rm NN},r}(\mathbb{E}_+) \coloneqq \mathcal{K}^{n,2}_{{\rm NN},r}(\mathbb{E}_+)
= \left\{\bm{A}\in\mathbb{S}^n\relmiddle| \left(\sum_{i=1}^nx_i^2\right)^r(\bm{x}\circ\bm{x})^\top \bm{A}(\bm{x}\circ\bm{x}) \in \Sigma_{n,2r+4}\right\},
\end{equation*}
where we identify $H_{n,2}$ with $\mathbb{S}^n$ in the second equation. Then, $\mathcal{K}_{{\rm NN},r}(\mathbb{E}_+)$ is a closed convex cone for each $r\in\mathbb{N}$ and the sequence $\{\mathcal{K}_{{\rm NN},r}(\mathbb{E}_+)\}_r$ satisfies $\mathcal{K}_{{\rm NN},r}(\mathbb{E}_+) \uparrow \mathcal{COP}(\mathbb{E}_+)$.
\end{corollary}

Our proposed inner-approximation hierarchy for $\mathcal{COP}^{n,m}(\mathbb{E}_+)$ is another generalization of Parrilo's for $\mathcal{COP}^n$ described in Sect.~\ref{subsubsec:Parrilo}. Consider the case of $m = 2$ and $\mathbb{E}_+ = \mathbb{R}_+^n$. Since $\bm{x}\circ\bm{x} = (x_1^2,\dots,x_n^2)$, we have
\begin{equation*}
\mathcal{K}_{{\rm NN},r}(\mathbb{R}_+^n) = \left\{\bm{A}\in\mathbb{S}^n\relmiddle| \left(\sum_{i=1}^nx_i^2\right)^r\sum_{i,j=1}^nA_{ij}x_i^2x_j^2 \in \Sigma_{n,2r+4}\right\},
\end{equation*}
which equals $\mathcal{K}_{{\rm P},r}^n$.

\begin{remark}\label{rem:SOScone}
The proposed inner-approximation hierarchy for $\mathcal{COP}^{n,m}(\mathbb{E}_+)$ can be extended to the case of \textit{SOS cones} proposed by Papp and Alizadeh~\cite{PA2013}. Let $A$ and $B$ be finite-dimensional real vector spaces and $\diamond:A\times A\to B$ be a bilinear mapping. The SOS cone is then defined as
\begin{equation*}
\Sigma_{\diamond} \coloneqq \conv\{x_i \diamond x_i \mid x_i\in A\}. \label{eq:SOScone}
\end{equation*}
As in the case of the Euclidean Jordan algebra, we may assume that $A$ and $B$ are Euclidean spaces without loss of generality and set $A = \mathbb{R}^l$ and $B = \mathbb{R}^n$. Note that each element of $\Sigma_{\diamond}$ can be written as the sum of at most $n$ elements $\bm{x}_1\diamond \bm{x}_1,\dots,\bm{x}_n\diamond\bm{x}_n$ such that $\bm{x}_1,\dots,\bm{x}_n\in\mathbb{R}^l$ by Carath\'{e}odory's theorem for cones~\cite[Exercise~B.1.7]{Bertsekas1999}. If $(A,B,\diamond)$ is formally real, or equivalently, if $\Sigma_{\diamond}$ is proper~\cite[Theorem~3.3]{PA2013}, then
\begin{equation*}
\mathcal{K}_r(\Sigma_{\diamond}) \coloneqq \left\{\theta\in H_{n,m} \relmiddle| \left(\sum_{i=1}^n\sum_{j=1}^l[\bm{x}_i]_j\right)^r\theta\left(\sum_{i=1}^n\bm{x}_i\diamond\bm{x}_i\right) \in \Sigma_{ln,2(m+r)}\right\}
\end{equation*}
is a closed convex cone for each $r\in\mathbb{N}$ and satisfies $\mathcal{K}_r(\Sigma_{\diamond}) \uparrow \mathcal{COP}^{n,m}(\Sigma_{\diamond})$. Note, however, that the number of variables appearing in $\mathcal{K}_r(\Sigma_{\diamond})$ is $l$ times as many as that in $\mathcal{K}_{{\rm NN},r}(\mathbb{E}_+)$. This is because, in general, the convex hull operator is needed to define SOS cones, whereas it is not needed in the case of symmetric cones.
\end{remark}

\section{Generalized doubly nonnegative cone}
\label{sec:DNN}
Let $\mathbb{K}$ be a closed convex cone in $\mathbb{R}^n$. We would like to consider a GDNN cone $\mathcal{DNN}(\mathbb{K})$ for the GCP cone $\mathcal{CP}(\mathbb{K})$. The GDNN cone should inherit as many properties that the DNN cone has as possible. In particular, the following requirements should be satisfied to say that $\mathcal{DNN}(\mathbb{K})$ is a GDNN cone for $\mathcal{CP}(\mathbb{K})$:

\begin{enumerate}[Requ{i}rement~1.]
\item $\mathcal{DNN}(\mathbb{R}_+^n) = \mathcal{DNN}^n$, \label{req:generalization}
\item $\mathcal{DNN}(\mathbb{K})$ is a closed convex cone, \label{req:clconv}
\item $\mathcal{CP}(\mathbb{K}) \subseteq \mathcal{DNN}(\mathbb{K}) \subseteq \mathbb{S}_+^n$, \label{req:inclusion}
\item $\mathcal{DNN}(\mathbb{K})$ is tractable.\label{req:tractable}
\end{enumerate}

Firstly, requirement~\ref{req:generalization} has to be satisfied to regard $\mathcal{DNN}(\mathbb{K})$ as a generalization of the DNN cone. Secondly, $\mathcal{DNN}(\mathbb{K})$ must be a cone to call it a GDNN ``cone.'' In addition, the closedness and convexity of $\mathcal{DNN}(\mathbb{K})$ is favorable in that dualizing it twice yields itself. Thirdly, the GCP cone is included in the semidefinite cone as mentioned in Sect.~\ref{subsec:notation}. Therefore, $\mathcal{DNN}(\mathbb{K})$ must satisfy requirement~\ref{req:inclusion} to provide stronger relaxation than SDP relaxation for GCPP. Finally, as mentioned in Sect.~\ref{sec:intro}, the main reason for considering GDNNP relaxation is to make optimization problems easier to solve on a computer. It is true that for general $\mathbb{K}$, it may be difficult to propose $\mathcal{DNN}(\mathbb{K})$ that is always easy to handle on a computer. However, at least for a cone $\mathbb{K}$ that is likely to appear in real applications such as a symmetric cone, $\mathcal{DNN}(\mathbb{K})$ should be tractable. Therefore, requirement~\ref{req:tractable} is also necessary.

On the basis of these requirements, we provide some candidate GDNN cones in this section. We focus on inner-approximation hierarchies for the GCOP cone to propose GDNN cones. As explained in Sect.~\ref{subsubsec:Parrilo}, the dual cone $(\mathcal{K}_{{\rm P},0}^n)^*$ of the zeroth level of Parrilo's hierarchy agrees with $\mathcal{DNN}^n$. In addition, the two hierarchies described in Sects.~\ref{subsubsec:Zuluaga} and \ref{subsec:proposed_approximation} are generalizations of Parrilo's. Therefore, we define a GDNN cone as the dual cone of the zeroth level of these inner-approximation hierarchies for the GCOP cone.

We first derive a GDNN cone from Zuluaga et al.'s hierarchy $\{\mathcal{K}_{{\rm ZVP},r}(\mathbb{K})\}_r$.

\begin{definition}
Let $\mathbb{K}$ be a semialgebraic pointed closed convex cone in $\mathbb{R}^n$. Then, we define $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})^*$ as the ZVP GDNN cone over $\mathbb{K}$ and write it as $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$.
\end{definition}

We give an explicit expression of $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$. Assume that $\mathbb{K}$ is represented as \eqref{eq:K_semialg}. Recall that $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K}) = \{\bm{A}\in \mathbb{S}^{n}\mid \bm{x}^\top \bm{A}\bm{x}\in E^{n,2}(\mathbb{K})\}$, where
\begin{equation}
E^{n,2}(\mathbb{K}) = \conv\left\{\psi^2\prod_{j=1}^k\phi_{i_j}\relmiddle|
\begin{array}{l}
k\in \mathbb{N},\ 2-\sum_{j=1}^km_{i_j}\in \mathbb{N}\text{ is even},\\
\psi\in H_{n,(2-\sum_{j=1}^km_{i_j})/2},\\
i_j\in \{1,\dots,q\}\ (j=1,\dots,k)
\end{array}
\right\}. \label{eq:EnmK}
\end{equation}
We may assume that $m_i \le 2$ because $\phi_i$ with $m_i \ge 3$ is ignored in constructing $E^{n,2}(\mathbb{K})$ and so $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$. We now express $\mathbb{K}$ as
\begin{equation}
\{\bm{x}\in\mathbb{R}^n\mid \bm{x}^\top \bm{Q}_i\bm{x} \ge 0\ (i=1,\dots,q_2),\ \bm{a}_i^\top\bm{x}\ge 0\ (i=1,\dots,q_1)\},\label{eq:semialg_set_quad}
\end{equation}
where $\bm{Q}_i\in \mathbb{S}^n\ (i = 1,\dots,q_2)$ and $\bm{a}_i\in\mathbb{R}^n\ (i = 1,\dots,q_1)$.

\begin{proposition}\label{prop:K_ZVP}
Suppose that $\mathbb{K}$ is expressed as \eqref{eq:semialg_set_quad}. Then,
\begin{equation*}
\mathcal{K}_{{\rm ZVP},0}(\mathbb{K}) = \mathbb{S}_+^n + \sum_{i=1}^{q_2}\mathbb{R}_+\bm{Q}_i + \sum_{1\le i\le j\le q_1}\mathbb{R}_+ \bm{A}^{ij},
\end{equation*}
where $\bm{A}^{ij} \coloneqq (\bm{a}_i\bm{a}_j^\top + \bm{a}_j\bm{a}_i^\top)/2$.
\end{proposition}

\begin{proof}
Let $\bm{A} \in \mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$. Note that we can replace the convex hull operator in Eq.~\eqref{eq:EnmK} with the conical hull operator because the inner set of the right-hand side of Eq.~\eqref{eq:EnmK} is a cone with zero. Then, since $\bm{x}^\top \bm{A}\bm{x}\in E^{n,2}(\mathbb{K})$, there exist $\bm{\psi}_t\in\mathbb{R}^n$, $\psi_{2(t)}\in\mathbb{R}$, $i_{2(t)}\in\{1,\dots,q_2\}$, $\psi_{1(t)}\in\mathbb{R}$, and $i_{1(t)}$, $j_{1(t)} \in \{1,\dots,q_1\}$ such that
\begin{align*}
\bm{x}^\top \bm{A} \bm{x} &=
\sum_{t}(\bm{\psi}_t^\top\bm{x})^2 + \sum_{t}\psi_{2(t)}^2(\bm{x}^\top \bm{Q}_{i_{2(t)}}\bm{x}) +  \sum_{t}\psi_{1(t)}^2(\bm{a}_{i_{1(t)}}^\top\bm{x}) (\bm{a}_{j_{1(t)}}^\top\bm{x}) \\
&= \bm{x}^\top\left(\sum_{t}\bm{\psi}_t\bm{\psi}_t^\top + \sum_{t}\psi_{2(t)}^2\bm{Q}_{i_{2(t)}} +
\sum_t\psi_{1(t)}^2\bm{A}^{i_{1(t)}j_{1(t)}}\right)\bm{x}.
\end{align*}
Since the above equation holds for all $\bm{x}$, it follows that
\begin{equation*}
\bm{A} = \sum_{t}\bm{\psi}_t\bm{\psi}_t^\top + \sum_{t}\psi_{2(t)}^2\bm{Q}_{i_{2(t)}} +
\sum_t\psi_{1(t)}^2\bm{A}^{i_{1(t)}j_{1(t)}},
\end{equation*}
which belongs to $\mathbb{S}_+^n + \sum_{i=1}^{q_2}\mathbb{R}_+\bm{Q}_i + \sum_{1\le i\le j\le q_1}\mathbb{R}_+ \bm{A}^{ij}$.

Conversely, let $\bm{A} \in \mathbb{S}_+^n + \sum_{i=1}^{q_2}\mathbb{R}_+\bm{Q}_i + \sum_{1\le i\le j\le q_1}\mathbb{R}_+\bm{A}^{ij}$. $\bm{A}$ can then be written as $\bm{P} + \sum_{i=1}^{q_2}\psi_{i} \bm{Q}_i + \sum_{1\le i\le j\le q_1}\psi_{ij}\bm{A}^{ij} $, where $\bm{P} \in \mathbb{S}_+^n$, $\psi_i \ge 0\ (i = 1,\dots,q_2)$, and $\psi_{ij}\ge 0\ (1\le i\le j\le q_1)$. Since $\bm{P} \in \mathbb{S}_+^n$, there exist $\bm{p}_1,\dots,\bm{p}_n\in\mathbb{R}^n$ such that $\bm{P} =\sum_{i=1}^n\bm{p}_i\bm{p}_i^\top$. Therefore,
\begin{equation*}
\bm{x}^\top \bm{A}\bm{x} = \sum_{i=1}^n(\bm{p}_i^\top\bm{x})^2 + \sum_{i=1}^{q_2}({\textstyle \sqrt{\psi_i}})^2\bm{x}^\top \bm{Q}_i\bm{x} + \sum_{1\le i\le j\le q_1}({\textstyle \sqrt{ \psi_{ij}}})^2(\bm{a}_i^\top\bm{x})(\bm{a}_j^\top\bm{x}) ,
\end{equation*}
which belongs to $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$.
\end{proof}

\begin{corollary}\label{cor:DNN_ZVP}
Suppose that $\mathbb{K}$ is expressed as \eqref{eq:semialg_set_quad}. Then,
\begin{align*}
&\mathcal{DNN}_{\rm ZVP}(\mathbb{K}) \\
&\quad= \mathbb{S}_+^n \cap \bigcap_{i=1}^{q_2}\{\bm{X}\in\mathbb{S}^n\mid \langle \bm{Q}_i,\bm{X}\rangle \ge 0\} \cap \bigcap_{1\le i\le j\le q_1}\{\bm{X}\in \mathbb{S}^n\mid \langle \bm{A}^{ij},\bm{X}\rangle \ge 0\}.
\end{align*}
\end{corollary}

\begin{proof}
Note that for $\bm{S}\in\mathbb{S}^n$, we have $(\mathbb{R}_+ \bm{S})^* = \{\bm{X}\in \mathbb{S}^n\mid \langle \bm{S},\bm{X}\rangle \ge 0\}$. In addition, for any closed convex cones $\mathcal{K}_1,\dots,\mathcal{K}_k$, $(\sum_{i=1}^k\mathcal{K}_i)^* = \bigcap_{i=1}^k\mathcal{K}^*$ holds. Using these facts, we obtain the desired result by taking the dual in Proposition~\ref{prop:K_ZVP}.
\end{proof}

The ZVP GDNN cone $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ satisfies all of the requirements listed at the beginning of Sect.~\ref{sec:DNN}. Firstly, $\mathcal{DNN}_{\rm ZVP}(\mathbb{R}_+^n;\bm{1}_n) = \mathcal{DNN}^n$ follows from the fact that $\mathcal{K}_{{\rm ZVP},r}(\mathbb{R}_+^n;\bm{1}_n)$ equals $\mathcal{K}_{{\rm P},r}^n$. Secondly, we see that $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ is a closed convex cone since it is obtained by dualizing $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$. Thirdly, $\mathcal{DNN}_{\rm ZVP}(\mathbb{K}) \subseteq \mathbb{S}_+^n$ follows from Corollary~\ref{cor:DNN_ZVP}. The inclusion $\mathcal{CP}(\mathbb{K}) \subseteq \mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ also holds, since $\mathcal{K}_{{\rm ZVP},r}(\mathbb{K}) \uparrow \mathcal{COP}(\mathbb{K})$, as well as the fact that $\mathcal{CP}(\mathbb{K})$ and $\mathcal{COP}(\mathbb{K})$ are dual with each other. Finally, Corollary~\ref{cor:DNN_ZVP} implies that $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ is characterized by a semidefinite constraint and linear inequality constraints. This means that $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ is tractable. Therefore, it is reasonable to call $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ a GDNN cone.

Note that unlike $\mathbb{S}_+^n +\mathcal{N}^n$, which is closed, $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$ is not closed in general. Therefore, the dual cone of $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ is not $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$ itself but the closure of it. However, at least when $\mathbb{K}$ is a direct product of a nonnegative orthant, and second-order cones or semidefinite cones, $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$ is closed (see Sects.~\ref{subsec:soc} and~\ref{subsec:sdc}).

Next, we derive a GDNN cone from our proposed hierarchy $\{\mathcal{K}_{{\rm NN},r}(\mathbb{K})\}_r$.
\begin{definition}
Let $\mathbb{K}$ be a symmetric cone in $\mathbb{R}^n$. We then define $\mathcal{K}_{{\rm NN},0}(\mathbb{K})^*$ as the NN GDNN cone over $\mathbb{K}$ and write it as $\mathcal{DNN}_{\rm NN}(\mathbb{K})$.
\end{definition}

The NN GDNN cone $\mathcal{DNN}_{\rm NN}(\mathbb{K})$ also satisfies all of the requirements listed at the beginning of Sect.~\ref{sec:DNN}. Requirement~\ref{req:generalization} holds since $\mathcal{K}_{{\rm NN},r}(\mathbb{R}_+^n)$ equals $\mathcal{K}_{{\rm P},r}^n$. Requirement~\ref{req:clconv} and $\mathcal{CP}(\mathbb{K}) \subseteq \mathcal{DNN}_{\rm NN}(\mathbb{K})$ in requirement~\ref{req:inclusion} hold for the same reason as the ZVP GDNN cone. In addition, for any $\bm{A} \in \mathbb{S}_+^n$, there exists $\bm{U}\in \mathbb{R}^{n\times n}$ such that $\bm{A}$ can be decomposed into $\bm{U}^\top \bm{U}$. For each $\bm{x}\in\mathbb{R}^n$, since each element of $\bm{x}\circ \bm{x}$ is a quadratic form, we let $\bm{x}\circ \bm{x} = (\phi_1(\bm{x}),\dots,\phi_n(\bm{x}))$, where $\phi_i(\bm{x})\in H_{n,2}$ for $i = 1,\dots,n$. Then, we get
\begin{equation*}
(\bm{x}\circ\bm{x})^\top \bm{A} (\bm{x}\circ\bm{x}) = \|\bm{U}(\bm{x}\circ\bm{x})\|^2
= \sum_{i=1}^n\left(\sum_{j=1}^nU_{ij}\phi_j(\bm{x})\right)^2 \in \Sigma_{n,4}.
\end{equation*}
Therefore, $\mathbb{S}_+^n \subseteq \mathcal{K}_{{\rm NN},0}(\mathbb{K})$ and so $\mathcal{DNN}_{\rm NN}(\mathbb{K}) \subseteq \mathbb{S}_+^n$ hold. Moreover, since $\mathcal{K}_{{\rm NN},0}(\mathbb{K})$ is defined with $\Sigma_{n,4}$, the condition that a matrix belongs to $\mathcal{K}_{{\rm NN},0}(\mathbb{K})$ can be represented by a semidefinite constraint and so $\mathcal{DNN}_{\rm NN}(\mathbb{K})$ is also tractable. It is thus also reasonable to call $\mathcal{DNN}_{\rm NN}(\mathbb{K})$ a GDNN cone. As mentioned in Corollary~\ref{cor:inner_approx_COP}, since $\mathcal{K}_{{\rm NN},0}(\mathbb{K})$ is always closed (unlike $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$), the dual of $\mathcal{DNN}_{\rm NN}(\mathbb{K})$ is precisely $\mathcal{K}_{{\rm NN},0}(\mathbb{K})$.
\begin{remark}
Similarly, for an SOS cone $\Sigma_{\diamond}$ introduced in Remark~\ref{rem:SOScone}, because $\mathcal{K}_0(\Sigma_{\diamond})^*$ also satisfies the four requirements, we can define it as the GDNN cone over an SOS cone.
\end{remark}

Above, we proposed two GDNN cones based on the inner-approximation hierarchies for the GCOP cone. On the other hand, Burer and Dong~\cite{BD2012} proposed another GDNN cone over a closed convex cone from a perspective other than inner-approximation hierarchies.

\begin{definition}[{\cite[Sect.~4]{BD2012}}]
For a closed convex cone $\mathbb{K}$ in $\mathbb{R}^n$, the BD GDNN cone $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ is defined by $\mathbb{S}_+^n \cap \mathcal{N}(\mathbb{K})$, where $\mathcal{N}(\mathbb{K})\coloneqq \{\bm{X}\in\mathbb{S}^n\mid \bm{X}\bm{s}\in\mathbb{K}\ \text{for all $\bm{s}\in \Ext(\mathbb{K}^*)$}\}$.
\end{definition}

We discuss whether it is reasonable to call $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ a GDNN cone based on the four requirements listed at the beginning of Sect.~\ref{sec:DNN}. Firstly, since $\Ext(\mathbb{R}_+^n) = \{a\bm{e}_i\mid a\ge 0,\ i=1,\dots,n\}$, $\mathcal{N}(\mathbb{R}_+^n) = \mathcal{N}^n$ holds and we have $\mathcal{DNN}_{\rm BD}(\mathbb{R}_+^n) = \mathcal{DNN}^n$. Secondly, using the assumption that $\mathbb{K}$ is a closed convex cone, we can easily show that $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ is also a closed convex cone. Thirdly, it is obvious that $\mathcal{DNN}_{\rm BD}(\mathbb{K}) \subseteq \mathbb{S}_+^n$ by definition. The inclusion $\mathcal{CP}(\mathbb{K}) \subseteq \mathcal{DNN}_{\rm BD}(\mathbb{K})$ has been proved in \cite[Proposition~3]{BD2012}. Finally, as a special case, if $\mathbb{K}$ is a direct product of a nonnegative orthant and second-order cones, then $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ is tractable, as will be seen in Sect.~\ref{subsec:soc}. Therefore, we may refer to $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ as a GDNN cone. However, it is difficult to show that $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ is tractable for a general closed convex cone $\mathbb{K}$. We will demonstrate this in the case where $\mathbb{K}$ is a direct product of a nonnegative orthant and semidefinite cones in Sect.~\ref{subsec:sdc}.

\begin{remark}
When we consider that the ZVP and NN GDNN cones are obtained by inner-approximation hierarchies, we can assume that the BD GDNN cone is obtained by the reformulation-linearization technique (RLT)~\cite{SA1999}. To explain this, we give another representation of $\mathcal{N}(\mathbb{K})$ when $\mathbb{K}$ is a \textit{solid} closed convex cone.

\begin{lemma}\label{lem:GNNcone}
Suppose that $\mathbb{K}$ is a solid closed convex cone. Then, $\mathcal{N}(\mathbb{K}) = \{\bm{X}\in\mathbb{S}^n\mid \bm{X}\bm{s}\in\mathbb{K}\ \text{for all $\bm{s}\in \mathbb{K}^*$}\}$.
\end{lemma}

\begin{proof}
Since the inclusion ``$\supseteq$'' is obvious, we only show ``$\subseteq$.'' Let $\bm{X}\in\mathcal{N}(\mathbb{K})$. It then follows that $\bm{X}\bm{s}'\in\mathbb{K}$ for all $\bm{s}'\in \Ext(\mathbb{K}^*)$. Under the assumption on $\mathbb{K}$, the dual cone $\mathbb{K}^*$ is a pointed closed convex cone. Therefore, it follows from Choquet's theorem~\cite[Sect.~13]{Phelps2001} that $\mathbb{K}^* = \clconv(\Ext(\mathbb{K}^*))$, where $\clconv(\cdot)$ is the closure of the convex hull of a set. Now, let $\bm{s}\in \mathbb{K}^*$. There then exists $\{\bm{s}^k\}_k\subseteq \conv(\Ext(\mathbb{K}^*))$ such that $\bm{s}^k\to\bm{s}\ (k\to\infty)$. For each $\bm{s}^k$, using Carath\'{e}odory's theorem for cones, there exist $\bm{s}^{k,i}\in \Ext(\mathbb{K}^*)\ (i = 1,\dots,n)$ and $\lambda^{k,i}$ with $\lambda^{k,i}\ge 0\ (i = 1,\dots,n)$ and $\sum_{i=1}^n\lambda^{k,i} = 1$ such that $\bm{s}^k = \sum_{i=1}^n\lambda^{k,i}\bm{s}^{k,i}$. Then, $\bm{X}\bm{s}^k = \sum_{i=1}^n\lambda^{k,i}\bm{X}\bm{s}^{k,i}\in \mathbb{K}$, since $\bm{X}\bm{s}^{k,i}\in\mathbb{K}$ and $\mathbb{K}$ is convex. Taking the limit $k\to\infty$, by the closedness of $\mathbb{K}$, we obtain $\bm{X}\bm{s}\in\mathbb{K}$.
\end{proof}

Now, consider the case where $\mathbb{K}$ is a solid \textit{polyhedral} cone, i.e., $\mathbb{K} = \{\bm{x}\in\mathbb{R}^n\mid \bm{A}\bm{x}\in\mathbb{R}_+^m\}$ for some $\bm{A}\in\mathbb{R}^{n\times m}$. The dual cone of $\mathbb{K}$ is $\{\bm{A}^\top \bm{y}\mid \bm{y}\in\mathbb{R}_+^m\}$. Then, it follows that
\begin{equation}
\mathcal{N}(\mathbb{K}) = \{\bm{X}\in\mathbb{S}^n\mid \bm{A}\bm{X}\bm{A}^\top \in\mathcal{N}^m\}. \label{eq:GNNcone_polyhedral}
\end{equation}
Indeed, let $\bm{X}\in\mathcal{N}(\mathbb{K})$. Then, from Lemma~\ref{lem:GNNcone}, we see that $\bm{A}(\bm{X}(\bm{A}^\top\bm{y})) \in\mathbb{R}_+^m$ for all $\bm{y}\in\mathbb{R}_+^m$. Since $\bm{y}\in\mathbb{R}_+^m$ is arbitrary, $\bm{A}\bm{X}\bm{A}^\top\in\mathcal{N}^m$ holds. Conversely, let $\bm{X}\in\mathbb{S}^n$ be a matrix such that $\bm{A}\bm{X}\bm{A}^\top\in\mathcal{N}^m$. Then, for any $\bm{A}^\top\bm{y}\in\mathbb{K}^*$ $(\bm{y}\in\mathbb{R}_+^m)$, since each row vector in $\bm{A}\bm{X}\bm{A}^\top$ is nonnegative, we have $\bm{A}(\bm{X}(\bm{A}^\top\bm{y}))\in\mathbb{R}_+^m$. Therefore, by Lemma~\ref{lem:GNNcone}, we obtain $\bm{X}\in\mathcal{N}(\mathbb{K})$. On the other hand, the constraint $\bm{A}\bm{X}\bm{A}^\top\in \mathcal{N}^m$ in Eq.~\eqref{eq:GNNcone_polyhedral} is obtained from the RLT for $\mathbb{K}$. Using $\bm{A}\bm{x}\in\mathbb{R}_+^m$, we have $\bm{A}\bm{x}\bm{x}^\top \bm{A}\in\mathcal{N}^m$. Linearizing $\bm{x}\bm{x}^\top$ with $\bm{X}\in\mathbb{S}^n$ leads to the above constraint. In fact, Burer and Dong~\cite{BD2013} (see also \cite{Dong2011}) considered the intersection of the semidefinite cone and the set~\eqref{eq:GNNcone_polyhedral} to be a generalization of the GDNN cone when $\mathbb{K}$ is a polyhedral cone (although the additional conditions on $\mathbb{K}$ are somewhat different).
\end{remark}

Finally, we provide a simpler representation of $\mathcal{N}(\mathbb{K})$ and $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ when $\mathbb{K}$ is a symmetric cone in $\mathbb{R}^n$, which we will use later. Recall that symmetric cones are self-dual. The next lemma states that $\Ext(\mathbb{K})$ is characterized by $\mathfrak{J}(\mathbb{K})$.

\begin{lemma}[{\cite[Corollary~12]{IL2017}}]\label{lem:characterization_ext}
Let $\bm{x}\in\mathbb{K}$ be given. Then, $\bm{x}\in \Ext(\mathbb{K})$ if and only if there exist $\alpha\ge 0$ and $\bm{c}\in\mathfrak{J}(\mathbb{K})$ such that $\bm{x} = \alpha\bm{c}$.
\end{lemma}

Lemma~\ref{lem:characterization_ext} immediately leads to the following lemma that we desired to have.

\begin{lemma}\label{lem:GNNcone_symmetric}
Let $\mathbb{K}$ be a symmetric cone in $\mathbb{R}^n$. Then, $\mathcal{N}(\mathbb{K}) = \{\bm{X}\in\mathbb{S}^n\mid \bm{X}\bm{s}\in\mathbb{K}\ \text{for all $\bm{s}\in \mathfrak{J}(\mathbb{K})$}\}$.
\end{lemma}

\section{Analysis on three generalized doubly nonnegative cones}
\label{sec:relationship}
In the previous section, we proposed two GDNN cones: $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ and $\mathcal{DNN}_{\rm NN}(\mathbb{K})$. We also introduced another GDNN cone, $\mathcal{DNN}_{\rm BD}(\mathbb{K})$, proposed by Burer and Dong~\cite{BD2012}. Note that the class of cones $\mathbb{K}$ for which each GDNN cone can be defined is different, and we cannot compare the three cones in the case where $\mathbb{K}$ is a general closed convex cone. That is, $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ is defined for semialgebraic pointed closed convex cones, whereas $\mathcal{DNN}_{\rm NN}(\mathbb{K})$ is defined for symmetric cones. Thus, in this section, we consider two special cases so that all three cones can be defined: one is the case where $\mathbb{K}$ is a direct product of a nonnegative orthant and second-order cones, and the other is the case where $\mathbb{K}$ is a direct product of a nonnegative orthant and semidefinite cones. Note that how we choose the vector $\bm{a}$ in the ZVP GDNN cone $\mathcal{DNN}_{\rm ZVP}(\mathbb{K};\bm{a})$ is a problem because the three GDNN cones are difficult to compare if we do not fix $\bm{a}$. In the case of $\mathbb{K} = \mathbb{R}_+^n$, $\bm{a} = \bm{1}_n$ gives the most natural generalization of $\mathcal{DNN}^n$ in that the hierarchy $\{\mathcal{K}_{{\rm ZVP},r}(\mathbb{R}_+^n;\bm{1}_n)\}_r$ directly reduces to Parrilo's. \footnote{However, $\mathcal{DNN}_{\rm ZVP}(\mathbb{R}_+^n;\bm{a})$ does not depend on the choice of $\bm{a}\in\setint(\mathbb{R}_+^n)$ since $E^{n,2}(\mathbb{R}_+^n;\bm{a}) = E^{n,2}(\mathbb{R}_+^n;\bm{1}_n)$.} Note that the vector $\bm{1}_n$ is the identity element of the Euclidean Jordan algebra associated with $\mathbb{R}_+^n$. As stated in Sect.~\ref{subsec:EJA}, since the identity element $\bm{e}$ of a Euclidean Jordan algebra $\mathbb{E}$ is in the interior of the associated symmetric cone $\mathbb{E}_+$, $\mathbb{E}_+$ and $\bm{e}$ satisfy Eqs.~\eqref{eq:exposed_face_1} and \eqref{eq:exposed_face_2}. Therefore, when $\mathbb{K}$ is a semialgebraic symmetric cone, we hereafter take $\bm{a}$ as the identity element of the Euclidean Jordan algebra associated with $\mathbb{K}$ and no longer specify it.

\subsection{When $\mathbb{K}$ is a direct product of a nonnegative orthant and second-order cones}
\label{subsec:soc}
In this subsection, we consider the case where $\mathbb{K}$ is a direct product of a nonnegative orthant and second-order cones, i.e., $\mathbb{K} = \mathbb{R}^{n_1}\times \prod_{h=2}^N\mathbb{L}^{n_h}$, and let $n \coloneqq \sum_{h=1}^Nn_h$. For convenience, we reindex $(1,\dots,n)$ as $(11,\dots,1n_1,21,\dots,2n_2,\dots,N1,\dots,Nn_N)$, i.e., let $hi \coloneqq \sum_{k=1}^{h-1}n_k + i$ for $h = 1,\dots,N$ and $i = 1,\dots,n_h$. Moreover, we set $\mathcal{I}_h \coloneqq \{h1,\dots,hn_h\}\ (h = 1,\dots,N)$, $\mathcal{I}_h^- \coloneqq \mathcal{I}_h\setminus\{h1\}\ (h = 2,\dots,N)$, and $\mathcal{I}_{\ge 0}\coloneqq \mathcal{I}_1\cup \bigcup_{h=2}^N\{h1\}$. We will also use this notation in Sect.~\ref{sec:experiment}.

When $\mathbb{K}$ is expressed as \eqref{eq:semialg_set_quad}, we have already given an explicit expression of $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ in Corollary~\ref{cor:DNN_ZVP}. However, in this case, $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ can be expressed in a simpler way.

\begin{proposition}\label{prop:K_ZVP_SOC}
Let $\bm{J}_{h}$ be the $n\times n$ matrix such that the $(h1,h1)$th element is $1$, $(h2,h2),\dots,(hn_h,hn_h)$th elements are $-1$, and other elements are $0$ for $h = 2,\dots,N$. Then,
\begin{equation}
\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})
= \mathbb{S}_+^n + \sum_{h=2}^N\mathbb{R}_+\bm{J}_h
+ \left\{\bm{N}\in\mathbb{S}^n\relmiddle|
N_{IJ} \begin{cases}
\ge 0& (I,J\in\mathcal{I}_{\ge 0})\\
= 0& (otherwise)
\end{cases}
\right\}.\label{eq:K_ZVP_SOC}
\end{equation}
\end{proposition}

\begin{proof}
For simplicity, we write the last set in the right-hand side of Eq.~\eqref{eq:K_ZVP_SOC} as $\mathcal{N}_{\ge 0}$. The identity element $\bm{e}$ of the Euclidean Jordan algebra associated with $\mathbb{K}$ is the vector with $I$th $(I\in\mathcal{I}_{\ge 0})$ elements 1 and the others 0. Then, as a semialgebraic representation of $\mathbb{K}$, we obtain
\begin{equation*}
\left\{\bm{x}\in\mathbb{R}^n \relmiddle|
\begin{array}{l}
\bm{e}_I^\top\bm{x} = x_I  \ge 0\ (I\in\mathcal{I}_{\ge 0}),\\
\bm{e}^\top\bm{x} = \sum_{I\in\mathcal{I}_{\ge 0}}x_I \ge 0,\\
\bm{x}^\top\bm{J}_h\bm{x} = x_{h1}^2 - \sum_{I\in\mathcal{I}_h^-}x_I^2 \ge 0\ (h=2,\dots,N)
\end{array}\right\}.
\end{equation*}
Let $\bm{E}^{IJ} \coloneqq (\bm{e}_I\bm{e}_J^\top + \bm{e}_J\bm{e}_I^\top)/2$, $\bm{E}_I \coloneqq (\bm{e}_I\bm{e}^\top + \bm{e}\bm{e}_I^\top)/2$, and $\bm{E} \coloneqq \bm{e}\bm{e}^\top$. By Proposition~\ref{prop:K_ZVP}, we have
\begin{equation*}
\mathcal{K}_{{\rm ZVP},0}(\mathbb{K}) = \mathbb{S}_+^n + \sum_{h=2}^N\mathbb{R}_+\bm{J}_h + \sum_{\substack{I\le J\\I,J\in\mathcal{I}_{\ge 0}}}\mathbb{R}_+\bm{E}^{IJ} + \sum_{I\in\mathcal{I}_{\ge 0}}\mathbb{R}_+\bm{E}_I + \mathbb{R}_+\bm{E}.
\end{equation*}
Therefore, it is sufficient to show that
\begin{equation*}
\sum_{\substack{I\le J\\I,J\in\mathcal{I}_{\ge 0}}}\mathbb{R}_+\bm{E}^{IJ} + \sum_{I\in\mathcal{I}_{\ge 0}}\mathbb{R}_+\bm{E}_I + \mathbb{R}_+\bm{E} = \mathcal{N}_{\ge 0}.
\end{equation*}
Since $\bm{e}_I\ (I\in\mathcal{I}_{\ge 0})$ and $\bm{e}$ are nonnegative vectors with only $I$th ($I\in\mathcal{I}_{\ge 0}$) elements positive, the matrices $\bm{E}^{IJ}$, $\bm{E}_I$, and $\bm{E}$ are in $\mathcal{N}_{\mathcal {I}_{\ge 0}}$, which implies the ``$\subseteq$" part. Conversely, let $\bm{N}\in \mathcal{N}_{\ge 0}$. Then,
\begin{equation*}
\bm{N} = \sum_{\substack{I< J\\I,J\in\mathcal{I}_{\ge 0}}}2N_{IJ}\bm{E}^{IJ} + \sum_{I\in\mathcal{I}_{\ge 0}}N_{II}\bm{E}^{II}\in \sum_{\substack{I\le J\\I,J\in\mathcal{I}_{\ge 0}}}\mathbb{R}_+ \bm{E}^{IJ},
\end{equation*}
which implies the ``$\supseteq$'' part. This completes the proof.
\end{proof}

\begin{corollary}\label{cor:GDNN_ZVP_SOC}
\begin{multline*}
\mathcal{DNN}_{\rm ZVP}(\mathbb{K}) =
\mathbb{S}_+^n \cap \bigcap_{h=2}^N\{\bm{X}\in\mathbb{S}^n\mid \langle\bm{J}_h,\bm{X}\rangle\ge 0\}\\
\cap\{\bm{N}\in\mathbb{S}^n\mid N_{IJ}\ge 0\ (I,J\in\mathcal{I}_{\ge 0})\}.
\end{multline*}
\end{corollary}

\begin{remark}\label{rem:KZVP_closed}
We mentioned that $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$ is not closed for a general semialgebraic pointed closed convex cone. However, $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$ is closed in this case. To prove this, we prepare an additional lemma that claims a sufficient condition that the Minkowski sum of pointed closed convex cones is closed. Because it is just a slight modification of \cite[Corollary~9.1.3]{Rockafellar1970}, we omit the proof.

\begin{lemma}\label{lem:minlovski_closed}
Let $\mathcal{K}_i \subseteq \mathbb{S}^n\ (i = 1,\dots,m)$ be pointed closed convex cones satisfying the following condition: for any $\bm{X}_i\in\mathcal{K}_i\ (i = 1,\dots,m)$, if $\sum_{i=1}^m\bm{X}_i = \bm{O}$, then $\bm{X}_i = \bm{O}$ for all $i = 1,\dots,m$. Then, $\sum_{i=1}^m\mathcal{K}_i$ is closed.
\end{lemma}

Now, let $\bm{P}\in\mathbb{S}_+^n$, $t_h\ge 0\ (h = 2,\dots,N)$, and $\bm{N}\in\mathcal{N}_{\ge 0}$ and suppose that
\begin{equation*}
\bm{A} = \bm{P} + \sum_{h=2}^Nt_h\bm{J}_h + \bm{N} = \bm{O}.
\end{equation*}
For every $h = 2,\dots,N$, since $A_{h1h1} = P_{h1h1} + t_h + N_{h1h1} = 0$ and each term is nonnegative, we have $P_{h1h1} = t_h = 0$. Given that $t_h = 0$ for all $h = 2,\dots,m$, for each $I \in \mathcal{I}_1\cup\bigcup_{h=2}^N\mathcal{I}_h^-$, since $A_{II} = P_{II} + N_{II} = 0$ and $P_{II}$ and $N_{II}$ are nonnegative, we have $P_{II} = 0$. Therefore, the diagonal elements of $\bm{P}$ are all 0 and so $\bm{P} = \bm{O}$ since $\bm{P}\in\mathbb{S}_+^n$. Finally, we obtain $\bm{A} = \bm{N} = \bm{O}$. Obviously, $\mathbb{S}_+^n$ and $\mathbb{R}_+\bm{J}_h\ (h=2,\dots,N)$ are pointed closed convex cones. In addition, since $\mathcal{N}_{\ge 0}\subseteq \mathcal{N}^n$, $\mathcal{N}_{\ge 0}$ is also a pointed closed convex cone. $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$ is thus closed by Lemma~\ref{lem:minlovski_closed}.
\end{remark}

Next, we give an explicit expression of $\mathcal{DNN}_{\rm NN}(\mathbb{K})$.

\begin{definition}\label{def:C}
For $\bm{y} = (y_\delta)_{\delta \in I(n,4)} \in \mathbb{R}^{I(n,4)}$, let $\bm{C}_0(\bm{y})\in\mathbb{S}^n$ be the matrix with the $(I,J)$th element:
\begin{alignat}{2}
&y_{2(\bm{e}_I+\bm{e}_J)} &\quad& (I,J\in\mathcal{I}_1), \label{def:eq:C1}\\
&\sum_{K\in\mathcal{I}_h}y_{2(\bm{e}_I+\bm{e}_K)} &\quad& (I\in\mathcal{I}_1,\ J = h1,\ h = 2,\dots,N), \label{def:eq:C2}\\
&2y_{2\bm{e}_I+\bm{e}_{h1}+\bm{e}_J} &\quad& (I\in\mathcal{I}_1,\ J\in\mathcal{I}_h^-,\ h = 2,\dots,N), \nonumber\\
&\sum_{K\in\mathcal{I}_g}\sum_{L\in\mathcal{I}_h} y_{2(\bm{e}_K+\bm{e}_L)} &\quad& (I=g1,\ J=h1,\ g,h=2,\dots,N),\label{def:eq:C8}\\
&\sum_{K\in\mathcal{I}_g} 2y_{2\bm{e}_K+\bm{e}_{h1}+\bm{e}_J} &\quad& (I=g1,\ J\in\mathcal{I}_h^-,\ g,h=2,\dots,N), \nonumber\\
&4y_{\bm{e}_{g1}+\bm{e}_I+\bm{e}_{h1}+\bm{e}_J} &\quad& (I\in\mathcal{I}_g^-,\ J\in\mathcal{I}_h^-,\ g,h=2,\dots,N).\nonumber
\end{alignat}
Then, we define $\mathcal{C}_0(\mathbb{K}) \coloneqq \{\bm{C}_0(\bm{y})\mid \bm{y}\in \mathcal{M}_{n,4}\}$.
\end{definition}

We show that $\mathcal{C}_0(\mathbb{K})$ is exactly $\mathcal{DNN}_{\rm NN}(\mathbb{K})$.

\begin{lemma}\label{lem:C_dual}
$\mathcal{K}_{{\rm NN},0}(\mathbb{K}) =\mathcal{C}_0(\mathbb{K})^*.$
\end{lemma}

\begin{proof}
For $\bm{A}\in\mathbb{S}^n$, let $P(\bm{x};\bm{A}) \coloneqq (\bm{x}\circ\bm{x})^\top \bm{A}(\bm{x}\circ\bm{x})$ for $\bm{x}\in\mathbb{R}^n$. Then, since
\begin{align*}
\bm{x}\circ\bm{x} = \left[(x_I^2)_{I\in\mathcal{I}_1},\left(\sum_{I\in\mathcal{I}_h}x_I^2,(2x_{h1}x_I)_{I\in\mathcal{I}_h^-}\right)_{h=2,\dots,N}\right],
\end{align*}
we see that $P(\bm{x};\bm{A})$ is equal to

\begin{align*}
&\sum_{I,J\in\mathcal{I}_1}A_{IJ}x_I^2x_J^2
+2\sum_{h=2}^N\sum_{I\in\mathcal{I}_1}\sum_{K\in\mathcal{I}_h}A_{Ih1}x_I^2x_K^2 + 2\sum_{h=2}^N\sum_{I\in\mathcal{I}_1}\sum_{J\in\mathcal{I}_h^-}A_{IJ}(2x_I^2x_{h1}x_J)\\
&+ \sum_{g,h=2}^N\sum_{K\in\mathcal{I}_g}\sum_{L\in\mathcal{I}_h}A_{g1h1}x_K^2x_L^2 + 2\sum_{g,h=2}^N\sum_{J\in\mathcal{I}_h^-}\sum_{K\in\mathcal{I}_g}A_{g1J}(2x_K^2x_{h1}x_J)\\
&+ \sum_{g,h=2}^N\sum_{I\in\mathcal{I}_g^-}\sum_{J\in\mathcal{I}_h^-}A_{IJ}(4x_{g1}x_Ix_{h1}x_J).
\end{align*}
Therefore, let $\bm{p}_{\bm{A}} \in \mathbb{R}^{I(n,4)}$ be the coefficient vector of $P(\bm{x};\bm{A})$, and then
\begin{equation}
\bm{y}^\top\bm{p}_{\bm{A}} = \langle \bm{C}_0(\bm{y}),\bm{A}\rangle \label{eq:C_dual}
\end{equation}
for all $\bm{y}\in \mathbb{R}^{I(n,4)}$.

Now, let $\bm{A} \in \mathcal{K}_{{\rm NN},0}(\mathbb{K})$. Then, $\bm{p}_{\bm{A}}\in \Sigma_{n,4}$ by the definition of $\mathcal{K}_{{\rm NN},0}(\mathbb{K})$. Therefore, for any $\bm{y}\in\mathcal{M}_{n,4}$, it follows from Eq.~\eqref{eq:C_dual} and the duality between $\Sigma_{n,4}$ and $\mathcal{M}_{n,4}$ that $\langle \bm{C}_0(\bm{y}),\bm{A}\rangle \ge 0$. Since $\bm{y}$ is arbitrary, we have $\bm{A} \in \mathcal{C}_0(\mathbb{K})^*$.

Conversely, let $\bm{A} \in \mathcal{C}_0(\mathbb{K})^*$. For any $\bm{y}\in\mathcal{M}_{n,4}$, it follows from $\bm{C}_0(\bm{y})\in\mathcal{C}_0(\mathbb{K})$ and the definition of a dual cone that $\bm{y}^\top \bm{p}_{\bm{A}} = \langle \bm{C}_0(\bm{y}),\bm{A}\rangle \ge 0$. Since $\bm{y} \in \mathcal{M}_{n,4}$ is arbitrary, we obtain $\bm{p}_{\bm{A}} \in \Sigma_{n,4}$, which implies that $\bm{A}\in \mathcal{K}_{{\rm NN},0}(\mathbb{K})$. This completes the proof.
\end{proof}

\begin{lemma}\label{lem:C_is_closed}
The set $\mathcal{C}_0(\mathbb{K})$ is a closed convex cone.
\end{lemma}

\begin{proof}
We can easily show that $\mathcal{C}_0(\mathbb{K})$ is a convex cone from the fact that $\bm{C}_0(\bm{y})$ is linear with respect to $\bm{y}$ and $\mathcal{M}_{n,4}$ is a convex cone. In what follows, we prove the closedness of $\mathcal{C}_0(\mathbb{K})$.
Let $\{\bm{y}^{(k)}\}_k \subseteq \mathcal{M}_{n,4}$ and suppose that $\bm{C}_0(\bm{y}^{(k)})$ converges to some $\bm{C}_0^*$ in the limit $k\to\infty$. It follows from the definition of $\mathcal{M}_{n,4}$ that $\bm{M}_{n,4}(\bm{y}^{(k)})\in\mathbb{S}_+^{I(n,2)}$, and in particular, the diagonal elements of $\bm{M}_{n,4}(\bm{y}^{(k)})$ are nonnegative. Hence, we see that
\begin{equation}
y_{2\bm{\gamma}}^{(k)} \ge 0\quad\text{for all $\bm{\gamma}\in I(n,2)$}. \label{eq:nonneg_y}
\end{equation}
Since $\bm{C}_0(\bm{y}^{(k)}) \to \bm{C}_0^*$, each element of $\bm{C}_0(\bm{y}^{(k)})$ defined by Definition~\ref{def:C} is bounded. Specifically,
\begin{enumerate}[(i)]
\item $\{y_{2(\bm{e}_I + \bm{e}_J)}^{(k)}\}_k$ is bounded for all $I$, $J\in\mathcal{I}_1$ (see \eqref{def:eq:C1}). \label{enum:1}

\item For each $h = 2,\dots,N$, $\{\sum_{J\in\mathcal{I}_h}y_{2(\bm{e}_I+\bm{e}_J)}^{(k)}\}$ is bounded for all $I\in\mathcal{I}_1$ (see \eqref{def:eq:C2}). Therefore, we see from \eqref{eq:nonneg_y} that $\{y_{2(\bm{e}_I+\bm{e}_J)}^{(k)}\}_k$ is bounded for all $I\in\mathcal{I}_1$ and $J\in\mathcal{I}_h$. \label{enum:3}

\item For each $g$, $h = 2,\dots,N$, $\{\sum_{I\in\mathcal{I}_g}\sum_{J\in\mathcal{I}_h} y_{2(\bm{e}_I+\bm{e}_J)}^{(k)}\}_k$ is bounded (see \eqref{def:eq:C8}). Therefore, $\{y_{2(\bm{e}_I+\bm{e}_J)}^{(k)}\}_k$ is bounded for all $I\in\mathcal{I}_g$ and $J\in\mathcal{I}_h$. \label{enum:5}
\end{enumerate}
Since $I(n,2) = \{\bm{e}_I + \bm{e}_J \mid 1\le I\le J\le n\}$, it follows from \eqref{enum:1} to \eqref{enum:5} that $\{y_{2\bm{\gamma}}^{(k)}\}_k$ is bounded for all $\bm{\gamma} \in I(n,2)$, which means the boundedness of the diagonal elements of $\bm{M}_{n,4}(\bm{y}^{(k)})$.
Combining the boundedness with the semidefiniteness of $\bm{M}_{n,4}(\bm{y}^{(k)})$ yields the boundedness of each element of $\bm{M}_{n,4}(\bm{y}^{(k)})$. Therefore, $\{\bm{y}^{(k)}\}_k$ is also bounded since $y_{\bm{\delta}}^{(k)}$ is one of the elements of $\bm{M}_{n,4}(\bm{y}^{(k)})$ for each $\bm{\delta} \in I(n,4)$. Thus, there exists a convergent subsequence $\{\bm{y}^{(k_r)}\}_r$ and $\bm{y}^*$ is the limit of $\{\bm{y}^{(k_r)}\}_r$. Then, since $\mathcal{M}_{n,4}$ is closed and $\bm{y}^{(k_r)} \in \mathcal{M}_{n,4}$, we have $\bm{y}^* \in \mathcal{M}_{n,4}$. Since $\bm{C}_0(\bm{y})$ is continuous with respect to $\bm{y}$, we obtain $\bm{C}_0(\bm{y}^{(k_r)}) \to \bm{C}_0(\bm{y}^*) = \bm{C}_0^*$. Thus, $\mathcal{C}_0(\mathbb{K})$ is closed.
\end{proof}

\begin{proposition}\label{prop:DNN_NN}
$\mathcal{DNN}_{\rm NN}(\mathbb{K}) = \mathcal{C}_0(\mathbb{K})$.
\end{proposition}

\begin{proof}
It is clear from Lemma~\ref{lem:C_dual} and Lemma~\ref{lem:C_is_closed}.
\end{proof}

\begin{remark}
In the same manner as Proposition~\ref{prop:DNN_NN}, we can characterize the dual cone of $\mathcal{K}_{{\rm NN},r}^{n,m}(\mathbb{K})$ in the case of general $m$ and $r$, which we write as $\mathcal{C}_{r}^{n,m}(\mathbb{K})$. Specifically, when $\mathbb{K} = \mathbb{R}_+^n$ and $m=2$, $\mathcal{C}_{r}^{n,2}(\mathbb{R}_+^n)$ reduces to the explicit expression of the dual cone of $\mathcal{K}_{{\rm P},r}^n$ given by \cite[Sect.~2.3]{GL2007}.
\end{remark}

So far, we have given an explicit expression of the ZVP and NN GDNN cones. In what follows, we discuss the inclusion relationship between the three GDNN cones. To begin with, we show that $\mathcal{DNN}_{\rm NN}(\mathbb{K})$ is strictly included in $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$.
\begin{proposition}\label{prop:DNNd_inclusion_ZVP_NN}
$\mathcal{K}_{{\rm ZVP},0}(\mathbb{K}) \subseteq \mathcal{K}_{{\rm NN},0}(\mathbb{K})$ holds. Moreover, the inclusion holds strictly in general.
\end{proposition}

\begin{proof}
Let
\begin{equation}
\bm{A} = \bm{P} + \sum_{h = 2}^Nt_h\bm{J}_{h} + \bm{N} \in \mathcal{K}_{{\rm ZVP},0}(\mathbb{K}), \label{eq:mat_in_K_ZVP_SOC}
\end{equation}
where $\bm{P}\in \mathbb{S}_+^n$, $t_2,\dots,t_N\ge 0$, and $\bm{N}\in \mathcal{N}_{\ge 0}$. Firstly, let $\bm{U}$ be an $n\times n$ matrix such that $\bm{P} = \bm{U}^\top\bm{U}$; then, $(\bm{x}\circ\bm{x})^\top \bm{P}(\bm{x}\circ\bm{x}) = \|\bm{U}(\bm{x}\circ\bm{x})\|^2 \in \Sigma_{n,4}$. Secondly, for each $h = 2,\dots,N$,
\begin{equation*}
(\bm{x}\circ\bm{x})^\top(t_h\bm{J}_h)(\bm{x}\circ\bm{x}) =  t_h\left(x_{h1}^2 - \sum_{I\in\mathcal{I}_h^-}x_I^2\right)^2 \in \Sigma_{n,4}.
\end{equation*}
Finally,
\begin{align*}
(\bm{x}\circ\bm{x})^\top \bm{N}(\bm{x}\circ\bm{x}) &= \sum_{I,J\in\mathcal{I}_1}N_{IJ}(x_Ix_J)^2 + 2\sum_{h=2}^N\sum_{I\in\mathcal{I}_1}\sum_{J\in\mathcal{I}_h}N_{Ih1}(x_Ix_J)^2\\
&\quad+ \sum_{g,h=2}^N\sum_{I\in\mathcal{I}_g}\sum_{J\in\mathcal{I}_h}N_{g1h1}(x_Ix_J)^2 \in \Sigma_{n,4}.
\end{align*}
Therefore, $(\bm{x}\circ\bm{x})^\top \bm{A}(\bm{x}\circ\bm{x}) \in \Sigma_{n,4}$, which means that $\bm{A}\in \mathcal{K}_{{\rm NN},0}(\mathbb{K})$.

The following example shows that the inclusion holds strictly. Suppose that $n_1\ge 1$ and $n_2\ge 2$. Let $\bm{A}\in\mathbb{S}^n$ be the matrix with the $(11,21)$th, $(11,22)$th, $(21,11)$th, and $(22,11)$th elements 1 and the others 0. Then, since
\begin{align*}
(\bm{x}\circ\bm{x})^\top \bm{A}(\bm{x}\circ\bm{x}) &= 2x_{11}^2\sum_{I\in\mathcal{I}_2}x_I^2 + 4x_{11}^2x_{21}x_{22}\\
&= 2x_{11}^2\left\{(x_{21}+x_{22})^2 + \sum_{I\in\mathcal{I}_2^-\setminus\{22\}}x_I^2\right\} \in \Sigma_{n,4},
\end{align*}
it follows that $\bm{A}\in \mathcal{K}_{{\rm NN},0}(\mathbb{K})$.

On the other hand, we assume that $\bm{A}\in\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$ and express $\bm{A}$ as Eq.~\eqref{eq:mat_in_K_ZVP_SOC}. Then, $P_{11,11} = 0$, since $0 = A_{11,11} = P_{11,11} + N_{11,11} \ge 0$. Combining $P_{11,11} = 0$ with $\bm{P}\in\mathbb{S}_+^n$ yields $P_{11,22} = 0$. Therefore, $A_{11,22}$ must be 0, which contradicts the definition of $\bm{A}$. Hence, $\bm{A} \not\in \mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$.
\end{proof}

\begin{corollary}\label{cor:DNN_inclusion_NN_ZVP}
$\mathcal{DNN}_{\rm NN}(\mathbb{K}) \subseteq \mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ holds. Moreover, the inclusion holds strictly in general.
\end{corollary}

\begin{proof}
Note that $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$ and $\mathcal{K}_{{\rm NN},0}(\mathbb{K})$ are both closed convex cones (see Remark~\ref{rem:KZVP_closed} and Corollary~\ref{cor:inner_approx_COP}, respectively). Therefore, taking the dual in Proposition~\ref{prop:DNNd_inclusion_ZVP_NN} gives the desired result.
\end{proof}

The following examples show that there is no inclusion relationship between $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ and $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ in general.

\begin{example}
[a matrix that is in $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ but is not in $\mathcal{DNN}_{\rm BD}(\mathbb{K})$]\label{ex:inZVP_notinBD} Suppose that $n_1 \ge 1$ and $n_2\ge 2$. Let
\begin{equation*}
\bm{A} = \left(
\begin{array}{ccccc}
\Diag(n_2-1,\bm{O}_{n_1-1}) & \vline &\begin{matrix}0 & \bm{1}_{n_2-1}^\top\\\bm{0}_{n_1-1} & \bm{O}_{(n_1-1)\times(n_2-1)} \end{matrix}&\vline & \bm{O}\\
\hline
\begin{matrix}0 & \bm{0}_{n_1-1}^\top\\\bm{1}_{n_2-1} & \bm{O}_{(n_2-1)\times(n_1-1)}\end{matrix} &\vline &\Diag(n_2-1,\bm{I}_{n_2-1}) &\vline &\bm{O}\\
\hline
\bm{O} &\vline& \bm{O} &\vline & \bm{O}
\end{array}\right).
\end{equation*}
We use Corollary~\ref{cor:GDNN_ZVP_SOC} to show $\bm{A}\in\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$. We can easily check that
\begin{equation*}
\bm{A} \in \bigcap_{h=2}^N\{\bm{X}\in\mathbb{S}^n\mid \langle\bm{J}_h,\bm{X}\rangle\ge 0\} \cap
\{\bm{N}\in\mathbb{S}^n\mid N_{IJ}\ge 0\ (I,J\in\mathcal{I}_{\ge 0})\}.
\end{equation*}
Therefore, it is sufficient to show that $\bm{A}\in \mathbb{S}_+^n$. $\bm{A}\in \mathbb{S}_+^n$ if and only if
\begin{equation}
\Diag\left[\bm{O}_{\sum_{h=1}^Nn_h-n_2-1},n_2-1,\begin{pmatrix}
n_2-1 & \bm{1}_{n_2-1}^\top\\
\bm{1}_{n_2-1} & \bm{I}_{n_2-1}
\end{pmatrix}\right] \in \mathbb{S}_+^n, \label{eq:ex_inZVP_notinNN_equiv}
\end{equation}
which is obtained by rearranging some rows and columns of $\bm{A}$. Moreover, Eq.~\eqref{eq:ex_inZVP_notinNN_equiv} is equivalent to
\begin{equation*}
\begin{pmatrix}
n_2-1&\bm{1}_{n_2-1}^\top\\
\bm{1}_{n_2-1} & \bm{I}_{n_2-1}
\end{pmatrix} \in \mathbb{S}_+^{n_2},
\end{equation*}
which is true because $(n_2 - 1) - \bm{1}_{n_2-1}^\top \bm{I}_{n_2-1}\bm{1}_{n_2-1} = 0$. (Here, we use the Schur complement lemma~\cite[Lemma~4.2.1]{BN2001}.) Therefore, $\bm{A}\in \mathcal{DNN}_{\rm ZVP}(\mathbb{K})$.

On the other hand, when we let
\begin{equation*}
\bm{s} = \left(\bm{0}_{n_1},\frac{1}{2},-\frac{\bm{1}_{n_2-1}}{2\sqrt{n_2-1}},\bm{0}\right)\in\mathfrak{J}(\mathbb{K}),
\end{equation*}
$\bm{A}\bm{s} \not\in \mathbb{K}$, since $(\bm{A}\bm{s})_1 = -\sqrt{n_2-1}/2 < 0$. Thus, $\bm{A}\not\in \mathcal{DNN}_{\rm BD}(\mathbb{K})$ by Lemma~\ref{lem:GNNcone_symmetric}.\
\end{example}

\begin{example}
[a matrix that is in $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ but is not in $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$]\label{ex:inBD_notinZVP} Suppose that $n_2\ge 3$. Let
\begin{equation*}
\bm{A} = \Diag\left(\bm{O}_{n_1},1,\frac{\bm{I}_{n_2-1}}{\sqrt{n_2-1}},\bm{O}\right).
\end{equation*}
Then, $\bm{A}\in \mathcal{DNN}_{\rm BD}(\mathbb{K})$. Indeed, let $\bm{s}\in \mathfrak{J}(\mathbb{K})$. If $\bm{s} = (\bm{0}_{n_1},1/2,\bm{v}/2,\bm{0})$ for some $\bm{v}\in S^{n_2-2}$, then
\begin{equation*}
\bm{A}\bm{s} = \left(\bm{0}_{n_1}, \frac{1}{2}, \frac{\bm{v}}{2\sqrt{n_2-1}},\bm{0}\right).
\end{equation*}
Since
\begin{equation*}
\left(\frac{1}{2}\right)^2 - \left\|\frac{\bm{v}}{2\sqrt{n_2-1}}\right\|^2 = \frac{1}{4}\left(1-\frac{1}{n_2-1}\right) \ge 0,
\end{equation*}
$(\frac{1}{2}, \frac{\bm{v}}{2\sqrt{n_2-1}}) \in \mathbb{L}^{n_2}$, and therefore we get $\bm{A}\bm{s}\in\mathbb{K}$. Otherwise, $\bm{A}\bm{s} = \bm{0}\in \mathbb{K}$.

On the other hand, $\bm{A}\not\in \mathcal{DNN}_{\rm ZVP}(\mathbb{K})$, since $\langle\bm{J}_2,\bm{A}\rangle = 1 -\sqrt{n_2-1} < 0$.
\end{example}

As a special case, we consider $n_h = 0\ (h = 1,3\dots,N)$, i.e., $\mathbb{K} = \mathbb{L}^n$. It is well known that $\mathcal{CP}(\mathbb{L}^n) = \mathbb{S}_+^n \cap \{\bm{X}\in\mathbb{S}^n\mid \langle \Diag(1,-\bm{I}_{n-1}),\bm{X}\rangle\ge 0\}$ and so $\mathcal{CP}(\mathbb{L}^n)$ itself is tractable~\cite[Theorem~1]{SZ2003}. Surprisingly, from Corollary~\ref{cor:GDNN_ZVP_SOC} and \ref{cor:DNN_inclusion_NN_ZVP}, we see that $\mathcal{DNN}_{\rm ZVP}(\mathbb{L}^n)$ and $\mathcal{DNN}_{\rm NN}(\mathbb{L}^n)$ agree with $\mathcal{CP}(\mathbb{L}^n)$. However, Example~\ref{ex:inBD_notinZVP} implies that $\mathcal{DNN}_{\rm BD}(\mathbb{L}^n)$ includes $\mathcal{CP}(\mathbb{L}^n)$ strictly if $n\ge 3$. In the case of $n \le 2$, since $\mathbb{L}^n$ is a solid polyhedral cone, by using Eq.~\eqref{eq:GNNcone_polyhedral}, we have $\mathcal{DNN}_{\rm BD}(\mathbb{L}^n) = \mathcal{CP}(\mathbb{L}^n)$. To summarize, we obtain the following result.

\begin{proposition}
$\mathcal{CP}(\mathbb{L}^n) = \mathcal{DNN}_{\rm NN}(\mathbb{L}^n) = \mathcal{DNN}_{\rm ZVP}(\mathbb{L}^n) \subseteq \mathcal{DNN}_{\rm BD}(\mathbb{L}^n)$ holds. Furthermore, the above inclusion of ``$\subseteq$'' holds strictly if and only if $n\ge 3$.
\end{proposition}

We have mentioned that $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ is tractable if $\mathbb{K}$ is a direct product of a nonnegative orthant and second-order cones, as claimed for the first time by Burer and Dong~\cite{BD2012}. However, they did not prove it, and as far as we know, it has never been officially proven. In addition, the proof is necessary to understand the numerical experiments conducted in Sect.~\ref{sec:experiment}. Therefore, in what follows, we explain why $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ is tractable in this case.

The claim is based on the fact that for a bounded full-dimensional convex set $P$, if the weak separation problem for $P$ can be solved in a polynomial time, the weak optimization problem for $P$ can be solved in a polynomial time by the ellipsoid method~\cite{GLS1993,KV2018}. Let
\begin{equation}
\begin{alignedat}{3}
&\mathop{\rm minimize}\limits_{\bm{X}} && \quad \langle \bm{C},\bm{X}\rangle \\
&\subjectto && \quad \langle \bm{A}_i, \bm{X}\rangle = b_i\ (i=1,\dots,m),\\
&&&\quad \bm{X}\in \mathcal{CP}(\mathbb{K})
\end{alignedat}\label{prob:GCPP}
\end{equation}
be the standard form of GCPP, where $\bm{C}$, $\bm{A}_1,\dots,\bm{A}_m\in\mathbb{S}^n$, and $b_1,\dots,b_m\in\mathbb{R}$. Then, BD GDNNP, the relaxation of problem~\eqref{prob:GCPP} with the BD GDNN cone, is represented as
\begin{equation}
\begin{alignedat}{3}
&\mathop{\rm minimize}\limits_{\bm{X}} && \quad \langle \bm{C},\bm{X}\rangle \\
&\subjectto && \quad \langle \bm{A}_i, \bm{X}\rangle = b_i\ (i=1,\dots,m),\\
&&&\quad \bm{X}\in\mathcal{DNN}_{\rm BD}(\mathbb{K}) = \mathbb{S}_+^n \cap \mathcal{N}(\mathbb{K}).
\end{alignedat}\label{prob:GDNN_BD}
\end{equation}
We roughly explain how to solve the separation problem for the feasible set of problem~\eqref{prob:GDNN_BD}.

Let $\overbar{\bm{X}}\in\mathbb{S}^n$ be given. We can easily check whether $\overbar{\bm{X}}$ satisfies the linear equation constraints and the semidefinite constraint in problem~\eqref{prob:GDNN_BD} and then construct a separating hyperplane if $\overbar{\bm{X}}$ violates any of them. Therefore, we only consider the separation problem for $\mathcal{N}(\mathbb{K})$.

Recall that $\mathcal{N}(\mathbb{K}) = \{\bm{X}\in\mathbb{S}^n\mid \bm{X}\bm{s}\in\mathbb{K} \text{ for all $\bm{s}\in\mathfrak{J}(\mathbb{K})$}\}$ when $\mathbb{K}$ is a symmetric cone in $\mathbb{R}^n$ (see Lemma~\ref{lem:GNNcone_symmetric}).
For each $\bm{s}\in \mathfrak{J}(\mathbb{K})$, since $\overbar{\bm{X}}\bm{s} \in \mathbb{K}$ is equivalent to $\lambda_{\rm min}(\overbar{\bm{X}}\bm{s}) \ge 0$, $\overbar{\bm{X}}\in \mathcal{N}(\mathbb{K})$ is equivalent to $\min_{\bm{s}\in\mathfrak{J}(\mathbb{K})}\lambda_{\rm min}(\overbar{\bm{X}}\bm{s})\ge 0$.
Moreover, from Lemma~\ref{lem:direct_sum}, $\min_{\bm{s}\in\mathfrak{J}(\mathbb{K})}\lambda_{\rm min}(\overbar{\bm{X}}\bm{s}) \ge 0$ if and only if the minimum of the following four values is greater than or equal to 0:
\begin{subequations}
\begin{align}
&\min_{\bm{s}_1\in\mathfrak{J}(\mathbb{R}_+^{n_1})}\lambda_{\rm min}^{\rm nno}(\overbar{\bm{X}}_{\mathcal{I}_1\mathcal{I}_1}\bm{s}_1),\label{eq:neg_neg}\\
&\min_{2\le h\le N}\min_{\bm{s}_h\in\mathfrak{J}(\mathbb{L}^{n_h})}\lambda_{\rm min}^{\rm nno}(\overbar{\bm{X}}_{\mathcal{I}_1\mathcal{I}_h}\bm{s}_h), \label{eq:neg_so}\\
&\min_{2\le h\le N}\min_{\bm{s}_1\in\mathfrak{J}(\mathbb{R}_+^{n_1})}\lambda_{\rm min}^{\rm soc}(\overbar{\bm{X}}_{\mathcal{I}_h\mathcal{I}_1}\bm{s}_1),\label{eq:so_neg}\\
&\min_{2\le g,h\le N}\min_{\bm{s}_h\in\mathfrak{J}(\mathbb{L}^{n_h})}\lambda_{\rm min}^{\rm soc}(\overbar{\bm{X}}_{\mathcal{I}_g\mathcal{I}_h}\bm{s}_h).\label{eq:so_so}
\end{align}
\end{subequations}

We can calculate \eqref{eq:neg_neg} in a polynomial time since $\eqref{eq:neg_neg}$ is the minimum of $\overbar{X}_{IJ}$ over $I$, $J\in\mathcal{I}_1$. If there exists $I_0$ and $J_0$ such that $\overbar{X}_{I_0J_0}<0$, then $\min_{\bm{s}\in\mathfrak{J}(\mathbb{K})}\lambda_{\rm min}(\overbar{\bm{X}}\bm{s}) < 0$ and the matrix $\bm{H}$ with all elements 0 except for $(I_0,J_0)$th and $(J_0,I_0)$th elements $-1$ gives a hyperplane separating $\overbar{\bm{X}}$ from $\mathcal{N}(\mathbb{K})$. Indeed, $\langle \overbar{\bm{X}},\bm{H}\rangle = -2\overbar{X}_{I_0J_0} > 0$, while $\langle \bm{X},\bm{H}\rangle \le 0$ for all $\bm{X} \in \mathcal{N}(\mathbb{K})$ since $X_{I_0J_0} \ge 0$.

We can also calculate \eqref{eq:neg_so} in a polynomial time:
\begin{align}
\eqref{eq:neg_so} &= \frac{1}{2}\min_{2\le h\le N}\min_{\substack{I\in\mathcal{I}_1\\ \bm{v}\in S^{n_h-2}}}
\left(\overbar{X}_{Ih1} + \overbar{\bm{X}}_{I\mathcal{I}_h^-}\bm{v}\right) \nonumber\\
&= \frac{1}{2}\min_{2\le h\le N}\min_{I\in\mathcal{I}_1}(\overbar{X}_{Ih1} - \|\overbar{\bm{X}}_{I\mathcal{I}_h^-}\|),\label{eq:neg_so_cs}
\end{align}
where we use the Cauchy-Schwarz inequality to derive Eq.~\eqref{eq:neg_so_cs}. Let $\bm{v}_{Ih}^*$ be a vector that attains Eq.~\eqref{eq:neg_so_cs} for each $I\in\mathcal{I}_1$ and $h = 2,\dots,N$. If there exist $I_0$ and $h_0$ such that $\overbar{X}_{I_0h_01} - \|\overbar{\bm{X}}_{I_0\mathcal{I}_{h_0}^-}\| < 0$, the matrix $\bm{H}_{I_0h_0}$ with all elements 0 except for $(I_0,\mathcal{I}_{h_0})$th and $(\mathcal{I}_{h_0},I_0)$th elements $(-1,-\bm{v}_{I_0h_0}^*)$, gives a hyperplane separating $\overbar{\bm{X}}$ from $\mathcal{N}(\mathbb{K})$.

We can also calculate \eqref{eq:so_neg} in a polynomial time since \eqref{eq:so_neg} is equal to the minimum of $\overbar{X}_{h1J}-\|\overbar{\bm{X}}_{\mathcal{I}_h^-J}\|$ over $J\in\mathcal{I}_1$ and $h = 2,\dots,m$. If there exist $J_0$ and $h_0$ such that $\overbar{X}_{h_01J_0}-\|\overbar{\bm{X}}_{\mathcal{I}_{h_0}^-J_0}\| < 0$, the matrix $\bm{H}_{J_0h_0}$ defined in the same way as $\bm{H}_{I_0h_0}$ also gives a hyperplane separating $\overbar{\bm{X}}$ from $\mathcal{N}(\mathbb{K})$.

We can also check whether \eqref{eq:so_so} is greater than or equal to 0 in a polynomial time. \footnote{This does not mean that we can calculate \eqref{eq:so_so} itself in a polynomial time.} Indeed, \eqref{eq:so_so} is greater than or equal to 0 if and only if $\overbar{\bm{X}}_{g1\mathcal{I}_h}\bm{s}_h \ge 0$ and $(\overbar{\bm{X}}_{g1\mathcal{I}_h}\bm{s}_h)^2 - \|\overbar{\bm{X}}_{\mathcal{I}_g^-\mathcal{I}_h}\bm{s}_h\|^2 \ge 0$ for all $2\le g,h\le N$ and $\bm{s}_h \in \mathfrak{J}(\mathbb{L}^{n_h})$. Whether $\overbar{\bm{X}}_{g1\mathcal{I}_h}\bm{s}_h \ge 0$ for all $2\le g,h\le N$ and $\bm{s}_h \in \mathfrak{J}(\mathbb{L}^{n_h})$ can be checked through the following equations:
\begin{align}
\min_{2\le g,h\le N}\min_{\bm{s}_h\in \mathfrak{J}(\mathbb{L}^{n_h})}\overbar{\bm{X}}_{g1\mathcal{I}_h}\bm{s}_h &= \frac{1}{2}\min_{2\le g,h\le N}\min_{\bm{v}\in S^{n_h-2}}\left(\overbar{X}_{g1h1} + \overbar{\bm{X}}_{g1\mathcal{I}_h^-}\bm{v}\right) \nonumber \\
&= \frac{1}{2}\min_{2\le g,h\le N}(\overbar{X}_{g1h1} - \|\overbar{\bm{X}}_{g1\mathcal{I}_h^-}\|), \label{eq:so_so_cs}
\end{align}
where we use the Cauchy-Schwarz inequality to derive the second equation. Let $\bm{v}_{gh}^*$ be a vector that attains \eqref{eq:so_so_cs} for each $2\le g,h\le N$. Assume that there exist $g_0$ and $h_0$ such that $\overbar{X}_{g_01h_01} - \|\overbar{\bm{X}}_{g_01\mathcal{I}_{h_0}^-}\| < 0$. Let $\bm{H}$ be the sum of the matrix with all elements 0 except for the $(g_0,\mathcal{I}_{h_0})$th element $(-1,-\bm{v}_{g_0h_0}^*)$ and its transposed matrix. Then, $\bm{H}$ gives a hyperplane separating $\overbar{\bm{X}}$ from $\mathcal{N}(\mathbb{K})$. In what follows, we assume that $\overbar{\bm{X}}_{g1\mathcal{I}_h}\bm{s}_h \ge 0$ for all $2\le g,h\le N$ and $\bm{s}_h \in \mathfrak{J}(\mathbb{L}^{n_h})$. For notational convenience, let
\begin{equation*}
\overbar{\bm{X}}_{\mathcal{I}_g\mathcal{I}_h} = \begin{pmatrix}
\overbar{X}_{gh}^{11} & (\overbar{\bm{X}}_{gh}^{12})^\top\\
\overbar{\bm{X}}_{gh}^{21} &  \overbar{\bm{X}}_{gh}^{22}
\end{pmatrix},
\end{equation*}
where $\overbar{X}_{gh}^{11}\in\mathbb{R}$, $\overbar{\bm{X}}_{gh}^{12}\in\mathbb{R}^{n_h-1}$, $\overbar{\bm{X}}_{gh}^{21}\in\mathbb{R}^{n_g-1}$, and $\overbar{\bm{X}}_{gh}^{22}\in\mathbb{R}^{(n_g-1)\times(n_h-1)}$. Then, since for $\bm{s}_h = (1/2,\bm{v}/2) \in \mathfrak{J}(\mathbb{L}^{n_h})$ with $\bm{v}\in S^{n_h-2}$,
\begin{align*}
&(\overbar{\bm{X}}_{g1\mathcal{I}_h}\bm{s}_h)^2 - \|\overbar{\bm{X}}_{\mathcal{I}_g^-\mathcal{I}_h}\bm{s}_h\|^2 \nonumber\\
&\quad= \frac{1}{4}[\bm{v}^\top\{\overbar{\bm{X}}_{gh}^{12}(\overbar{\bm{X}}_{gh}^{12})^\top-(\overbar{\bm{X}}_{gh}^{22})^\top\overbar{\bm{X}}_{gh}^{22}\}\bm{v} \nonumber\\
&\qquad+ 2(\overbar{X}_{gh}^{11}\overbar{\bm{X}}_{gh}^{12}-(\overbar{\bm{X}}_{gh}^{22})^\top\overbar{\bm{X}}_{gh}^{21})^\top\bm{v} + (\overbar{X}_{gh}^{11})^2 - \|\overbar{\bm{X}}_{gh}^{21}\|^2] \coloneqq f_{gh}(\bm{v}).
\end{align*}
Therefore, $(\overbar{\bm{X}}_{g1\mathcal{I}_h}\bm{s}_h)^2 - \|\overbar{\bm{X}}_{\mathcal{I}_g^-\mathcal{I}_h}\bm{s}_h\|^2 \ge 0$ for all $2\le g,h\le N$ and $\bm{s}_h\in\mathfrak{J}(\mathbb{L}^{n_h})$ if and only if the minimum of the optimal value of the optimization problem
\begin{equation}
\min_{\bm{v}\in S^{n_h-2}}f_{gh}(\bm{v}) \label{prob:TRS}
\end{equation}
over $2\le g,h\le N$ is greater than or equal to 0. As problem~\eqref{prob:TRS} is a minimization problem of a quadratic function over the unit sphere, it is known as a trust region subproblem (TRS), which can be solved in a polynomial time~\cite{RW1997}. Suppose that the optimal value of problem~\eqref{prob:TRS} is less than 0 for some $g_0$ and $h_0$, and let $\bm{v}_{g_0h_0}^*$ be an optimal solution of the TRS. Then, since $\overbar{X}_{g_0h_0}^{11} + (\overbar{\bm{X}}_{g_0h_0}^{12})^\top\bm{v}_{g_0h_0}^* \ge 0$, it follows that $\overbar{X}_{g_0h_0}^{11} + (\overbar{\bm{X}}_{g_0h_0}^{12})^\top\bm{v}_{g_0h_0}^* - \|\overbar{\bm{X}}_{g_0h_0}^{21} + \overbar{\bm{X}}_{g_0h_0}^{22}\bm{v}_{g_0h_0}^*\| < 0$. Let
\begin{equation*}
\bm{c} \coloneqq \begin{cases}
\frac{\overbar{\bm{X}}_{g_0h_0}^{21} + \overbar{\bm{X}}_{g_0h_0}^{22}\bm{v}_{g_0h_0}^*}{\|\overbar{\bm{X}}_{g_0h_0}^{21} + \overbar{\bm{X}}_{g_0h_0}^{22}\bm{v}_{g_0h_0}^*\|} & \text{(if $\overbar{\bm{X}}_{g_0h_0}^{21} + \overbar{\bm{X}}_{g_0h_0}^{22}\bm{v}_{g_0h_0}^*\neq \bm{0}$)},\\
\text{an arbitrary element of $S^{n_{g_0}-2}$} & \text{(if $\overbar{\bm{X}}_{g_0h_0}^{21} + \overbar{\bm{X}}_{g_0h_0}^{22}\bm{v}_{g_0h_0}^* = \bm{0}$)}.
\end{cases}
\end{equation*}
Then, $\overbar{X}_{g_0h_0}^{11} + (\overbar{\bm{X}}_{g_0h_0}^{12})^\top\bm{v}_{g_0h_0}^* - \|\overbar{\bm{X}}_{g_0h_0}^{21} + \overbar{\bm{X}}_{g_0h_0}^{22}\bm{v}_{g_0h_0}^*\| = \overbar{X}_{g_0h_0}^{11} + (\overbar{\bm{X}}_{g_0h_0}^{12})^\top\bm{v}_{g_0h_0}^* -(\overbar{\bm{X}}_{g_0h_0}^{21})^\top\bm{c} -\bm{c}^\top\overbar{\bm{X}}_{g_0h_0}^{22}\bm{v}_{g_0h_0}^*$. Therefore, let $\bm{H}$ be the sum of the matrix with all elements 0 except for the $(\mathcal{I}_{g_0},\mathcal{I}_{h_0})$th element
\begin{equation*}
\begin{pmatrix}
-1 & (-\bm{v}_{g_0h_0}^*)^\top\\
\bm{c} & \bm{c}(\bm{v}_{g_0h_0}^*)^\top
\end{pmatrix}
\end{equation*}
and its transposed matrix. Then, $\bm{H}$ gives a hyperplane separating $\overbar{\bm{X}}$ from $\mathcal{N}(\mathbb{K})$.

Finally, we discuss the inclusion relationship between $\mathcal{DNN}_{\rm NN}(\mathbb{K})$ and $\mathcal{DNN}_{\rm BD}(\mathbb{K})$. Since $\mathcal{DNN}_{\rm NN}(\mathbb{K}) \subseteq \mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ (Corollary~\ref{cor:DNN_inclusion_NN_ZVP}), the matrix given in Example~\ref{ex:inBD_notinZVP} is also a matrix that is in $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ but not in $\mathcal{DNN}_{\rm NN}(\mathbb{K})$. Therefore, we are interested in whether there exists a matrix that is in $\mathcal{DNN}_{\rm NN}(\mathbb{K})$ but not in $\mathcal{DNN}_{\rm BD}(\mathbb{K})$. If not, $\mathcal{DNN}_{\rm NN}(\mathbb{K})$ is included in $\mathcal{DNN}_{\rm BD}(\mathbb{K})$. Although we were not able to determine this theoretically, the results of our numerical experiment imply that $\mathcal{DNN}_{\rm NN}(\mathbb{K})$ is included in $\mathcal{DNN}_{\rm BD}(\mathbb{K})$. For details, see Sect.~\ref{subsec:NN_BD_GDNNcone}.

\subsection{When $\mathbb{K}$ is a direct product of a nonnegative orthant and semidefinite cones}
\label{subsec:sdc}
In this subsection, we consider the case where $\mathbb{K}$ is a direct product of a nonnegative orthant and semidefinite cones, i.e., $\mathbb{K} = \mathbb{R}_+^{n_1}\times \prod_{h=2}^N\svec(\mathbb{S}_+^{n_h})$, and let $n \coloneqq n_1 + \sum_{h=2}^N\tilde{n}_h$. For convenience, we reindex $(1,\dots,n)$ as
\begin{equation*}
(11,\dots,1n,211,212,222,\dots,21n_2,\dots,2n_2n_2,\dots,N11,\dots,Nn_Nn_N),
\end{equation*}
i.e., $1i \coloneqq i$ for $i = 1,\dots,n$, and $hij \coloneqq n_1+\sum_{k=2}^{h-1}\tilde{n}_k + j(j-1)/2 + i$ for $h = 2,\dots,N$ and $1\le i\le j\le N$. For $h = 2,\dots,N$ and $1\le j < i\le n_h$, let $hij \coloneqq hji$. Moreover, we set $\widetilde{\mathcal{I}}_h \coloneqq \{h11,h12,\dots,hn_hn_h\}\ (h = 2,\dots,N)$ and
\begin{equation*}
\widetilde{\mathcal{I}}_{\ge 0} \coloneqq \{11,\dots,1n_1,211,222,\dots,2n_2n_2,\dots,N11,\dots,Nn_Nn_N\}.
\end{equation*}

As mentioned in Sect.~\ref{subsec:EJA}, the semidefinite cone $\mathbb{S}_+^m$ is a symmetric cone. In addition, $\mathbb{S}_+^m$ is also semialgebraic since
\begin{equation*}
\mathbb{S}_+^m= \{\bm{X}\in\mathbb{S}^m\mid \det \bm{X}_{\mathcal{II}} \ge 0 \text{ for all $\mathcal{I} \subseteq \{1,\dots,m\}$}\}.
\end{equation*}
Therefore, we can define all three GDNN cones properly in this case.

However, it is difficult to see whether $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ is tractable in the same manner as Sect.~\ref{subsec:soc}. As in Sect.~\ref{subsec:soc}, the separation problem for $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ reduces to the problem of whether $\min_{\bm{s}\in\mathfrak{J}(\mathbb{K})}\lambda_{\rm min}(\bm{X}\bm{s})$ is greater than or equal to $0$, so
\begin{equation*}
\min_{2\le g,h\le N}\min_{\bm{s}_h\in\mathfrak{J}(\svec(\mathbb{S}_+^{n_h}))}\lambda_{\rm min}^{\rm sdc}(\bm{X}_{\widetilde{\mathcal{I}}_g\widetilde{\mathcal{I}}_h}\bm{s}_h)
\end{equation*}
need to be computed. Using the fact mentioned in Example~\ref{ex:sdc}, we see that
\begin{align*}
&\min_{2\le g,h\le N}\min_{\bm{s}_h\in\mathfrak{J}(\svec(\mathbb{S}_+^{n_h}))}\lambda_{\rm min}^{\rm sdc}(\bm{X}_{\widetilde{\mathcal{I}}_g\widetilde{\mathcal{I}}_h}\bm{s}_h)\\
&\quad= \min_{2\le g,h\le N}\min_{\bm{w}\in S^{n_h-1}}\lambda_{\rm min}^{\rm sdc}(\bm{X}_{\widetilde{\mathcal{I}}_g\widetilde{\mathcal{I}}_h}\svec(\bm{w}\bm{w}^\top))\\
&\quad= \min_{2\le g,h\le N}\min_{(\bm{v},\bm{w})\in S^{n_g-1}\times S^{n_h-1}}\bm{v}^\top \smat(\bm{X}_{\widetilde{\mathcal{I}}_g\widetilde{\mathcal{I}}_h}\svec(\bm{w}\bm{w}^\top))\bm{v},
\end{align*}
and calculating the minimum eigenvalue of a matrix is equivalent to minimizing the Rayleigh quotient to derive the second equation. This is an optimization problem to minimize the quartic function over the direct product of two spheres, which seems to be much more difficult to solve than a TRS.

On the other hand, the NN and ZVP GDNN cones have superiority over the BD one in that they are always tractable. In what follows, we discuss the inclusion relationship between the two and show that the NN GDNN cone is strictly included in the ZVP one, as in the case of the second-order cone.

Firstly, we give an explicit expression of $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$.
\begin{proposition}\label{prop:K_ZVP_SDC}
Let $\bm{J}_h^{ij}$ be the $n\times n$ matrix with $(hii,hjj)$th and $(hjj,hii)$th elements $1$, $(hij,hij)$th element $-1$, and other elements $0$. Then,
\begin{multline}
\mathcal{K}_{{\rm ZVP},0}(\mathbb{K}) = \mathbb{S}_+^n + \sum_{h=2}^N\sum_{1\le i< j\le n_h}\mathbb{R}_+\bm{J}_h^{ij}  \\+ \left\{\bm{N}\in\mathbb{S}^n\relmiddle|
N_{IJ} \begin{cases}
\ge 0& (I,J\in\widetilde{\mathcal{I}}_{\ge 0})\\
= 0& (otherwise)
\end{cases}
\right\}. \label{eq:K_ZVP_SDC}
\end{multline}
\end{proposition}
For simplicity, we write the last set in the right-hand side of Eq.~\eqref{eq:K_ZVP_SDC} as $\widetilde{\mathcal{N}}_{\ge 0}$. Because Proposition~\ref{prop:K_ZVP_SDC} can be proven in the same way as Proposition~\ref{prop:K_ZVP_SOC}, we omit the proof. We can also show that $\mathcal{K}_{{\rm ZVP},0}(\mathbb{K})$ is closed using Lemma~\ref{lem:minlovski_closed}. Moreover, taking the dual in Proposition~\ref{prop:K_ZVP_SDC}, we can obtain an explicit expression of $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$.

\begin{proposition}\label{prop:K_inclusion_ZVP_NN_SDC}
$\mathcal{K}_{{\rm ZVP},0}(\mathbb{K}) \subseteq \mathcal{K}_{{\rm NN},0}(\mathbb{K})$ holds. Moreover, the inclusion holds strictly in general.
\end{proposition}
\begin{proof}
Note that
\begin{equation*}
(\bm{x}\circ\bm{x})_I = \begin{dcases}
x_I^2 & (I = 11,\dots,1n_1),\\
x_{hii}^2 + \frac{1}{2}\sum_{k:k\neq i}x_{hki}^2 & (I = hii,\ h = 2,\dots,N,\ i = 1,\dots,n_h),\\
\begin{split}
&x_{hii}x_{hij} + x_{hij}x_{hjj} \\
&\qquad+ \frac{1}{\sqrt{2}}\sum_{k:k\neq i,j}x_{hik}x_{hjk}
\end{split} & (I = hij,\ h = 2,\dots,N,\ 1\le i < j\le n_h).
\end{dcases}
\end{equation*}
Let
\begin{equation}
\bm{A} = \bm{P} + \sum_{h=2}^N\sum_{1\le i< j\le n_h}t_h^{ij}\bm{J}_h^{ij} + \bm{N}, \label{eq:mat_in_K_ZVP_SDC}
\end{equation}
where $\bm{P}\in\mathbb{S}_+^n$, $t_h^{ij}\ge 0$, and $\bm{N}\in\widetilde{\mathcal{N}}_{\ge 0}$. Firstly, as the proof of Proposition~\ref{prop:K_ZVP_SOC}, $(\bm{x}\circ\bm{x})^\top \bm{P}(\bm{x}\circ \bm{x})\in\Sigma_{n,4}$. Secondly, for $h = 2,\dots,N$ and $1\le i < j\le n_h$, since
\begin{align*}
&2(\bm{x}\circ\bm{x})^\top\bm{J}_h^{ij}(\bm{x}\circ\bm{x})\\
&\quad= 4\left(x_{hii}^2 + \frac{1}{2}\sum_{k:k\neq i}x_{hki}^2\right)\left(x_{hjj}^2  + \frac{1}{2}\sum_{k:k\neq j}x_{hkj}^2\right)\\
&\quad\qquad- 2\left(x_{hii}x_{hij} + x_{hij}x_{hjj} + \frac{1}{\sqrt{2}}\sum_{k:k\neq i,j}x_{hik}x_{hjk}\right)^2\\
&\quad= (x_{hij}^2-2x_{hii}x_{hjj})^2 + \sum_{k:k\neq i,j}(x_{hij}x_{hik}-\sqrt{2}x_{hii}x_{hjk})^2\\
&\quad\qquad + \sum_{k:k\neq i,j}(x_{hij}x_{hjk}-\sqrt{2}x_{hjj}x_{hik})^2 + \sum_{\substack{k<l\\k,l\neq i,j}}(x_{hik}x_{hjl}-x_{hil}x_{hjk})^2,
\end{align*}
we have $(\bm{x}\circ\bm{x})^\top\bm{J}_h^{ij}(\bm{x}\circ\bm{x})\in\Sigma_{n,4}$. Finally,
\begin{align}
&(\bm{x}\circ\bm{x})^\top \bm{N}(\bm{x}\circ\bm{x}) \nonumber\\
&\quad= \sum_{i,j=1}^{n_1}N_{1i,1j}x_{1i}^2x_{1j}^2 + 2\sum_{h=2}^N\sum_{i=1}^{n_1}\sum_{j=1}^{n_h}N_{1i,hjj}x_{1i}^2\left(x_{hjj}^2 + \frac{1}{2}\sum_{k:k\neq j}x_{hkj}^2\right)\nonumber\\
&\quad\qquad + \sum_{g,h=2}^N N_{gii,hjj}\left(x_{gii}^2 + \frac{1}{2}\sum_{k:k\neq i}x_{gki}^2\right)\left(x_{hjj}^2 + \frac{1}{2}\sum_{k:k\neq j}x_{hkj}^2\right). \label{eq:N_SDC}
\end{align}
Since all variables that appear in Eq.~\eqref{eq:N_SDC} are squared and each element of $\bm{N}$ is nonnegative, we see that $(\bm{x}\circ\bm{x})^\top \bm{N}(\bm{x}\circ\bm{x}) \in\Sigma_{n,4}$. Therefore, $(\bm{x}\circ\bm{x})^\top \bm{A}(\bm{x}\circ\bm{x})\in \Sigma_{n,4}$, which means that $\bm{A}\in\mathcal{K}_{{\rm NN},0}(\mathbb{K})$.

The following example shows that the inclusion holds strictly. Suppose that $n_1\ge 1$ and $n_2\ge 2$. Let $\epsilon$ be a sufficiently small positive value, $\bm{a} = (a_{ij})_{1\le i\le j\le n_2}$ be the vector such that
\begin{equation*}
a_{ij} = \begin{cases}
1 & (i = j),\\
\epsilon & (i < j),
\end{cases}
\end{equation*}
and $\bm{A}\in\mathbb{S}^n$ be the matrix with $(11,\widetilde{\mathcal{I}}_2)$th and $(\widetilde{\mathcal{I}}_2,11)$th elements $\bm{a}$ and the others $0$. Then, after a little complicated calculation, we obtain
\begin{dmath*}
(\bm{x}\circ\bm{x})^\top \bm{A}(\bm{x}\circ\bm{x}) = x_{11}^2\left[\epsilon\sum_{i<j}\{(x_{2ii} + x_{2ij})^2 + (x_{2ij} + x_{2jj})^2\} + \frac{\epsilon}{\sqrt{2}}\sum_{i<j}\sum_{k:k\neq i,j}(x_{2ik} + x_{2jk})^2  + \left\{2-(n_2-1)\epsilon\right\}\sum_{i=1}^{n_2}x_{2ii}^2 + [2-\{2 + \sqrt{2}(n_2-2)\}\epsilon]\sum_{i<j}x_{2ij}^2\right].
\end{dmath*}
Thus, $(\bm{x}\circ\bm{x})^\top \bm{A}(\bm{x}\circ\bm{x})$ can be represented as an SOS if
\begin{equation*}
\epsilon \le \min\left\{\frac{2}{n_2-1},\frac{2}{2 + \sqrt{2}(n_2-2)}\right\}.
\end{equation*}
Such a positive $\epsilon$ certainly exists.

On the other hand, assume that $\bm{A}$ can be expressed as Eq.~\eqref{eq:mat_in_K_ZVP_SDC}. Then, $P_{11,11}$ must be 0 since $0 = P_{11,11} + N_{11,11} \ge 0$. Combining $P_{11,11} = 0$ with $\bm{P}\in\mathbb{S}_+^n$ yields $P_{11,2ij} = 0$ for all $i<j$. Therefore, for a pair $(i,j)$ with $i<j$, $A_{11,2ij}$ must be $0$. However, by the definition of $\bm{A}$, $A_{11,2ij} = \epsilon > 0$, which is a contradiction.
\end{proof}

Taking the dual in Proposition~\ref{prop:K_inclusion_ZVP_NN_SDC}, we have the following desired result.
\begin{corollary}
$\mathcal{DNN}_{\rm NN}(\mathbb{K}) \subseteq \mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ holds. Moreover, the inclusion holds strictly in general.
\end{corollary}

\section{Numerical experiments}
\label{sec:experiment}
In this section, we conduct experiments to investigate the numerical properties of the three GDNN cones in the case where $\mathbb{K}$ is a direct product of a nonnegative orthant and second-order cones. In Sect.~\ref{subsec:NN_BD_GDNNcone}, we numerically prove that the NN GDNN cone is included in the BD one. In Sect.~\ref{subsec:MISOCP}, we solve GDNNP arising from mixed 0--1 second-order cone programming to compare the three GDNN cones. All experiments discussed in this section were conducted with MATLAB (R2021b) on a computer with an Intel Core i5-8279U 2.40 GHz CPU and 16 GB of memory. When we solved optimization problems, the modeling language YALMIP~\cite{Lofberg2004} (version 20210331) and the MOSEK solver~\cite{MOSEK} (version 9.3.3) were used.

\subsection{Inclusion relationship between NN and BD GDNN cones}
\label{subsec:NN_BD_GDNNcone}
For simplicity, we assume that $\mathbb{K} = \mathbb{R}_+^{n_1}\times \mathbb{L}^{n_2}$, and in particular, we let $n_1 = 1$ and $n_2 = 3$ in this subsection. Then we can prove theoretically that for any $\overbar{\bm{X}}\in \mathcal{DNN}_{\rm NN}(\mathbb{K})$, Eqs.~\eqref{eq:neg_neg}, \eqref{eq:neg_so}, and \eqref{eq:so_neg} are nonnegative and $\overbar{\bm{X}}_{21\mathcal{I}_2}\bm{s}_2 \ge 0$ for all $\bm{s}_2 \in \mathfrak{J}(\mathbb{L}^{n_2})$. (Due to space limitations, we do not prove this here.) Therefore, $\overbar{\bm{X}}$ is guaranteed to belong to $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ if $(\overbar{\bm{X}}_{21\mathcal{I}_2}\bm{s}_2)^2 - \|\overbar{\bm{X}}_{\mathcal{I}_2^-\mathcal{I}_2}\bm{s}_2\|^2 \ge 0$ for all $\bm{s}_2 \in \mathfrak{J}(\mathbb{L}^{n_2})$, which can be checked by solving a TRS (as shown in Sect.~\ref{subsec:soc}). On the basis of this fact, we conducted the following experiment. First, we created 1000 vectors $\bm{y}_1,\dots,\bm{y}_{1000}$ in $\mathcal{M}_{4,4}$ randomly (see Appendix~\ref{apdx:vector} for the details of the vector creation). Then, we constructed 1000 matrices $\overbar{\bm{X}}_i \coloneqq \bm{C}_0(\bm{y}_i) \in \mathcal{DNN}_{\rm NN}(\mathbb{K})$ according to Definition~\ref{def:C}. Finally, for each $\overbar{\bm{X}}_i$, we solved the corresponding TRS and found the optimal value. The results are shown in Fig.~\ref{fig:optval_TRS}.

\begin{figure}[tbp]
\centering
\includegraphics[width=\linewidth]{Fig1.eps}
\caption{Optimal value (denoted by asterisk) of trust region subproblem corresponding to each $\overbar{\bm{X}}_i \in \mathcal{DNN}_{\rm NN}(\mathbb{K})$.}
\label{fig:optval_TRS}
\end{figure}

We can see in Fig.~\ref{fig:optval_TRS} that all of the optimal values are greater than 0 (most of them range from around 500 to 3000), and so all $\overbar{\bm{X}}_i \in \mathcal{DNN}_{\rm NN}(\mathbb{K})$ prepared in the experiment are also in $\mathcal{DNN}_{\rm BD}(\mathbb{K})$. Thus, we presume that the NN GDNN cone is included in the BD GDNN cone:

\begin{conjecture}\label{conj:DNN_inclusion_NN_BD}
If $\mathbb{K}$ is a direct product of a nonnegative orthant and second-order cones, $\mathcal{DNN}_{\rm NN}(\mathbb{K}) \subseteq \mathcal{DNN}_{\rm BD}(\mathbb{K})$.
\end{conjecture}

Note that Conjecture~\ref{conj:DNN_inclusion_NN_BD} is also compatible with the results in Sect.~\ref{subsec:MISOCP}. So far, we have shown the inclusion relationship between the three GDNN cones in Corollary~\ref{cor:DNN_inclusion_NN_ZVP}, Example~\ref{ex:inZVP_notinBD}, and \ref{ex:inBD_notinZVP} as well as in Conjecture~\ref{conj:DNN_inclusion_NN_BD}. We depict these results in Fig.~\ref{fig:inclusion}.

\begin{figure}[tbp]
\centering
\includegraphics[width=.3\linewidth]{Fig2.eps}
\caption{Inclusion relationship between NN, ZVP, and BD generalized doubly nonnegative cones (including Conjecture~\ref{conj:DNN_inclusion_NN_BD}).}
 \label{fig:inclusion}
\end{figure}

\subsection{Mixed 0--1 second-order cone programming}
\label{subsec:MISOCP}
We consider the (nonconvex) conic QP with binary and continuous variables:
\begin{equation}
\begin{alignedat}{3}
&\mathop{\rm minimize}\limits_{\bm{x}} && \quad \bm{x}^\top \bm{Q}\bm{x} + 2\bm{c}^\top\bm{x}\\
&\subjectto && \quad \bm{A}\bm{x} = \bm{b},\\
&&& \quad x_i\in\{0,1\}\ (i\in B),\\
&&&\quad \bm{x}\in\mathbb{K}',
\end{alignedat}\label{prob:CQP}
\end{equation}
where $\bm{Q}\in\mathbb{S}^n$, $\bm{c}\in\mathbb{R}^n$, $\bm{A}\in\mathbb{R}^{m\times n}$, $\bm{b}\in\mathbb{R}^m$, $B\subseteq \{1,\dots,n\}$, and $\mathbb{K}'$ is a closed convex cone in $\mathbb{R}^n$. Burer~\cite{Burer2012} showed that problem~\eqref{prob:CQP} is equivalent to the GCPP:
\begin{equation*}
\begin{alignedat}{3}
&\mathop{\rm minimize}\limits_{\bm{x},\bm{X}} && \quad \langle \bm{Q},\bm{X}\rangle + 2\bm{c}^\top\bm{x}\\
&\subjectto && \quad \bm{A}\bm{x} = \bm{b},\\
&&& \quad \diag(\bm{A}\bm{X}\bm{A}^\top) = (b_1^2,\dots,b_n^2),\\
&&& \quad -X_{ii} + x_i = 0\ (i\in B),\\
&&&\quad \begin{pmatrix}
1& \bm{x}^\top\\
\bm{x}& \bm{X}
\end{pmatrix} \in \mathcal{CP}(\mathbb{R}_+ \times\mathbb{K}'),
\end{alignedat}
\end{equation*}
under the ``key assumption'' that any $\bm{x}$ such that $\bm{x}\in\mathbb{K}'$ and $\bm{A}\bm{x} = \bm{b}$ satisfies $0\le x_i\le 1$ for all $i\in B$.

As a special case of problem~\eqref{prob:CQP}, we consider the mixed 0--1 second-order cone programming:
\begin{equation}
\begin{alignedat}{3}
&\mathop{\rm minimize}\limits_{\bm{x}} && \quad\bm{c}^\top\bm{x}\\
&\subjectto && \quad 0\le x_1 \le 2,\\
&&& \quad 0\le x_i \le 1\ (i=2,\dots,n),\\
&&& \quad x_i\in\{0,1\}\ (i\in B\subseteq \{2,\dots,n\}),\\
&&&\quad \bm{x}\in\mathbb{L}^n.
\end{alignedat}\label{prob:MISOCP}
\end{equation}
The second constraint of problem~\eqref{prob:MISOCP} ensures that problem~\eqref{prob:MISOCP} satisfies the key assumption when slack variables are added to it. Therefore, we can transform problem~\eqref{prob:MISOCP} into GCPP equivalently. Specifically, by introducing $2n$ nonnegative slack variables, we can convert problem~\eqref{prob:MISOCP} into the standard form~\eqref{prob:GCPP} of GCPP with $4n+|B|+1$ equality constraints and $\mathbb{K} = \mathbb{R}_+^{2n+1}\times \mathbb{L}^n$. In this subsection, we solve the problem obtained by relaxing the GCPP with each GDNN cone and compare the results.

We created instances of problem~\eqref{prob:MISOCP} as follows. The number of variables $n$ was set to 5, 10, 30, and 50. The set $B$ of indices for which variables are binary was made by choosing $0.4n$ elements from $\{2,\dots,n\}$ randomly. All elements of $\bm{c}$ were independent and identically distributed (i.i.d.) and each followed the standard normal distribution. For each $n$, we made five instances varying the randomness of $B$ and $\bm{c}$. For each instance, the optimal value of the relaxation problem with $\mathcal{DNN}_{\rm NN}(\mathbb{K})$ (written as NN in Tables~\ref{tab:MISOCP_optval} and \ref{tab:MISOCP_time}), $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ (ZVP), and $\mathcal{DNN}_{\rm BD}(\mathbb{K})$ (BD) as well as the CPU time to solve the problems were measured. For reference, we also solved the problem~\eqref{prob:MISOCP} itself (MISOCP) and the relaxation problem with the semidefinite cone (SDP). To improve the numerical stability, $0.005\bm{I}$ was added to the coefficient matrix $\bm{C}$ in the standard form~\eqref{prob:GCPP} when we solved the SDP relaxation problems.

We mentioned that BD GDNNP can be solved with the ellipsoid method if $\mathbb{K}$ is a direct product of a nonnegative orthant and second-order cones. However, it is known that this method is quite slow in practice even though it is a polynomial-time algorithm~\cite{GLS1993}. Therefore, we solved it here as semi-infinite conic programming by adopting an algorithm based on the explicit exchange method~\cite{OHF2012} (see Appendix~\ref{apdx:algorithm} for the details of the algorithm).

\begin{table}[tbp]
\centering
\caption{Optimal values of problem~\eqref{prob:MISOCP} or its GDNNP and SDP relaxation problems.}
\begin{tabular}{rrrrrrr}
\hline
& & \multicolumn{5}{c}{Optimal value} \\
$n$ & No. & MISOCP & NN & ZVP & BD & SDP \\
\hline
5    & 1 & $-$4.01  & $-$4.01 & $-$4.01  & $-$4.01  & $-$30.56  \\
     & 2 & $-$3.18  & $-$3.18 & $-$3.18  & $-$3.18  & $-$4.93   \\
     & 3 & $-$0.28  & $-$0.28 & $-$0.31  & $-$0.28  & $-$16.86  \\
     & 4 & 0.00   & 0.00  & 0.00   & 0.00   & $-$106.50 \\
     & 5 & $-$1.47  & $-$1.47 & $-$1.47  & $-$1.47  & $-$163.54 \\
10   & 1 & $-$4.73  & OOM   & $-$4.74  & $-$4.77  & $-$42.56  \\
     & 2 & $-$5.43  & OOM   & $-$5.43  & $-$5.43  & $-$140.18 \\
     & 3 & $-$1.99  & OOM   & $-$1.99  & $-$1.99  & $-$13.20  \\
     & 4 & 0.00   & OOM   & $-$0.86  & 0.00   & $-$186.66 \\
     & 5 & $-$4.23  & OOM   & $-$4.23  & $-$4.23  & $-$53.90  \\
30   & 1 & $-$9.17  & OOM   & $-$9.17  & $-$9.62  & $-$328.08 \\
     & 2 & $-$9.42  & OOM   & $-$9.42  & $-$9.95  & $-$340.17 \\
     & 3 & $-$5.91  & OOM   & $-$5.91  & $-$6.00  & $-$120.07 \\
     & 4 & $-$3.05  & OOM   & $-$3.07  & $-$3.25  & $-$444.75 \\
     & 5 & $-$9.58  & OOM   & $-$9.58  & $-$10.14 & $-$362.77 \\
50   & 1 & $-$9.34  & OOM   & $-$9.34  & $-$10.93 & $-$489.81 \\
     & 2 & $-$9.70  & OOM   & $-$9.71  & $-$10.25 & $-$324.13 \\
     & 3 & $-$6.68  & OOM   & $-$6.69  & $-$7.16  & $-$293.58 \\
     & 4 & $-$3.30  & OOM   & $-$3.30  & $-$3.78  & $-$560.80 \\
     & 5 & $-$12.07 & OOM   & $-$12.10 & $-$13.29 & $-$750.69 \\
\hline
\end{tabular}
\label{tab:MISOCP_optval}
\end{table}

\begin{table}[tbp]
\centering
\caption{CPU time (s) required to solve problem~\eqref{prob:MISOCP} or its GDNNP and SDP relaxation problems.}
\begin{tabular}{rrrrrrr}
\hline
& & \multicolumn{5}{c}{CPU time (s)} \\
$n$ & No. & MISOCP & NN & ZVP & BD & SDP \\
\hline
5   & 1 & 0.11   & 44.79 & 0.45   & 5.07     & 0.12   \\
    & 2 & 0.09   & 47.51 & 0.19   & 2.13     & 0.12   \\
    & 3 & 0.11   & 44.56 & 0.23   & 2.40     & 0.12   \\
    & 4 & 0.09   & 40.39 & 0.17   & 2.29     & 0.12   \\
    & 5 & 0.09   & 48.20 & 0.17   & 2.87     & 0.12   \\
10  & 1 & 0.49   & OOM   & 0.55   & 8.27     & 0.25   \\
    & 2 & 0.12   & OOM   & 0.42   & 5.03     & 0.25   \\
    & 3 & 0.12   & OOM   & 0.42   & 3.95     & 0.21   \\
    & 4 & 0.11   & OOM   & 0.56   & 3.25     & 0.26   \\
    & 5 & 0.10   & OOM   & 0.43   & 3.00     & 0.35   \\
30  & 1 & 0.13   & OOM   & 11.95  & 514.90   & 14.97  \\
    & 2 & 0.13   & OOM   & 17.18  & 722.05   & 13.63  \\
    & 3 & 0.13   & OOM   & 14.77  & 617.47   & 15.03  \\
    & 4 & 0.15   & OOM   & 20.51  & 539.05   & 13.13  \\
    & 5 & 0.17   & OOM   & 11.65  & 486.40   & 14.19  \\
50  & 1 & 0.18   & OOM   & 150.92 & 10698.90 & 174.48 \\
    & 2 & 0.18   & OOM   & 174.87 & 11921.19 & 186.34 \\
    & 3 & 0.20   & OOM   & 157.36 & 10299.13 & 173.74 \\
    & 4 & 0.22   & OOM   & 249.99 & 11148.59 & 192.00 \\
    & 5 & 0.23   & OOM   & 173.28 & 10736.15 & 174.71 \\
\hline
\end{tabular}
\label{tab:MISOCP_time}
\end{table}
Tables~\ref{tab:MISOCP_optval} and \ref{tab:MISOCP_time} show the optimal values of the problem~\eqref{prob:MISOCP} or its GDNNP and SDP relaxation problems and the CPU time required to solve them, respectively, where ``OOM'' means that we could not solve the problem because of insufficient memory. First, we can see in Table~\ref{tab:MISOCP_optval} that the optimal values of the GDNNP relaxation problems are much better than those of the SDP relaxation problems and are close to those of the original problems. This implies that GDNNP relaxation can provide much tighter bounds than SDP relaxation.

Next, we compare the three types of GDNNP relaxation. We proved in Corollary~\ref{cor:DNN_inclusion_NN_ZVP} that $\mathcal{DNN}_{\rm NN}(\mathbb{K})$ is strictly included in $\mathcal{DNN}_{\rm ZVP}(\mathbb{K})$ when $\mathbb{K}$ is a direct product of a nonnegative orthant and second-order cones. We can observe that the strict inclusion relationship also appeared numerically in the case of $n=5$ and $\textrm{No.}= 3$ and that the optimal value of the NN GDNNP relaxation problem was better than that of the ZVP one. However, NN GDNNP relaxation took the longest time of the three and we could not compute the case of $n \ge 10$ because of insufficient memory.\footnote{We tried to solve the NN GDNNP relaxation problems on another computer with 64 GB of memory, but the same issue persisted.} We suspect that one of the reasons is that NN GDNNP relaxation is characterized by the semidefiniteness of the moment matrix. If the size of a variable matrix $\bm{X}$ in the standard form~\eqref{prob:GCPP} is $\bar{n}$, the NN GDNNP relaxation problem includes a semidefinite constraint of size $|I(\bar{n},2)| = \bar{n}(\bar{n}+1)/2$, while the ZVP GDNNP relaxation problem includes a semidefinite constraint of only size $\bar{n}$.

The results also show that ZVP GDNNP relaxation has better numerical properties than BD GDNNP relaxation. As illustrated in Example~\ref{ex:inZVP_notinBD} and \ref{ex:inBD_notinZVP}, the inclusion relationship between the ZVP and BD GDNN cones does not hold. However, the optimal values of the ZVP GDNNP relaxation problems are better than those of the BD in most cases, especially when $n\ge 30$. Moreover, we can see in Table~\ref{tab:MISOCP_time} that the computational time required to solve the ZVP GDNNP relaxation problems is much shorter than that for the BD ones. This is presumably because a ZVP GDNNP relaxation problem can be solved by calling a solver only once, whereas the algorithm used to solve a BD one needs to call a solver many times.

\section{Conclusion}
\label{sec:conclusion}
In this work, we aimed to provide a tighter and more efficient relaxation for GCPP. To achieve this, we focused on inner-approximation hierarchies for the GCOP cone. We first generalized Parrilo's hierarchy for the COP cone to that for the GCOP cone over a symmetric cone. Using this hierarchy as well as Zuluaga et al.'s hierarchy for the GCOP cone over a semialgebraic cone, we secondly proposed two (NN and ZVP) GDNN cones as the dual cone of the zeroth level of the hierarchies. Since the proposed GDNN cones are based on the approximation hierarchies, they are (if defined) always tractable, in contrast to the BD one. We also studied the inclusion relationship between three GDNN cones in the case where $\mathbb{K}$ is a direct product of a nonnegative orthant, and second-order cones or semidefinite cones in particular. We found that the NN GDNN cone is strictly included in the ZVP one theoretically and in the BD one numerically. Although there is no inclusion relationship between the ZVP and BD GDNN cones, the numerical experiment showed that the ZVP GDNN cone could give better relaxation than the BD one. These theoretical and numerical results demonstrate the superiority of the proposed GDNN cones over the BD one. Moreover, GDNNP relaxation gave much tighter bounds than SDP relaxation, which suggests a fruitful avenue for further study.

We listed four requirements that a GDNN cone should satisfy in Sect.~\ref{sec:DNN}. Although the three GDNN cones that appear in this paper satisfy these requirements, they are different sets from each other, which means we need to look at other properties of the DNN cone to decide on the most appropriate GDNN cone. For example, the matrix completability might provide a useful clue. It is known that the CP-completability of a partial CP matrix and the DNN-completability of a partial DNN one are both characterized by a block-clique graph~\cite{DJ1998}, so the completability of a partial GCP and GDNN matrix might be one key to considering this problem.

\vspace{0.5cm}
\noindent
{\bf Acknowledgments}
This work was supported by the Tokyo Tech Advanced Human Resource Development Fellowship for Doctoral Students and JSPS KAKENHI Grant Number JP20H02385.

\section*{Declarations}
{\bf Conflict of interest}
The authors declare that they have no conflict of interest.

\begin{appendices}
\section{Creation of vectors in $\mathcal{M}_{4,4}$}
\label{apdx:vector}
First, we created a $10\times 10$ (not necessarily symmetric) matrix $\bm{M}_{\rm nonsym}$ such that all elements of $\bm{M}_{\rm nonsym}$ were i.i.d. and each followed the standard normal distribution. Second, we let $\bm{M} = \bm{M}_{\rm nonsym}\bm{M}_{\rm nonsym}^\top$ and replaced some elements using the following MATLAB code:
\bigskip
\begin{Verbatim}[fontsize=\small,commandchars=\\\[\]]
M(1,2)\;=\;M(5,5);\;M(2,1)\;=\;M(5,5);\;M(1,3)\;=\;M(6,6);\;M(3,1)\;=\;M(6,6);
M(1,4)\;=\;M(7,7);\;M(4,1)\;=\;M(7,7);\;M(1,8)\;=\;M(5,6);\;M(8,1)\;=\;M(6,5);
M(1,9)\;=\;M(5,7);\;M(9,1)\;=\;M(7,5);\;M(1,10)\;=\;M(6,7);\;M(10,1)\;=\;M(7,6);
M(2,3)\;=\;M(8,8);\;M(3,2)\;=\;M(8,8);\;M(2,4)\;=\;M(9,9);\;M(4,2)\;=\;M(9,9);
M(2,6)\;=\;M(5,8);\;M(6,2)\;=\;M(8,5);\;M(2,7)\;=\;M(5,9);\;M(7,2)\;=\;M(9,5);
M(2,10)\;=\;M(8,9);\;M(10,2)\;=\;M(9,8);\;M(3,4)\;=\;M(10,10);\;M(4,3)\;=\;M(10,10);
M(3,5)\;=\;M(6,8);\;M(5,3)\;=\;M(8,6);\;M(3,7)\;=\;M(6,10);\;M(7,3)\;=\;M(10,6);
M(3,9)\;=\;M(8,10);\;M(9,3)\;=\;M(10,8);\;M(4,5)\;=\;M(7,9);\;M(5,4)\;=\;M(9,7);
M(4,6)\;=\;M(7,10);\;M(6,4)\;=\;M(10,7);\;M(4,8)\;=\;M(9,10);\;M(8,4)\;=\;M(10,9);
M(5,10)\;=\;M(7,8);\;M(6,9)\;= M(7,8);\;M(10,5)\;=\;M(8,7);\;M(9,6)\;=\;M(8,7).
\end{Verbatim}
\bigskip
If the matrix $\bm{M}$ obtained by the replacement is semidefinite, the vector $\bm{y}$ with $\bm{M} = \bm{M}_{4,4}(\bm{y})$ is in $\mathcal{M}_{4,4}$. We prepared 1000 different semidefinite matrices $\bm{M}_1,\dots,\bm{M}_{1000}$ and 1000 vectors $\bm{y}_1,\dots,\bm{y}_{1000}$ corresponding to them.

\section{Explicit exchange method for BD generalized doubly nonnegative programming}
\label{apdx:algorithm}
\begin{algorithm}[t]
\caption{Explicit exchange method for BD GDNNP~\eqref{prob:GDNN_BD} with a symmetric cone $\mathbb{K}$.}
\label{alg:explicit}
\begin{description}
\item[\bf Step 0.]Choose a positive sequence $\{\gamma_k\}_k$ such that $\gamma_k \downarrow 0\ (k\to\infty)$, a positive value $\tau$, and a finite subset $\mathfrak{J}^{(0,0)}$ of $\mathfrak{J}(\mathbb{K})$. Solve ${\rm P}(\mathfrak{J}^{(0,0)})$ to obtain an optimal solution $\bm{X}^{(0,0)}$, where ${\rm P}(\mathfrak{J}')$ is defined as
\begin{equation*}
{\rm P}(\mathfrak{J}'):\quad
\begin{alignedat}{3}
&\mathop{\rm minimize}\limits_{\bm{X}} && \quad \langle \bm{C},\bm{X}\rangle \\
&\subjectto && \quad \langle \bm{A}_i, \bm{X}\rangle = b_i\ (i=1,\dots,m),\\
&&&\quad \bm{X}\in \mathbb{S}_+^n,\\
&&&\quad \bm{X}\bm{s} \in \mathbb{K}\ (\forall\bm{s}\in \mathfrak{J}')
\end{alignedat}
\end{equation*}
for a finite subset $\mathfrak{J}'$ of $\mathfrak{J}(\mathbb{K})$. Set $k \coloneqq 0$.
\item[\bf Step 1.]Obtain $\bm{X}^{(k+1,0)}$ and $\mathfrak{J}^{(k+1,0)}$ by the following procedure.
\begin{description}
\item [\bf Step1-1.]Set $r\coloneqq 0$.
\item [\bf Step1-2.]Try to find $\bm{s}_{\rm new}^{(k,r)}$ such that $\lambda_{\rm min}(\bm{X}^{(k,r)}\bm{s}_{\rm new}^{(k,r)} + \gamma_k\bm{e}) < 0$.
\begin{enumerate}[(a)]
\item If there exists such $\bm{s}_{\rm new}^{(k,r)}$, let $\overbar{\mathfrak{J}}^{(k,r+1)} \coloneqq \mathfrak{J}^{(k,r)}\cup\{\bm{s}_{\rm new}^{(k,r)}\}$ and solve ${\rm P}(\overbar{\mathfrak{J}}^{(k,r+1)})$ to find an optimal solution $\bm{X}^{(k,r+1)}$ and optimal dual variables $\bm{v}_{\bm{s}}^{(k,r+1)}\ (\bm{s}\in\overbar{\mathfrak{J}}^{(k,r+1)})$. Let $\mathfrak{J}^{(k,r+1)}\coloneqq \{\bm{s}\in\overbar{\mathfrak{J}}^{(k,r+1)}\mid \bm{v}_{\bm{s}}^{(k,r+1)}\neq\bm{0}\}$. Set $r \coloneqq r + 1$ and go to the beginning of Step 1-2; \label{enum:is_exist}
\item Otherwise, let $\bm{X}^{(k+1,0)} \coloneqq \bm{X}^{(k,r)}$ and $\mathfrak{J}^{(k+1,0)} \coloneqq \mathfrak{J}^{(k,r)}$.\label{enum:isnot_exist}
\end{enumerate}
\end{description}
\item[\bf Step 2.]If $\gamma_k \le \tau$, stop the algorithm. Otherwise, set $k \coloneqq k + 1$ and go to Step 1.
\end{description}
\end{algorithm}
The algorithm used to solve BD GDNNP is shown in Algorithm~\ref{alg:explicit}. Note that the algorithm works as long as $\mathbb{K}$ is a symmetric cone in $\mathbb{R}^n$ but not necessarily a direct product of a nonnegative orthant and second-order cones. In this paper, $\gamma_k$ was set to $0.5^k$ in advance, but if case~\eqref{enum:is_exist} in Step 1-2 occurred five times in a row, $\gamma_{k+1}$ was set to $\tau$ at the end of Step 2 and returned to Step 1 to make the convergence faster. The threshold value $\tau$ in Algorithm~\ref{alg:explicit} was set to $10^{-5}$. The subset $\mathfrak{J}^{(0,0)}$ was set to $\emptyset$. We tried to find $\bm{s}_{\rm new}^{(k,r)}$ in the following way. Since
\begin{equation*}
\mathfrak{J}(\mathbb{K}) = \{(\bm{e}_i,\bm{0}_n)\mid i = 1,\dots,2n+1\} \cup \{(\bm{0}_{2n+1},1/2,\bm{v}/2)\mid \bm{v}\in S^{n-2}\}
\end{equation*}
in this experiment, before starting the algorithm, we took
\begin{equation*}
\mathfrak{J}_{\rm fix} = \{(\bm{e}_i,\bm{0})\mid i = 1,\dots,2n+1\} \cup \{(\bm{0},1/2,\bm{v}_i/2)\mid i = 1,\dots,1000\},
\end{equation*}
where each $\bm{v}_i$ was generated from $S^{n-2}$ randomly.
In Step 1-2, we first checked whether there exists $\bm{s}_{\rm new} \in \mathfrak{J}_{\rm fix}$ such that $\lambda_{\rm min}(\bm{X}^{(k,r)}\bm{s}_{\rm new} + \gamma_k\bm{e}) < 0$. If it exists, let $\bm{s}_{\rm new}^{(k,r)} = \bm{s}_{\rm new}$. Otherwise, we next solved the optimization problem $\min_{\bm{s}\in \mathfrak{J}(\mathbb{K})}\lambda_{\rm min}(\bm{X}^{(k,r)}\bm{s} + \gamma_k\bm{e})$. As explained in Sect.~\ref{subsec:soc}, when $\mathbb{K}$ is a direct product of a nonnegative orthant and second-order cones, it is easy to check whether the optimal value of the problem is less than 0. (Note that $\min_{\bm{s}\in \mathfrak{J}(\mathbb{K})}\lambda_{\rm min}(\bm{X}^{(k,r)}\bm{s} + \gamma_k\bm{e}) = \min_{\bm{s}\in \mathfrak{J}(\mathbb{K})}\lambda_{\rm min}(\bm{X}^{(k,r)}\bm{s}) + \gamma_k$.) In addition, $\bm{v}_{\bm{s}}^{(k,r+1)}$ was regarded as $\bm{0}$ if $\|\bm{v}_{\bm{s}}^{(k,r+1)}\| \le 10^{-12}$.
\end{appendices}

redpajama_set_name: RedPajamaArXiv