# Sparse Conic Reformulation of Structured QCQPs based on Copositive
Optimization with Applications in Stochastic Optimization

Markus Gabl  IOR, Karlsruhe Institute of Technology, Germany.
<EMAIL_ADDRESS>

###### Abstract

Recently, Bomze et. al. introduced a sparse conic relaxation of the scenario
problem of a two stage stochstic version of the standard quadratic
optimization problem. When compared numerically to Burer’s classical
reformulation, the authors showed that there seems to be almost no difference
in terms of solution quality, whereas the solution time can differ by orders
of magnitudes. While the authors did find a very limited special case, for
which Burer’s reformulation and their relaxation are equivalent, no satisfying
explanation for the high quality of their bound was given. This article aims
at shedding more light on this phenomenon and give a more thorough theoretical
account of its inner workings. We argue that the quality of the outer
approximation cannot be explained by traditional results on sparse conic
relaxations based on positive semidenifnite or completely positive matrix
completion, which require certain sparsity patterns characterized by chordal
and block clique graphs respectively, and put certain restrictions on the type
of conic constraint they seek to sparsify. In an effort to develope an
alternative approach, we will provide a new type of convex reformulation of a
large class of stochastic quadratically constrained quadratic optimization
problems that is similar to Burer’s reformulation, but lifts the variables
into a comparatively lower dimensional space. The reformulation rests on a
generalization of the set-completely positive matrix cone. This cone can then
be approximated via inner and out approximations in order to obtain upper and
lower bounds, which potentially close the optimality gap, and hence can give a
certificate of exactness for these sparse reformulations outside of
traditional, known sufficient conditions. Finally, we provide some numerical
experiments, where we asses the quality of the inner and outer approximations,
thereby showing that the approximations may indeed close the optimality gap in
interesting cases.

Keywords: Quadratic Optimization $\cdot$ Copositive Optimization$\cdot$ Matrix
Completion $\cdot$ Conic Optimization

##  1 Introduction

Recently, in [3], the authors considered the scenario problem of a two-stage
stochastic version of the standard quadratic optimization problem given by

$\displaystyle\min_{\mathbf{x}\in\mathbb{R}^{n_{1}},\mathbf{y}_{i}\in\mathbb{R}^{n_{2}}}\left\\{\mathbf{x}^{\mathsf{T}}{\mathsf{A}}\mathbf{x}+\sum_{i=1}^{S}p_{i}\left(\mathbf{x}^{\mathsf{T}}{\mathsf{B}}_{i}\mathbf{y}_{i}+\mathbf{y}_{i}^{\mathsf{T}}{\mathsf{C}}_{i}\mathbf{y}_{i}\right)\colon(\mathbf{x},\mathbf{y}_{i})\in\Delta,\
i\in[1\\!:\\!S]\right\\},$ (2St3QP)

where $\Delta\subset\mathbb{R}^{n_{1}+n_{2}}$ is the unit simplex, and
$p_{i},\ i\in[1\\!:\\!S]$ are probabilities of certain scenarios occurring.
This optimization problem can be exactly reformulated into a copositive
optimization problem based on Burer’s reformulation presented in [4]. The
reformulation forces a lifting of the space of variables into a space of
dimension $O((n_{1}+Sn_{2})^{2})$, which makes this reformulation entirely
impractical for the purposes of stochastic optimization since the number of
scenarios $S$ is typically very high and the copostive optimization problem
has to be approximated with semidefinite optimization problems, which are
known to scale poorly. In an effort to circumvent this issue, the authors
introduced a copositive relaxation that merely requires
$O(S(n_{1}+n_{2})^{2})$ variables and showed empirically that the
approximating SDPs are practical even if the number of scenarios is high.
Somewhat surprisingly, they observed that the quality of the solutions they
found did not substantially differ from the bound obtained by employing the
traditional copositive reformulation. In fact they state that the difference
was small enough to possibly be an artifact of numerical inaccuracies of the
sdp-solver. Aside from an exactness result for a niche case of (2St3QP) no
theoretical explanation for this phenomenon was provided. The present article
is chiefly motivated by the question: why does the cheap relaxation perform so
well? While we were not able to fully answer this question, we are still able
to provide valuable theoretical insights that amount to a novel, practical
approach to sparse conic reformulations. In short we introduce a
generalization of the set-completely positive matrix cones that yield conic
relaxations that are sparse to begin with, and which can, much like the
traditional set-completely positive matrix cones, be approximated in order to
generate lower and upper bounds, that may certify optimality in case the gap
between them is zero.

To set up our exposition, we will now introduce a more general quadratic
optimization problem and discuss some important context, specifically
copositive optimization and sparse conic reformulations based on matrix
completion. To begin with, the class optimization problems in question is
given by:

$\displaystyle\begin{split}\min_{\mathbf{x},\mathbf{y}_{i}}\mathbf{x}^{\mathsf{T}}{\mathsf{A}}\mathbf{x}+\mathbf{a}^{\mathsf{T}}\mathbf{x}&+\sum_{i=1}^{S}\mathbf{x}^{\mathsf{T}}{\mathsf{B}}_{i}\mathbf{y}_{i}+\mathbf{y}_{i}^{\mathsf{T}}{\mathsf{C}}_{i}\mathbf{y}_{i}+\mathbf{c}_{i}^{\mathsf{T}}\mathbf{y}_{i}\\\
\mathrm{s.t.:}\
{\mathsf{F}}_{i}\mathbf{x}+{\mathsf{G}}_{i}\mathbf{y}_{i}&={\mathbf{r}}_{i},\quad\hskip
1.70709pti\in[1\\!:\\!S],\\\
Q_{j}(\mathbf{x},\mathbf{y}_{1},\dots,\mathbf{y}_{S})&=0,\quad\hskip
2.84544ptj\in[1\\!:\\!K],\\\ \mathbf{x}&\in{\mathcal{K}}_{0},\\\
\mathbf{y}_{i}&\in{\mathcal{K}}_{i},\quad i\in[1\\!:\\!S],\end{split}$ (1)

where ${\mathcal{K}}_{0}\subseteq\mathbb{R}^{n_{1}},\
{\mathcal{K}}_{i}\subseteq\mathbb{R}^{n_{2}},\ i\in[1\\!:\\!S]$, are closed,
convex cones, ${\mathsf{A}}\in\SS^{n_{1}}$ (i.e. symmetric matrices of oder
$n_{1}$), $\ \mathbf{a}\in\mathbb{R}^{n_{1}}$,
${\mathsf{B}}_{i}\in\mathbb{R}^{n_{1}\times n_{2}},\
{\mathsf{C}}_{i}\in\SS^{n_{2}},\mathbf{c}_{i}\in\mathbb{R}^{n_{2}},\
i\in[1\\!:\\!S]$ and ${\mathsf{F}}_{i}\in\mathbb{R}^{m_{i}\times n_{1}},\
{\mathsf{G}}_{i}\in\mathbb{R}^{m_{i}\times n_{2}},\
{\mathbf{r}}_{i}\in\mathbb{R}^{m_{i}},\ i\in[1\\!:\\!S]$. Further,
$Q_{j}(\cdot)\colon\mathbb{R}^{n_{1}+Sn_{2}}\rightarrow\mathbb{R},\
j\in[1\\!:\\!K]$ are quadratic functions that do not involve bilinear terms
between $\mathbf{y}_{i}$ and $\mathbf{y}_{j}$ for $i\neq j$. The special
structure in place here is that $\mathbf{y}_{i}$ does not interact with
$\mathbf{y}_{j}$ in a bilinear fashion in neither the constraints nor the
objective, and the statement stays true even if the linear constraints are
squared.

This setup encompasses not only (2St3QP), but general two-stage stochastic
conic QCQPs over finitely supported distributions, which are important since
they are used to approximate two-stage stochastic conic QCQPs with infinite
support. In the context of two-stage stochastic optimization, $S$ would be the
number of scenarios and $\mathbf{y}_{i}$ would be variables specific to
scenario $i$. Hence, the special structure in (1) is native to all two-stage
stochastic QCQPs regardless of the structure of the nominal QCQP.

Under some well known regularity conditions on the functions $Q_{i}(.)$ (see
[5, 11, 7]) our structured QCQP can be reformulated into a conic optimization
problem with ${\mathcal{O}}\left((n_{1}+Sn_{2})^{2}\right)$ variables. This
reformulation takes the form:

$\displaystyle\begin{split}\min_{{\mathsf{X}},{\mathsf{Y}}_{i},{\mathsf{Z}}_{i},\mathbf{x},\mathbf{y}_{i}}\mathrm{Tr}({\mathsf{A}}_{i}{\mathsf{X}})+\mathbf{a}^{\mathsf{T}}\mathbf{x}&+\sum_{i=1}^{S}\mathrm{Tr}({\mathsf{B}}_{i}{\mathsf{Z}}_{i})+\mathrm{Tr}({\mathsf{C}}_{i}{\mathsf{Y}}_{i,i})+\mathbf{c}_{i}^{\mathsf{T}}\mathbf{y}\\\
\mathrm{s.t.:}\
{\mathsf{F}}_{i}\mathbf{x}+{\mathsf{G}}_{i}\mathbf{y}_{i}&={\mathbf{r}}_{i},\quad\hskip
19.91684pti\in[1\\!:\\!S],\\\
\operatorname{diag}\left(\begin{pmatrix}{\mathsf{F}}_{i}&{\mathsf{G}}_{i}\end{pmatrix}\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\begin{pmatrix}{\mathsf{F}}_{i}^{\mathsf{T}}\\\
{\mathsf{G}}_{i}^{\mathsf{T}}\end{pmatrix}\right)&={\mathbf{r}}_{i}\circ{\mathbf{r}}_{i},\quad
i\in[1\\!:\\!S],\\\
\hat{Q}_{j}(\mathbf{x},{\mathsf{X}},\mathbf{y}_{1},{\mathsf{Z}}_{1},{\mathsf{Y}}_{1},\dots,\mathbf{y}_{S},{\mathsf{Z}}_{S},{\mathsf{Y}}_{S})&=0,\quad\hskip
17.64056pt\ j\in[1\\!:\\!K],\\\
\begin{pmatrix}1&\mathbf{x}^{\mathsf{T}}&\mathbf{y}_{1}^{\mathsf{T}}&\dots&\mathbf{y}_{S}^{\mathsf{T}}\\\
\mathbf{x}&{\mathsf{X}}&{\mathsf{Z}}_{1}^{\mathsf{T}}&\dots&{\mathsf{Z}}_{S}^{\mathsf{T}}\\\
\mathbf{y}_{1}&{\mathsf{Z}}_{1}&{\mathsf{Y}}_{1,1}&\dots&{\mathsf{Y}}_{1,S}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
\mathbf{y}_{S}&{\mathsf{Z}}_{S}&{\mathsf{Y}}_{S,1}&\dots&{\mathsf{Y}}_{S,S}\end{pmatrix}&\in\mathcal{CPP}(\mathbb{R}_{+}\times_{i=0}^{S}{\mathcal{K}}_{i}).\end{split}$
(2)

for appropriate linear functions $\hat{Q}_{ij}$ with
$\hat{Q}_{ij}(\mathbf{x},\mathbf{x}\mathbf{x}^{\mathsf{T}},\mathbf{y}_{1},\mathbf{y}_{1}\mathbf{x}^{\mathsf{T}},\mathbf{y}_{1}\mathbf{y}_{1}^{\mathsf{T}},\dots,\mathbf{y}_{S},\mathbf{y}_{S}\mathbf{x}^{\mathsf{T}},\mathbf{y}_{S}\mathbf{y}_{S}^{\mathsf{T}})=Q_{ij}(\mathbf{x},\mathbf{y}_{1},\dots,\mathbf{y}_{S})$,
with $\circ$ denoting the elementwise multiplication of vectors, and the set-
completely positive matrix cone is define as

$\displaystyle\mathcal{CPP}_{n}({\mathcal{K}})$
$\displaystyle\coloneqq\left\\{\sum_{i=1}^{k}\mathbf{x}_{i}\mathbf{x}_{i}^{\mathsf{T}}\colon\mathbf{x}_{i}\in{\mathcal{K}},\
i\in[1\\!:\\!k]\right\\}$
$\displaystyle=\mathrm{clconv}\left\\{\mathbf{x}\mathbf{x}^{\mathsf{T}}\colon\mathbf{x}\in{\mathcal{K}}\right\\}=\\{{\mathsf{X}}{\mathsf{X}}^{\mathsf{T}}\colon{\mathsf{X}}\in\mathbb{R}^{n\times
k}\,,\,\mathbf{x}_{i}\in{\mathcal{K}},\,i\in[1\\!:\\!k]\\},$

for a closed, convex cone ${\mathcal{K}}\subseteq\mathbb{R}^{n}$. For example,
$\mathcal{CPP}(\mathbb{R}^{n})$ is the positive semidefinite matrix cone,
denoted by $\SS^{n}_{+}$, and $\mathcal{CPP}(\mathbb{R}^{n}_{+})$ is the
classical completely positive matrix cone, extensively discussed in [1]. In
the literature, optimization over the set-completely positive cone and its
dual, the set-copositive matrix cone is colloquially referred to as copositive
optimization. In general, set-completely positive matrix cones are intractable
and have to be approximated. For example, it is well known that

$\displaystyle\mathcal{CPP}(\mathbb{R}^{n}_{+})\subseteq\mathcal{DNN}^{n}\coloneqq\SS^{n}_{+}\cap{\mathcal{N}}^{n},$

where ${\mathcal{N}}^{n}$ is the cone of nonnegative $n\times n$ matrices and
$\mathcal{DNN}^{n}$ is called the doubly nonnegative matrix cone.

While many tractable approximations do exist, be it based on positive
semidefinite, second order cone or linear programming constraints, they all
have in common that their complexity increases exponentially with the
approximations quality. Even simple approximations, such as
$\mathcal{DNN}^{n}$, typically involve semidefinite constraints of the same
order as the set-completely positive constraint. As a result the above
reformulation is often impractical. Especially in the context of stochastic
optimization, where the number of scenarios $S$ is typically very high, the
size of the psd-constraints, which is of the order
${\mathcal{O}}\left((n_{1}+Sn_{2})^{2}\right)$, becomes prohibitive.

Following the basic idea of the authors in [3], we can obtain a lower
dimensional relaxation by replacing the conic constraint by $S$ smaller conic
constraints given by

$\displaystyle\begin{pmatrix}1&\mathbf{x}^{\mathsf{T}}&\mathbf{y}_{i}^{\mathsf{T}}\\\
\mathbf{x}&{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
\mathbf{y}_{i}&{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i,i}\end{pmatrix}\in\mathcal{CPP}\left(\mathbb{R}_{+}\times{\mathcal{K}}_{i}\right),\
i\in[1\\!:\\!S],$ (3)

so that the number of variables is now
${\mathcal{O}}\left(S(n_{1}+n_{2})^{2}\right)$, therefore linear in $S$. The
cost we have to pay is that the resulting optimization problem is not
necessarily equivalent to (2) and hence to (1), as the conic constraints are
clearly a relaxation of the conic constraint of the exact reformulation. It
is, however, this relaxation which performed so inexplicably well when it was
applied in [3].

In searching for an explanation of this performance, one may turn to the
literature on sparse reformulations of conic optimization problems. Results in
this field are typically based on theorems on matrix completion. The central
question in that area is, when a given matrix with non-specified entries, so
called partial matrices, can be completed to a matrix in
$\mathcal{CPP}({\mathcal{K}})$. This is useful in the context of solving a
conic optimization problem: if the problem data is sparse so that some of the
entries of the matrix variable only appear in the conic constraint, one can
check if the removal of that entries leaves a partial matrix for which one can
give sufficient conditions so that it is completable to a matrix that fulfills
the original conic constraint. If such conditions are available, they replace
the conic constraint and the spurious entries of the matrix can be dropped
entirely. The result is, what we will call a sparse reformulation of the
original conic problem. These reformulations can reduce the number of
variables substantially, which eases the computational burden so that
otherwise unmanageable problems become viable.

The classical text on such an approach is [15], where the conic constraint to
be massaged is an sdp-constraint. Their approach utilizes the fact that a
partial matrix, where the non-specified entries exhibit the so called chordal
sparsity pattern can always be completed to a psd-matrix provided all fully
specified, principle submatrices are positive semidefinite. The framework was
applied in various contexts such as robust optimization [13] or optimal power
flow [8, 14]. A similar approach was recently put forward by [10], who applied
classical $\mathcal{CPP}(\mathbb{R}^{n}_{+})$-completion results derived in
[6] in the context of copositive optimization. Their approach necessitates the
presence of so called block-clique sparsity patterns in the problem data,
owing to the fact that partial matrices with block-clique specification
pattern can be completed to matrices in $\mathcal{CPP}(\mathbb{R}^{n}_{+})$
whenever the fully specified, principle submatrices are completely positive.

Unfortunately, none of these results are able to explain the phenomenon we
seek to investigate and we will spend a full section on discussing their
shortcomings and what we can still learn from them about our object of
interest. We will argue that, unless ${\mathcal{K}}=\mathbb{R}^{n}$, the
required sparsity patterns are, outside of some limited special cases, not the
ones present in (2), where the sparsity pattern takes the form of an arrow-
head. Also, in cases where ${\mathcal{K}}$ is neither the positive orthant nor
the full space, completion results are, to the best of our knowledge, entirely
absent from literature.

#### Contribution

In an effort to remedy these shortcummings, we propose a new approach to
sparse conic reformulations. Rather than treating completability of a matrix
as an abstract concept we identify a cone that is isomorphic to the cone of
completeable partial matrices with arrowhead sparsity pattern, denoted
$\mathcal{CMP}$, as a generalization of the set-completely positive matrix
cone. We show that the geometry of this cone can be used in order to derive a
lower dimensional alternative to the exact reformulation (2). Much the same
way one uses inner and outer approximations in order to solve copositive
optimization problems, we derive inner and outer approximations of
$\mathcal{CMP}$ in order to obtain upper and lower bounds to this new conic
optimization problem. Numerical experiments show that in practice these
approximations exhibit interesting beneficial properties.

#### Outline

The rest of the article is organized as follows: In Section 2 we will give a
short discussion on existing approaches to sparse conic optimization and
discuss the limitations that ultimately make these techniques unfit to tackle
sparse reformulations of (2). Hence, we develop an alternative approach in
Section 3, based on the aforementioned convex cone $\mathcal{CMP}$. This new
type of convex reformulation motivates a strategy to sparse optimization that
is analogous to classical copositive optimization techniques, where difficult
conic constraints are approximated via inner and outer approximations. In
Section 4 we present many such approximations and discuss their limitations.
Finally, we asses the efficacy of our approach in extensive numerical
experiments.

### Notation

Throughout the paper matrices are denoted by sans-serif capital letters (e.g.
${\mathsf{O}}$ will denote the zero matrix, where the size will be clear from
the context), vectors by boldface lower case letters (e.g. $\mathbf{o}$ will
denote the zero vector,$\mathbf{e}_{i}$ will denote a vector of zeros with a
one at the $i$-th coordinate) and scalars (real numbers) by simple lower case
letters. Sets will be denoted using calligraphic letters, e.g., cones will
often be denoted by ${\mathcal{K}}$. We use $\SS^{n}$ to indicate the set of
symmetric matrices and $\SS^{n}_{+}$/$\SS^{n}_{-}$ for the sets of
positive-/negative-semidefinite symmetric matrices, respectively. Moreover, we
use ${\mathcal{N}}_{n}$ to denote the set of entrywise nonnegative, symmetric
matrices. We also use the shorthand notation
$[l\\!:\\!k]\coloneqq\left\\{l,l+1,\dots,k-1,k\right\\}\subseteq\mathbb{N}$.
For a given set ${\mathcal{A}}$ we denote its convex hull by
$\mathrm{conv}({\mathcal{A}})$. For a convex set ${\mathcal{C}}$, the set of
generators of its extreme rays and points is given by
$\mathrm{ext}({\mathcal{C}})$. We also make use of the Frobenius product of
two appropriately sized matrices ${\mathsf{A}}$ and ${\mathsf{B}}$ defined as
${\mathsf{A}}\bullet{\mathsf{B}}\coloneqq\mathrm{trace}({\mathsf{A}}^{\mathsf{T}}{\mathsf{B}})$,
which can be interpreted as the sum of the inner products of the columns of
${\mathsf{A}}$ and ${\mathsf{B}}$.

##  2 Classical approaches to sparse conic optimization and why they fail

As stated in the introduction, there are already many approaches for utilizing
sparsity patterns in conic optimization problems. At the core of these results
lie matrix completion theorems, which we will discuss shortly. But in order to
state them we must introduce some essential terms first.

A graph $G=({\mathcal{V}},{\mathcal{E}})$ is given by its set of vertices
${\mathcal{V}}=\left\\{v_{1},\dots,v_{n}\right\\}$ and its set of edges
${\mathcal{E}}\subseteq\left\\{\left\\{v,u\right\\}\colon
v,u\in{\mathcal{V}}\right\\}$, both of which are finite. A subgraph
$T=({\mathcal{V}}_{T},{\mathcal{E}}_{T})$ of a graph $G$ is a graph such that
${\mathcal{V}}_{T}\subseteq{\mathcal{V}}$ and
${\mathcal{E}}_{T}\subseteq{\mathcal{E}}$. Vertex $v_{j}$ is adjacent to
$v_{j}$ and vice versa if $\left\\{v_{i},v_{j}\right\\}\in{\mathcal{E}}$. If
$e=\\{v_{i},v_{j}\\}\in{\mathcal{E}}$ then $v_{i}$ and $v_{j}$ are incident on
$e$. A graph where all vertices are adjacent to one another is called a
complete graph. A path that connects vertex $v_{i}$ with $v_{j}$ is given by a
sequence of edges so that $\\{v_{1}.v_{k_{1}}\\},\dots,\\{v_{k_{p}},v_{j}\\}$,
$v_{k_{i}}$ are distinct and $p>1$ is the length of that path. A graph is
connected if any two vertices have a connecting path. A graph that is not
connected is disconnected. A cycle is path that connects a vertex $v$ to
itself. A chord of a cycle with length greater than 3 is an edge that connects
two vertexes who are incident on two different edges of the cycle. A graph is
chordal if every cycle with length greater 3 has a chord. A subgraph of $G$
that is complete is called a clique. A block $B$ of a graph is a subgraph that
is connected, has no disconnected subgraph that is obtained by removing just
one vertex and its adjacent edges (i.e. a cut vertex) from $B$, and is not
contained in any other subgraph with these two properties. A block-clique
graph is a graph whose blocks are cliques.

A partial matrix of order $n$ is a matrix whose entries in the $i$-th row and
the $j$-th column are determined if and only if
$(i,j)\in{\mathcal{I}}\subseteq[1\\!:\\!n]^{2}$ and are undetermined
otherwise. A matrix is said to be partial positive semidefinite/ completely
positive/ doubly nonnegative if and only if every fully determined principal
submatrix is positive semidefinite/ completely positive/ doubly nonnegative. A
partial matrix is positive semidefinite/ completely positive/ doubly
nonnegative completable if we can specify the undetermined entries so that the
fully specified matrix is semidefinite/ completely positive/ doubly
nonnegative.

The specification graph of partial matrix ${\mathsf{A}}$ of order $n$ is a
graph $G({\mathsf{A}})$ with vertices ${\mathcal{V}}=\left\\{v_{i}\colon
i\in[1\\!:\\!n]\right\\}$ and edges ${\mathcal{E}}$ such that
$\left\\{v_{i},v_{j}\right\\}\in{\mathcal{E}}$ if and only if the entry
$a_{ij}$ is specified. A symmetric matrix with $G({\mathsf{A}})=G$ is called a
symmetric matrix realization of $G$.

The following three theorems give the key results on matrix completion as far
as this text is concerned:

######  Theorem 1.

All partial positive semidefinite symmetric matrix realizations of a graph $G$
are positive semidefinite completable if and only if $G$ is chordal.

###### Proof.

See [1, Theorem 1.39]. ∎

######  Theorem 2.

Every partial completely positive matrix realization of a graph $G$ is
completely positive completable if and only if G is a block-clique graph

###### Proof.

See [1, Theorem 2.33]. ∎

######  Theorem 3.

Every partial doubly nonnegative matrix realization of a graph $G$ is doubly
nonnegative completable if and only if G is a block-clique graph

###### Proof.

See [6]. ∎

These theorems can be used in order to establish that a constraint on a high-
dimensional matrix, say ${\mathsf{X}}$, can be replaced by a number of
constraints on certain, principal submatrices of ${\mathsf{X}}$ without
increasing the feasible set. This is achieved by showing that values for the
submatrices of ${\mathsf{X}}$ that fulfill the latter constraints can be
completed to a full evaluation of ${\mathsf{X}}$ that fulfills the original
larger constraint. For the sake of illustration we present the following toy
example.

######  Example 1.

Consider the optimization problem

$\displaystyle\min_{{\mathsf{X}}\in\SS^{n}_{+}}\left\\{{\mathsf{Q}}\bullet{\mathsf{X}}\colon{\mathsf{B}}\bullet{\mathsf{X}}=1\right\\},$
(4)

where $({\mathsf{Q}})_{ij}=({\mathsf{B}})_{ij}=0$ if $|i-j|>1$, the remaining
entries of ${\mathsf{B}}$ equal one and those of ${\mathsf{Q}}$ are arbitrary.
The entries of ${\mathsf{X}}$ that are outside the inner band of width 1 are
not present in neither the equality constraint nor the objective. Consider the
relaxation of (4) where the psd-constraints is replaced by

$\displaystyle\begin{pmatrix}X_{ii}&X_{ij}\\\
X_{ji}&X_{jj}\end{pmatrix}\in\SS^{2}_{+}\quad\forall(i,j)\colon|i-j|=1,\ i<j,$
(5)

and the entries of ${\mathsf{X}}$ outside of the inner band are dropped from
the problem. Clearly, we obtain a relaxation of the original problem since the
new condition is necessary for the ${\mathsf{X}}$ to be positive semidefinite.
Also, the fact that we dropped entries of ${\mathsf{X}}$ can be thought of as
a replacement of the matrix ${\mathsf{X}}$ by a partial matrix, say
${\mathsf{X}}_{*}$, whose entries outside the inner band are not specified. In
this case the specification graph of ${\mathsf{X}}_{*}$ is easily checked to
be chordal, as it doesn’t contain any cycles at all. Hence, if all fully
specified submatrices of ${\mathsf{X}}_{*}$ are positive semidefinite, i.e.
(5) holds, then it can be completed to positive semidefinite matrix by 1. The
resulting matrix would be feasible for (4) with the same objective function
value, so that the relaxation turns out to be lossless.

One may attempt to similarly derive a sparse reformulation of (8) by invoking
the completion results we discussed above. This would necessitate to show that
a partial matrix of the following form

$\displaystyle\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{1}^{\mathsf{T}}&{\mathsf{Z}}_{2}^{\mathsf{T}}&\dots&{\mathsf{Z}}_{S-1}^{\mathsf{T}}&{\mathsf{Z}}_{S}^{\mathsf{T}}\\\
{\mathsf{Z}}_{1}&{\mathsf{Y}}_{1,1}&\mathbf{*}&\dots&\mathbf{*}&\mathbf{*}\\\
{\mathsf{Z}}_{2}&\mathbf{*}&{\mathsf{Y}}_{2,2}&\dots&\mathbf{*}&\mathbf{*}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
{\mathsf{Z}}_{S-1}&\mathbf{*}&\mathbf{*}&\dots&{\mathsf{Y}}_{S-1,S-1}&\mathbf{*}\\\
{\mathsf{Z}}_{S}&\mathbf{*}&\mathbf{*}&\dots&\mathbf{*}&{\mathsf{Y}}_{S,S}\end{pmatrix},\
$

can be completed to a set-completely positive matrix whenever the submatrices

$\displaystyle\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i,i}\end{pmatrix}\in\mathcal{CPP}\left({\mathcal{K}}_{0}\times{\mathcal{K}}_{i}\right),\
i\in[1\\!:\\!S].$

Note, that this would coincide with the model in [3], which we discussed in
the introduction, so that the matrix completion theory is a promising
contender for the desired explanation for the effectiveness of the model. The
strategy appears feasible at first, at least for the case where
${\mathcal{K}}_{i}$ are nonnegative orthants given that in this case,
completion results are readily available. Unfortunately it is futile, since
the arrowhead structure is not block-clique outside of narrow special cases,
as we will now show.

######  Lemma 4.

Let $S>1$ and consider a partial matrix of where the specified entries exhibit
an arrow-head structure, i.e.

$\displaystyle\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{1}^{\mathsf{T}}&{\mathsf{Z}}_{2}^{\mathsf{T}}&\dots&{\mathsf{Z}}_{S-1}^{\mathsf{T}}&{\mathsf{Z}}_{S}^{\mathsf{T}}\\\
{\mathsf{Z}}_{1}&{\mathsf{Y}}_{1,1}&\mathbf{*}&\dots&\mathbf{*}&\mathbf{*}\\\
{\mathsf{Z}}_{2}&\mathbf{*}&{\mathsf{Y}}_{2,2}&\dots&\mathbf{*}&\mathbf{*}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
{\mathsf{Z}}_{S-1}&\mathbf{*}&\mathbf{*}&\dots&{\mathsf{Y}}_{S-1,S-1}&\mathbf{*}\\\
{\mathsf{Z}}_{S}&\mathbf{*}&\mathbf{*}&\dots&\mathbf{*}&{\mathsf{Y}}_{S,S}\end{pmatrix},\
$

where ${\mathsf{X}}\in\SS^{n_{1}},\ {\mathsf{Y}}_{i,i}\in\SS^{n_{2}},\
{\mathsf{Z}}_{i}\in\mathbb{R}^{n_{2}\times n_{1}},\ i\in[1\\!:\\!S],$ and let
$G_{spec}$ be its specification graph. Then $G_{spec}$ is chordal. If
$n_{1}\in\left\\{0,1\right\\}$ then $G_{spec}$ is also a block-clique graph,
which is not the case otherwise.

###### Proof.

We start out by showing that $G_{spec}$ is chordal in general. We group the
nodes of the specification graph into $S+1$ groups where the first group
$g_{0}=\left\\{1,\dots n_{1}\right\\}$ are the nodes that correspond to the
first $n_{1}$ rows of the matrix and whose internal edges are specified by the
north west entries ${\mathsf{X}}$. The second group
$g_{1}=\left\\{n_{1}+1,\dots,n_{1}+n_{2}\right\\}$ corresponds to the rows
$n_{1}+1$ to $n_{1}+n_{2}$ whose internal edges are specified by the blocks
${\mathsf{Y}}_{2,2}$ and whose external edges, connecting to neighbors outside
of $g_{1}$, are specified by ${\mathsf{Z}}_{1}$. The construction of the
remaining groups proceeds accordingly. We will now show that any cycle of
length greater 3 must have a chord. Note that all the groups are cliques since
the blocks ${\mathsf{Y}}_{i,i}$ are fully specified. Thus, a cycle of length
greater than 3 must have a chord if it is entirely contained in one of the
groups. We therefore only need to consider cycles that are not entirely
contained in one group. Also, any member of $g_{0}$ is a neighbor to any other
node in the graph since the blocks ${\mathsf{Z}}_{i},\ i\in[1\\!:\\!S]$ are
fully specified. Thus, if a vertex $v$ of $g_{0}$ is visited by a cycle, then
the edge to any other node in the cycle that is not the predecessor of $v$
gives a chord. A cycle that visits more than one group needs to visit $g_{0}$
since the other groups are not connected to one another and thus has a chord.

If $n_{1}=1$ then $g_{0}$ is a singleton. A block cannot contain just vertices
from multiple $g_{i},\ i\in[1\\!:\\!S]$ since these groups are pairwise
disconnected. A connection can only be established by adding $g_{0}$ but then
the single node in $g_{0}$ is a cut vertex, i.e. the subgraph can become
disconnected by deleting a single node and its adjacent edges. Hence, a block
of $G_{spec}$ must be a subgraph formed from the union of $g_{0}$ and one
$g_{i},i\in[1\\!:\\!S]$ and the respective edges. A subgraph formed from all
the nodes of such a union, say $T$, cannot be contained in any other block
since the construction of such a block would require to add nodes from a third
group. Thus, $T$ is a block, but it is also a clique since the $q_{i}$ is a
clique and the node in $g_{0}$ is adjacent to all the members of $g_{i}$.

If $n_{1}=0$ then $G_{spec}$ consists of $S$ subgraphs that are cliques and
pairwise disconnected, hence they are blocks.

Otherwise, the entire graph is its only block since it cannot become
disconnected by deleting a single node and its adjacent edges, but this block
is not a clique since $g_{i},\ i\in[1\\!:\\!S]$ have no inter-group edges. ∎

As a consequence of the lemma, the traditional route for sparse conic
reformulations provides little insight: If ${\mathcal{K}}_{i}$ are positive
orthants the completion theorems are not applicable since (2) lacks the proper
sparsity pattern. Also in that case, we cannot compare the $\mathcal{DNN}$
relaxations of (2) and its sparse relaxation based on (3), since the same
sparsity pattern would be required. If ${\mathcal{K}}_{i}$ are neither the
positive orthant nor the full space, we do not even have any completion
results to begin with.

Still, the present methodology allows for at least some insight into the
benefits of working with (3), namely in the form of the following performance
guarantee.

######  Theorem 5.

Let $\mathrm{val}(SDP)$ be the optimal value of problem (2) after
$\mathcal{CPP}(\mathbb{R}_{+}\times_{i=0}^{S}{\mathcal{K}}_{i})$ is replaced
by $\SS^{n_{1}+Sn_{2}+1}$ and let $\mathrm{val}(R)$ be that optimal value
after replacing the full conic constraint with the conic constraints in (3).
We have $\mathrm{val}(SDP)\leq\mathrm{val}(R)$ and the statement also holds if
we replace the cones
$\mathcal{CPP}(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\times{\mathcal{K}}_{i}),\
i\in[1\\!:\\!S]$ in (3) by any other subsets of $\SS^{n_{1}+n_{2}+1}_{+}$.

###### Proof.

Clearly, the two problems have the same objective function, so we only need to
compare the feasible sets. Let
$\left({\mathsf{X}},{\mathsf{Y}}_{1},\dots,{\mathsf{Y}}_{S},{\mathsf{Z}}_{i},\dots,{\mathsf{Z}}_{S},\mathbf{x},\mathbf{y}_{1},\dots,\mathbf{y}_{S}\right)$
be such that

$\displaystyle\begin{pmatrix}1&\mathbf{x}^{\mathsf{T}}&\mathbf{y}_{i}^{\mathsf{T}}\\\
\mathbf{x}&{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
\mathbf{y}_{i}&{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}$
$\displaystyle\in\SS^{n_{1}+n_{2}+1},\ i\in[1\\!:\\!S],$ (6)

and the linear constraints in (2) are fulfilled, i.e. we have a feasible
solution for the optimization problem defining $\mathrm{val}(R)$. All we nee
to show, is that, after setting ${\mathsf{Y}}_{i,i}={\mathsf{Y}}_{i},\
i\in[1\\!:\\!S]$, we can find ${\mathsf{Y}}_{i,j},\ i\neq j$ such that we can
construct a positive semidefinite matrix. By 1 it suffices to show that the
specification graph of the partial matrix where ${\mathsf{Y}}_{i,j},\ i\neq j$
are not specified is a chordal graph and that all fully specified principal
submatrices are positive semidefinite. So consider the partial matrix

$\displaystyle\begin{pmatrix}1&\mathbf{x}^{\mathsf{T}}&\mathbf{y}_{1}^{\mathsf{T}}&\mathbf{y}_{2}^{\mathsf{T}}&\dots&\mathbf{y}_{S-1}^{\mathsf{T}}&\mathbf{y}_{S}^{\mathsf{T}}\\\
\mathbf{x}&{\mathsf{X}}&{\mathsf{Z}}_{1}^{\mathsf{T}}&{\mathsf{Z}}_{2}^{\mathsf{T}}&\dots&{\mathsf{Z}}_{S-1}^{\mathsf{T}}&{\mathsf{Z}}_{S}^{\mathsf{T}}\\\
\mathbf{y}_{1}&{\mathsf{Z}}_{1}&{\mathsf{Y}}_{1,1}&\mathbf{*}&\dots&\mathbf{*}&\mathbf{*}\\\
\mathbf{y}_{2}&{\mathsf{Z}}_{2}&\mathbf{*}&{\mathsf{Y}}_{2,2}&\dots&\mathbf{*}&\mathbf{*}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\mathbf{y}_{S-1}&{\mathsf{Z}}_{S-1}&\mathbf{*}&\mathbf{*}&\dots&{\mathsf{Y}}_{S-1,S-1}&\mathbf{*}\\\
\mathbf{y}_{S}&{\mathsf{Z}}_{S}&\mathbf{*}&\mathbf{*}&\dots&\mathbf{*}&{\mathsf{Y}}_{S,S}\end{pmatrix}.$

Since in all but the first two columns (we use this word now referring to
literal columns in the above representation) have unspecified blocks one can
only obtain fully specified principal submatrices if one deletes all but one
of the partially specified columns and all but the respective rows (again in
the literal sense). The so obtained blocks are precisely the blocks in (6) and
are thus positive semidefinite. The chordality of the specification graph
follows from 4. This completes the proof. ∎

The theorem states that our sparse, hence low dimensional, relaxation is at
least as strong as the fully dimensional SDP-relaxation and thus gives a
theoretical performance guarantee. It also applies to relaxations of (3) such
as the $\mathcal{DNN}$-relaxation since
$\mathcal{DNN}^{n}\subseteq\SS^{n}_{+}$.

######  Remark 1.

We could have arrived at 4 by using the results in [9] who describe a
chordality-detection procedure for SDPs with chordal sparsity pattern.
However, this procedure seemed more complicated than proving chordality of
arrow-head matrices directly here. It is nonetheless important to note that
the above result is not the first of its kind, but can be obtained directly
from known results in literature. Still, to the best of our knowledge, the
context in which we use this technique is original.

######  Remark 2.

At this point we would also like to highlight a specific shortcoming of the
above completion theorems. An inattentive reading of their claims might give
the false impression that, as an example, for a partial psd-matrix to be
completable, it needs to have a chordal specification graph. This assessment
is incorrect. A partial psd-matrix ${\mathsf{M}}$ may have a specification
graph $G({\mathsf{M}})$ that is not chordal, while still being psd-
completeable. All the theorem says is that not all partial psd-matrices with
specification graph $G({\mathsf{M}})$ are psd-completable. But that does not
exclude the possibility that some still can be completed. This is significant,
since for a sparse relaxation to be exact it suffices that its optimal set
contains just one appropriately completable matrix. To additionally require
that all other feasible matrices, or more so, all matrices with the same
sparsity pattern are completable is needlessly restrictive, which explains
part of the inflexibility of the classical machinery.

##  3 An alternative approach to sparse reformulations

We have seen that the classical approach to sparse reformulations is limited
in several capacities. It is restrictive with respect to the cones
${\mathcal{K}}_{i}$ and it is inflexible with respect to the sparsity
structure, such that it is ultimately ill-equipped to tackle sparse
reformulations of (2). We therefore propose and alternative strategy, where we
provide a convex-conic reformulation of (1) based on a generalization of
$\mathcal{CPP}$ that rests on a lifting of the space of variables into a space
that is of lower dimension than required for the classical
$\mathcal{CPP}$-reformulation (2). Hence, the reformulation is already sparse,
which comes at the price of having to optimize over a new, complicated cone.
This, however, is just a new guise of an old problem in copositive
optimization, and we will meet in a, thus, familiar fashion: by providing
inner and out approximations, that provide upper and lower bounds on the
problem whose gap is hopefully small or even zero. In order to achieve this we
will first introduce some necessary concepts, that will allow us to state and
proof our main reformulation result. After that, we close this section with a
detailed description of our approach.

###  3.1 The space of connected components $\SS_{n}^{S,k}$ and the cone of
completable, completely positive, connected components $\mathcal{CMP}$

We define

$\displaystyle\SS_{n}^{S,k}$
$\displaystyle\coloneqq\left\\{\left[\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{1}^{\mathsf{T}}\\\
{\mathsf{Z}}_{1}&{\mathsf{Y}}_{1}\end{pmatrix},\dots,\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{S}^{\mathsf{T}}\\\
{\mathsf{Z}}_{S}&{\mathsf{Y}}_{S}\end{pmatrix}\right]\colon\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\in\SS^{n},\ i\in[1\\!:\\!S],\
{\mathsf{X}}\in\SS^{k}\right\\},$

i.e. the set of vectors of $S$ symmetric matrices of order $n$ connected by a
component of order $k$, which we call the space of connected components. In
order to distinguish elements of $\SS_{n}^{S,k}$ from normal matrices we use
san-serif letters braced by rectangular braces, for example
$\left[{\mathsf{A}}\right]$. Note, that $\SS_{n}^{S,k}$ is isomorphic to the
space of arrowhead matrices by the isomorphism

$\displaystyle\Gamma\colon\SS^{S,k}_{n}\rightarrow\SS^{k+Sn},\
\left[{\mathsf{A}}\right]\mapsto\Gamma\left(\left[{\mathsf{A}}\right]\right)\coloneqq\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{1}^{\mathsf{T}}&\dots&{\mathsf{Z}}_{S}\\\
{\mathsf{Z}}_{1}&{\mathsf{Y}}_{1}&\dots&{\mathsf{O}}\\\
\vdots&\vdots&\ddots&\vdots\\\
{\mathsf{Z}}_{S}&{\mathsf{O}}&\dots&{\mathsf{Y}}_{S}\end{pmatrix},$

where for the inverse we have

$\displaystyle\Gamma^{-1}\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{1}^{\mathsf{T}}&\dots&{\mathsf{Z}}_{S}\\\
{\mathsf{Z}}_{1}&{\mathsf{Y}}_{1}&\dots&{\mathsf{O}}\\\
\vdots&\vdots&\ddots&\vdots\\\
{\mathsf{Z}}_{S}&{\mathsf{O}}&\dots&{\mathsf{Y}}_{S}\end{pmatrix}=\left[\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{1}^{\mathsf{T}}\\\
{\mathsf{Z}}_{1}&{\mathsf{Y}}_{1}\end{pmatrix},\dots,\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{S}^{\mathsf{T}}\\\
{\mathsf{Z}}_{S}&{\mathsf{Y}}_{S}\end{pmatrix}\right]\in\SS^{S,k}_{n}.$

Thus, $\SS_{n}^{S,k}$ is a vector space with a natural inner product
$\left[{\mathsf{A}}\right]\odot\left[{\mathsf{B}}\right]\coloneqq\Gamma\left(\left[{\mathsf{A}}\right]\right)\bullet\Gamma\left(\left[{\mathsf{A}}\right]\right)$,
sum
$\left[{\mathsf{A}}\right]\oplus\left[{\mathsf{B}}\right]\coloneqq\Gamma\left(\left[{\mathsf{A}}\right]\right)+\Gamma\left(\left[{\mathsf{A}}\right]\right)$
and scalar multiplication
$\lambda\left[{\mathsf{A}}\right]\coloneqq\Gamma^{-1}\left(\lambda\Gamma\left(\left[{\mathsf{A}}\right]\right)\right)$.
For notational convenience we will expand the meaning of the inverse
$\Gamma^{-1}$ so that it is applicable to non-arrowhead matrices as well,
where the nonzero off-diagonal blocks are treated as though they were blocks
of zeros as in the definition above. Also, we define a second, analogous
isomorphism $\Gamma_{*}(\cdot)$ that maps into the space of partial matrices
where the blocks of zeros in the definition of $\Gamma(\cdot)$ are not
specified. We also will use the shorthand notation

$\displaystyle\left[\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{1}^{\mathsf{T}}\\\
{\mathsf{Z}}_{1}&{\mathsf{Y}}_{1}\end{pmatrix},\dots,\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{S}^{\mathsf{T}}\\\
{\mathsf{Z}}_{S}&{\mathsf{Y}}_{S}\end{pmatrix}\right]=\left[\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\right]_{i\in[1\\!:\\!S]}.$

The central object we are interested in is the following subset of
$\SS_{n}^{S,k}$:

$\displaystyle\mathcal{CMP}\left({\mathcal{K}}_{0},\dots,{\mathcal{K}}_{S}\right)$
$\displaystyle\coloneqq\mathrm{conv}\left\\{\left[\begin{pmatrix}\mathbf{x}\\\
\mathbf{y}_{i}\end{pmatrix}\begin{pmatrix}\mathbf{x}\\\
\mathbf{y}_{i}\end{pmatrix}^{\mathsf{T}}\right]_{i\in[1\\!:\\!S]}\colon\begin{pmatrix}\mathbf{x}\\\
\mathbf{y}_{i}\end{pmatrix}\in{\mathcal{K}}_{0}\times{\mathcal{K}}_{i},\
i\in[1\\!:\\!S]\right\\},$

where ${\mathcal{K}}_{0}\subseteq\mathbb{R}^{k},\
{\mathcal{K}}_{i}\subseteq\mathbb{R}^{n-k},\ i\in[1\\!:\\!S]$ are convex
cones, which we refer to as ground cones. We often use $\mathcal{CMP}$ without
its arguments as a colloquial term, in case the respective ground cones are
not important to, or clear from, the context at hand. The same is true for all
abbreviations of its inner and outer approximations that will be discussed
later in the text.

We call $\mathcal{CMP}$ the cone of completable, completely positive,
connected components and we will justify that name in a latter section.
Further, we define $\mathrm{gen}\mathcal{CMP}$ to be the set of its
generators, i.e. the set we obtain by omitting the
$\operatorname{conv}$-operator in the definition of $\mathcal{CMP}$.

###  3.2 Main result: a new type of convex reformulation, with reduced
dimensionality

The deriviation of our main result relies heavily on the very general
framework from [11], for achieving convex reformulations for a large array of
problems. In the following paragraphs we will give a small and simplified
account of their results in order to make the derivation of our main result as
transparent as possible. The two theorems we discuss shortly are
specializations of theorems in [11], which we prove here for the readers
convenience. To distinguish this more abstract discussion from the rest of the
paper, and to highlight the special role of the sets we are about to
introduce, we diverge from the convention of denoting sets via calligraphic
capital letters and use blackboard bold capital letters.

We start out be investigating a more general question. So, let $\mathbb{V}$ be
a vector space of dimension $n$. For a (possibly nonconvex) cone
$\mathbb{K}\subseteq\mathbb{V}$, and vectors
${\mathsf{Q}},{\mathsf{H}}_{0}\in\mathbb{V}$ and a convex set
$\mathbb{J}\subseteq\mathrm{conv}(\mathbb{K})$. We want to know when we have
the equality:

$\displaystyle\min_{{\mathsf{X}}\in\mathbb{V}}\left\\{\langle{\mathsf{Q}},{\mathsf{X}}\rangle\colon{\mathsf{X}}\in\mathbb{K}\cap\mathbb{J},\
\langle{\mathsf{H}}_{0},{\mathsf{X}}\rangle=1\right\\}=\min_{{\mathsf{X}}\in\mathbb{V}}\left\\{\langle{\mathsf{Q}},{\mathsf{X}}\rangle\colon{\mathsf{X}}\in\mathbb{J},\
\langle{\mathsf{H}}_{0},{\mathsf{X}}\rangle=1\right\\}?$

Defining
$\mathbb{H}\coloneqq\left\\{{\mathsf{X}}\colon\langle{\mathsf{H}}_{0},{\mathsf{X}}\rangle=1\right\\}$,
we can equivalently ask for conditions for the equality

$\displaystyle\mathrm{conv}(\mathbb{H}\cap\mathbb{K}\cap\mathbb{J})=\mathbb{H}\cap\mathbb{J}.$

The following theorem gives an answer based on convex geometry.

######  Theorem 6.

For $\mathbb{H},\mathbb{K},\mathbb{J}$ as above, assume that
$\mathbb{H}\cap\mathbb{J}\neq\emptyset$ is bounded and that $\mathbb{J}$ is a
face of $\mathrm{conv}(\mathbb{K})$. Then
$\mathrm{conv}(\mathbb{H}\cap\mathbb{K}\cap\mathbb{J})=\mathbb{H}\cap\mathbb{J}$.

###### Proof.

For the "$\subseteq$"-inclusion, since
$\mathbb{H}\cap\mathbb{K}\cap\mathbb{J}\subseteq\mathbb{H}\cap\mathbb{J}$ and
the latter set is convex, there is nothing left to show. For the converse, let
${\mathsf{X}}\in\mathbb{H}\cap\mathbb{J}$. Then
${\mathsf{X}}\in\mathrm{conv}(\mathbb{K})$ since
$\mathbb{J}\subseteq\mathrm{conv}(\mathbb{K})$, so that
${\mathsf{X}}=\sum_{i=1}^{n}{\mathsf{X}}_{i}$ with
${\mathsf{X}}_{i}\in\mathbb{K}\setminus\left\\{{\mathsf{O}}\right\\}$ but also
${\mathsf{X}}_{i}\in\mathbb{J}$ since $\mathbb{J}$ is a face of
$\mathrm{conv}(\mathbb{K})$ so that
${\mathsf{X}}_{i}\in\mathbb{K}\cap\mathbb{J}$. Now,
$\langle{\mathsf{H}}_{0},{\mathsf{X}}_{i}\rangle>0$ since
$\mathbb{H}\cap\mathbb{J}\neq\emptyset$ is bounded. Define
$\lambda_{i}=\langle{\mathsf{H}}_{0},{\mathsf{X}}_{i}\rangle.$ We have
$\langle{\mathsf{H}}_{0},{\mathsf{X}}\rangle=\sum_{i}\langle{\mathsf{H}}_{0},{\mathsf{X}}_{i}\rangle=\sum_{i}\lambda_{i}=1$
and
$\lambda_{i}^{-1}{\mathsf{X}}_{i}\eqqcolon\bar{\mathsf{X}}_{i}\in\mathbb{K}\cap\mathbb{J}$
and thus
${\mathsf{X}}=\sum_{i}\lambda_{i}\bar{\mathsf{X}}_{i}\in\mathrm{conv}(\mathbb{H}\cap\mathbb{K}\cap\mathbb{J})$.
∎

This theorem motivates the search for a condition that lets us identify faces
of convex cones, which are provided in the following theorem.

######  Theorem 7.

Assume that
$\mathbb{J}=\left\\{{\mathsf{X}}\in\mathrm{conv}(\mathbb{K})\colon\langle{\mathsf{A}}_{i},{\mathsf{X}}\rangle=0,\
i\in[1\\!:\\!m]\right\\}$ and define
$\mathbb{J}_{p}\coloneqq\left\\{{\mathsf{X}}\in\mathrm{conv}(\mathbb{K})\colon\langle{\mathsf{A}}_{i},{\mathsf{X}}\rangle=0,\
i\in[1\\!:\\!p]\right\\}$ so that $\mathbb{J}_{m}=\mathbb{J}$ and
$\mathbb{J}_{0}=\mathrm{conv}(\mathbb{K})$. If
${\mathsf{A}}_{p}\in\mathbb{J}_{p-1}^{*},i\in[1\\!:\\!m]$ then $\mathbb{J}$ is
a face of $\mathrm{conv}(\mathbb{K})$.

###### Proof.

Since a face of a face a convex set is itself a face of that set, the claim
will follow by induction if we can show that

${\mathsf{A}}_{p}\in\mathbb{J}_{p-1}^{*}\implies\mathbb{J}_{p}\mbox{ is a face
of }\mathbb{J}_{p-1}.$

So let $\mathbb{J}_{p}\ni{\mathsf{X}}={\mathsf{X}}_{1}+{\mathsf{X}}_{2}$ with
${\mathsf{X}}_{i}\in\mathbb{J}_{p-1},\ i\in\left\\{1,2\right\\}$. We have
$\langle{\mathsf{A}}_{p},{\mathsf{X}}_{i}\rangle\geq 0$ since
${\mathsf{A}}_{p}\in\mathbb{J}_{p-1}^{*}$ so that
$0=\langle{\mathsf{A}}_{p},{\mathsf{X}}\rangle=\langle{\mathsf{A}}_{p},{\mathsf{X}}_{1}\rangle+\langle{\mathsf{A}}_{p},{\mathsf{X}}_{2}\rangle$
implies that actually $\langle{\mathsf{A}}_{p},{\mathsf{X}}_{i}\rangle=0$ and
we indeed have ${\mathsf{X}}_{i}\in\mathbb{J}_{p},\ i\in\left\\{1,2\right\\}$.
∎

Based on the above theorems, it is quite straight forward to prove the
classical result from [4], at least for the case where the linear portion of
the set is bounded, with
$\mathbb{K}=\mathrm{ext}\mathcal{CPP}(\mathbb{R}_{+}\times{\mathcal{K}})$ and
$\mathbb{J}$ equal to the feasible set of the conic reformulation (we omit
laying out the details here, but the steps required are equivalent to the ones
laid out in the proof of 8). A natural question is, whether we can execute a
similar strategy for proving the exactness of a conic reformulation of reduced
dimension by replacing the cone of extreme rays of
$\mathcal{CPP}({\mathcal{K}})$ with another appropriately structured object as
our choice for $\mathbb{K}$.

In the following theorem we show that by choosing
$\mathbb{K}=\mathrm{gen}\mathcal{CMP}\left(\left(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\right),{\mathcal{K}}_{1},\dots,{\mathcal{K}}_{S}\right)$
and $\mathbb{J}$ and $\mathbb{H}$ appropriately we can use 6 in order to
obtain an exact conic reformulation of (1).

######  Theorem 8.

Considering (1), assume
${\mathcal{F}}_{i}~{}\coloneqq~{}\left\\{\left(\mathbf{x}^{\mathsf{T}},\mathbf{y}_{i}^{\mathsf{T}}\right)\in{\mathcal{K}}_{0}\times{\mathcal{K}}_{i}\colon{\mathsf{F}}_{i}\mathbf{x}+{\mathsf{G}}_{i}\mathbf{y}_{i}={\mathbf{r}}_{i}\right\\}$
are nonempty bounded sets. Further, assume that

$\displaystyle\begin{pmatrix}\mathbf{x},\mathbf{y}_{i}\end{pmatrix}\in{\mathcal{F}}_{i},\
i\in[1\\!:\\!S]\implies
Q_{j}(\mathbf{x},\mathbf{y}_{1},\dots,\mathbf{y}_{S})\geq 0,\
j\in[1\\!:\\!K].$ (7)

Then (1) is equivalent to the following conic optimization problem:

$\displaystyle\begin{split}\min_{[{\mathsf{X}}]\in\SS_{n_{1}+n_{2}+1}^{S,n_{1}+1}}[{\mathsf{C}}]\odot[{\mathsf{X}}]&\\\
\mathrm{s.t.:}\ [{\mathsf{H}}_{0}]\odot[{\mathsf{X}}]&=1,\\\
[{\mathsf{F}}_{i}]\odot[{\mathsf{X}}]&=0,\ i\in[1\\!:\\!S],\\\
\hat{Q}_{j}\left([{\mathsf{X}}]\right)&=0,\ j\in[1\\!:\\!K],\\\
[{\mathsf{X}}]&\in\mathcal{CMP}\left(\left(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\right),{\mathcal{K}}_{1},\dots,{\mathcal{K}}_{S}\right),\end{split}$
(8)

where
$[{\mathsf{C}}],[{\mathsf{H}}_{0}],[{\mathsf{F}}_{i}]\in\SS_{n_{1}+n_{2}+1}^{S,n_{1}+1},\
i\in[1\\!:\\!S]$ are defined as

$\displaystyle[{\mathsf{C}}]$
$\displaystyle\coloneqq\Gamma^{-1}\begin{pmatrix}0&\tfrac{1}{2}\mathbf{a}^{\mathsf{T}}&\tfrac{1}{2}\mathbf{c}_{1}^{\mathsf{T}}&\dots&\tfrac{1}{2}\mathbf{c}_{S}^{\mathsf{T}}\\\
\tfrac{1}{2}\mathbf{a}&{\mathsf{A}}&\tfrac{1}{2}{\mathsf{B}}_{1}&\dots&\tfrac{1}{2}{\mathsf{B}}_{S}\\\
\tfrac{1}{2}\mathbf{c}_{1}^{\mathsf{T}}&\tfrac{1}{2}{\mathsf{B}}_{1}^{\mathsf{T}}&{\mathsf{C}}_{1}&\dots&{\mathsf{O}}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
\tfrac{1}{2}\mathbf{c}_{S}^{\mathsf{T}}&\tfrac{1}{2}{\mathsf{B}}_{S}^{\mathsf{T}}&{\mathsf{O}}&\dots&{\mathsf{C}}_{S}\end{pmatrix},\quad[{\mathsf{H}}_{0}]=\Gamma^{-1}\left(\mathbf{e}_{1}\mathbf{e}_{1}^{\mathsf{T}}\right),$
$\displaystyle[{\mathsf{F}}_{i}]$
$\displaystyle\coloneqq\Gamma^{-1}\left(\left(-{\mathbf{r}}_{i},{\mathsf{F}}_{i},{\mathsf{O}},\dots,{\mathsf{G}}_{i},\dots,{\mathsf{O}}\right)^{\mathsf{T}}\left(-{\mathbf{r}}_{i},{\mathsf{F}}_{i},{\mathsf{O}},\dots,{\mathsf{G}}_{i},\dots,{\mathsf{O}}\right)\right).$

and
$\hat{Q}_{j}(\cdot)\colon\SS^{S,n_{1}+1}_{n_{1}+n_{2}+1}\rightarrow\mathbb{R}$
are linear functions such that

$\displaystyle\hat{Q}_{j}\left(\Gamma^{-1}\left(\begin{pmatrix}x_{0}\\\
\mathbf{x}\\\ \mathbf{y}_{1}\\\ \vdots\\\
\mathbf{y}_{S}\end{pmatrix}\begin{pmatrix}x_{0}\\\ \mathbf{x}\\\
\mathbf{y}_{1}\\\ \vdots\\\
\mathbf{y}_{S}\end{pmatrix}^{\mathsf{T}}\right)\right)=Q_{j}(\mathbf{x},\mathbf{y}_{1},\dots,\mathbf{y}_{S}),\
j\in[1\\!:\\!K]$

###### Proof.

Consider the following equivalences

$\displaystyle{\mathsf{F}}_{i}\mathbf{x}+{\mathsf{G}}_{i}\mathbf{y}_{i}$
$\displaystyle={\mathbf{r}}_{i},\ \mathbf{y}\in{\mathcal{K}}_{i},\
i\in[1\\!:\\!S],\ \mathbf{x}\in{\mathcal{K}}_{0},$ $\displaystyle
Q_{j}(\mathbf{x},\mathbf{y}_{1},\dots,\mathbf{y}_{S})$ $\displaystyle=0,\
j\in[1\\!:\\!K],$ $\displaystyle\Updownarrow$
$\displaystyle\begin{Vmatrix}\left(-{\mathbf{r}}_{i},{\mathsf{F}}_{i},{\mathsf{O}},\dots,{\mathsf{G}}_{i},\dots,{\mathsf{O}}\right)\begin{pmatrix}x_{0}\\\
\mathbf{x}\\\ \mathbf{y}_{1}\\\ \vdots\\\
\mathbf{y}_{S}\end{pmatrix}\end{Vmatrix}^{2}$ $\displaystyle=0,\
\mathbf{y}\in{\mathcal{K}}_{i},\ i\in[1\\!:\\!S],\
\mathbf{x}\in{\mathcal{K}}_{0},\ x_{0}\geq 0,\ x_{0}^{2}=1,$ $\displaystyle
Q_{j}(\mathbf{x},\mathbf{y}_{1},\dots,\mathbf{y}_{S})$ $\displaystyle=0,\
j\in[1\\!:\\!K],$ $\displaystyle\Updownarrow$
$\displaystyle[{\mathsf{X}}]=\Gamma^{-1}\left(\begin{pmatrix}x_{0}\\\
\mathbf{x}\\\ \mathbf{y}_{1}\\\ \vdots\\\
\mathbf{y}_{S}\end{pmatrix}\begin{pmatrix}x_{0}\\\ \mathbf{x}\\\
\mathbf{y}_{1}\\\ \vdots\\\ \mathbf{y}_{S}\end{pmatrix}^{\mathsf{T}}\right),\
[{\mathsf{F}}_{i}]\odot[{\mathsf{X}}]$ $\displaystyle=0,\
\mathbf{y}\in{\mathcal{K}}_{i},\ i\in[1\\!:\\!S],\
\mathbf{x}\in{\mathcal{K}}_{0},\ x_{0}\geq 0,\ x_{0}^{2}=1,$
$\displaystyle\hat{Q}_{j}([{\mathsf{X}}])$ $\displaystyle=0\ j\in[1\\!:\\!K]$
$\displaystyle\Updownarrow$
$\displaystyle[{\mathsf{H}}_{0}]\odot[{\mathsf{X}}]$ $\displaystyle=1,$
$\displaystyle[{\mathsf{F}}_{i}]\odot[{\mathsf{X}}]$ $\displaystyle=0,\
i\in[1\\!:\\!S],$ $\displaystyle\hat{Q}_{j}([{\mathsf{X}}])$ $\displaystyle=0\
j\in[1\\!:\\!K],$ $\displaystyle[{\mathsf{X}}]$
$\displaystyle\in\mathrm{gen}\mathcal{CMP}\left(\left(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\right),{\mathcal{K}}_{1},\dots,{\mathcal{K}}_{S}\right).$

Invoking 6, we specify

$\displaystyle\mathbb{K}$
$\displaystyle=\mathrm{gen}\mathcal{CMP}\left(\left(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\right),{\mathcal{K}}_{1},\dots,{\mathcal{K}}_{S}\right),$
$\displaystyle\mathbb{H}$
$\displaystyle=\left\\{[{\mathsf{X}}]\in\SS_{n_{1}+n_{2}+1}^{S,n_{1}+1}\colon[{\mathsf{H}}_{0}]\odot[{\mathsf{X}}]=1\right\\},$

and we need to show is that

$\displaystyle\mathbb{J}$
$\displaystyle=\left\\{[{\mathsf{X}}]\in\mathcal{CMP}\left(\left(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\right),{\mathcal{K}}_{1},\dots,{\mathcal{K}}_{S}\right)\colon\begin{array}[]{l}[{\mathsf{F}}_{i}]\odot[{\mathsf{X}}]=0,\
i\in[1\\!:\\!S]\\\ \hat{Q}_{j}\left([{\mathsf{X}}]\right)=0,\
j\in[1\\!:\\!K]\end{array}\right\\},$

is a face of
$\mathcal{CMP}\left(\left(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\right),{\mathcal{K}}_{1},\dots,{\mathcal{K}}_{S}\right)$.
By 7, this will follow if we can show that
$[{\mathsf{F}}_{i}]\odot[{\mathsf{X}}]\geq 0,\
\forall[{\mathsf{X}}]\in\mathcal{CMP}\left(\left(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\right),{\mathcal{K}}_{1},\dots,{\mathcal{K}}_{S}\right),\
i\in[1\\!:\\!S]$ and that $\hat{Q}_{j}([{\mathsf{X}}])\geq 0,\
j\in[1\\!:\\!K]$ whenever $[{\mathsf{X}}]$ fulfills the homogeneous and conic
constraints in the description of the feasible set of the conic optimization
problem. We will first show, that the statement of the theorem held if the
quadratic constraints were omitted. Indeed for any of the $[{\mathsf{F}}_{i}]$
and any
$[{\mathsf{X}}]\in\mathrm{gen}\mathcal{CMP}\left(\left(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\right),{\mathcal{K}}_{1},\dots,{\mathcal{K}}_{S}\right)$
we have

$\displaystyle\begin{split}[{\mathsf{F}}_{i}]\odot[{\mathsf{X}}]=&\left(\left(-{\mathbf{r}}_{i},{\mathsf{F}}_{i},\dots,{\mathsf{G}}_{i},\dots\right)^{\mathsf{T}}\left(-{\mathbf{r}}_{i},{\mathsf{F}}_{i},\dots,{\mathsf{G}}_{i},\dots\right)\right)\bullet\begin{pmatrix}\mathbf{x}\mathbf{x}^{\mathsf{T}}&\mathbf{x}\mathbf{y}_{1}^{\mathsf{T}}&\dots&\mathbf{x}\mathbf{y}_{S}^{\mathsf{T}}\\\
\mathbf{y}_{1}\mathbf{x}^{\mathsf{T}}&\mathbf{y}_{1}\mathbf{y}_{1}^{\mathsf{T}}&\dots&{\mathsf{O}}\\\
\vdots&\vdots&\ddots&\vdots\\\
\mathbf{y}_{S}\mathbf{x}^{\mathsf{T}}&{\mathsf{O}}&\dots&\mathbf{y}_{S}\mathbf{y}_{S}^{\mathsf{T}}\end{pmatrix}\\\
=&\begin{pmatrix}-{\mathbf{r}}_{i},{\mathsf{F}}_{i},{\mathsf{G}}_{i}\end{pmatrix}^{\mathsf{T}}\begin{pmatrix}-{\mathbf{r}}_{i},{\mathsf{F}}_{i},{\mathsf{G}}_{i}\end{pmatrix}\bullet\begin{pmatrix}\mathbf{x}\mathbf{x}^{\mathsf{T}}&\mathbf{x}\mathbf{y}_{i}^{\mathsf{T}}\\\
\mathbf{y}_{i}\mathbf{x}^{\mathsf{T}}&\mathbf{y}_{i}\mathbf{y}_{i}^{\mathsf{T}}\end{pmatrix}\\\
=&\begin{Vmatrix}\begin{pmatrix}-{\mathbf{r}}_{i},{\mathsf{F}}_{i},{\mathsf{G}}_{i}\end{pmatrix}\begin{pmatrix}\mathbf{x}\\\
\mathbf{y}_{i}\end{pmatrix}\end{Vmatrix}^{2}\geq 0.\end{split}$

To complete the first part of the argument we need to show that the feasible
set is bounded. To this end we consider its recession cone which by
[rockafellar2015convex, Corollary 8.3.3.] is given by

$\displaystyle
0^{+}{\mathcal{F}}\coloneqq\left\\{[{\mathsf{X}}]\in\mathcal{CMP}\left(\left(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\right),{\mathcal{K}}_{1},\dots,{\mathcal{K}}_{S}\right)\colon[{\mathsf{H}}_{0}]\odot[{\mathsf{X}}]=0,\
[{\mathsf{F}}_{i}]\odot[{\mathsf{X}}]=0,\ i\in[1\\!:\\!S]\right\\}.$

Take an arbitrary $\left[{\mathsf{X}}\right]\in 0^{+}{\mathcal{F}}$, then

$\displaystyle\left[{\mathsf{F}}_{i}\right]\odot\left[{\mathsf{X}}\right]$
$\displaystyle=\sum_{l=1}^{k}\lambda_{l}\begin{Vmatrix}\begin{pmatrix}-{\mathbf{r}}_{i},{\mathsf{F}}_{i},{\mathsf{G}}_{i}\end{pmatrix}\begin{pmatrix}x^{0}_{l}\\\
\mathbf{x}_{l}\\\ \mathbf{y}^{i}_{l}\end{pmatrix}\end{Vmatrix}^{2}=0,\
i\in[1\\!:\\!S]\mbox{ and }$
$\displaystyle\left[{\mathsf{H}}_{0}\right]\odot\left[{\mathsf{X}}\right]$
$\displaystyle=\sum_{l=1}^{k}\left(x^{0}_{l}\right)^{2}=0,\mbox{ implying that
}x^{0}_{l}=0,\ l\in[1\\!:\\!k].$

Thus, for any $i\in[1\\!:\\!S]$ and $l\in[1\\!:\\!k]$ we have
${\mathsf{F}}_{i}\mathbf{x}_{l}+{\mathsf{G}}_{i}\mathbf{y}^{i}_{l}=\mathbf{o}$
and
$\left(0,\mathbf{x}_{l},\mathbf{y}^{i}_{l}\right)\in\mathbb{R}_{+}\times{\mathcal{K}}_{0}\times{\mathcal{K}}_{i}$
so that we have a element of the recession cone of ${\mathcal{F}}_{i}$, which
only contains the origin by the boundedness assumption, so that
$\left[{\mathsf{X}}\right]=\left[{\mathsf{O}}\right]$. So far our arguments
imply that

$\displaystyle\hat{\mathbb{J}}\coloneqq\left\\{[{\mathsf{X}}]\in\mathcal{CMP}\left(\left(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\right),{\mathcal{K}}_{1},\dots,{\mathcal{K}}_{S}\right)\colon[{\mathsf{F}}_{i}]\odot[{\mathsf{X}}]=0,\
i\in[1\\!:\\!S]\right\\}$

is a face of $\mathbb{K}$, hence its extreme points correspond to extreme rays
of $\mathbb{K}$ by 6, that is
$\mathrm{gen}\mathcal{CMP}\left(\left(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\right),{\mathcal{K}}_{1},\dots,{\mathcal{K}}_{S}\right)$.
But then (7) implies that $\hat{Q}_{j}([{\mathsf{X}}])\geq 0,\
j\in[1\\!:\\!K]$ whenever $[{\mathsf{X}}]\in\hat{\mathbb{J}}$ so that by 7 the
set $\mathbb{J}$ is a face of $\mathbb{K}$ and our theorem follows from 6. ∎

While the above representation of the conic problem is convenient for the
application of Theorems 6 and 7 and the statement of the proof, we can use [5,
Proposition 3] in order to present it in a more familiar form:

$\displaystyle\begin{split}\min_{{\mathsf{X}},{\mathsf{Y}}_{i},{\mathsf{Z}}_{i},\mathbf{x},\mathbf{y}_{i}}{\mathsf{A}}_{i}\bullet{\mathsf{X}}+\mathbf{a}^{\mathsf{T}}\mathbf{x}&+\sum_{i=1}^{S}{\mathsf{B}}_{i}\bullet{\mathsf{Z}}_{i}+{\mathsf{C}}_{i}\bullet{\mathsf{Y}}_{i,i}+\mathbf{c}_{i}^{\mathsf{T}}\mathbf{y}\\\
\mathrm{s.t.:}\
{\mathsf{F}}_{i}\mathbf{x}+{\mathsf{G}}_{i}\mathbf{y}_{i}&={\mathbf{r}}_{i},\quad\hskip
19.91684pti\in[1\\!:\\!S],\\\
\operatorname{diag}\left(\begin{pmatrix}{\mathsf{F}}_{i}&{\mathsf{G}}_{i}\end{pmatrix}\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\begin{pmatrix}{\mathsf{F}}_{i}^{\mathsf{T}}\\\
{\mathsf{G}}_{i}^{\mathsf{T}}\end{pmatrix}\right)&={\mathbf{r}}_{i}\circ{\mathbf{r}}_{i},\quad
i\in[1\\!:\\!S],\\\
\hat{Q}_{j}(\mathbf{x},{\mathsf{X}},\mathbf{y}_{1},{\mathsf{Z}}_{1},{\mathsf{Y}}_{1},\dots,\mathbf{y}_{S},{\mathsf{Z}}_{S},{\mathsf{Y}}_{S})&=0,\quad\hskip
17.07182pt\ j\in[1\\!:\\!K],\\\
\left[\begin{pmatrix}1&\mathbf{x}^{\mathsf{T}}&\mathbf{y}_{i}^{\mathsf{T}}\\\
\mathbf{x}&{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
\mathbf{y}_{i}&{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\right]_{i\in[1\\!:\\!S]}&\in\mathcal{CMP}\left(\left(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\right),{\mathcal{K}}_{1},\dots,{\mathcal{K}}_{S}\right).\end{split}$
(9)

Before discussing this new type of conic reformulation, we want to point out,
that there is a another way to prove 8. First, we make the following
observation:

######  Theorem 9.

The partial matrix

$\displaystyle{\mathsf{M}}_{*}\coloneqq\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{1}^{\mathsf{T}}&\dots&{\mathsf{Z}}_{S}\\\
{\mathsf{Z}}_{1}&{\mathsf{Y}}_{1}&\dots&*\\\ \vdots&\vdots&\ddots&\vdots\\\
{\mathsf{Z}}_{S}&*&\dots&{\mathsf{Y}}_{S}\end{pmatrix},$

is completable to a matrix in
$\mathcal{CPP}({\mathcal{K}}_{0}\times_{i=1}^{S}{\mathcal{K}}_{i})$ if and
only if there are decompositions

$\displaystyle\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}=\begin{pmatrix}\bar{{\mathsf{X}}}\bar{{\mathsf{X}}}^{\mathsf{T}}&\bar{{\mathsf{X}}}\bar{{\mathsf{Y}}}_{i}^{\mathsf{T}}\\\
\bar{{\mathsf{Y}}}_{i}\bar{{\mathsf{X}}}^{\mathsf{T}}&\bar{{\mathsf{Y}}}_{i}\bar{{\mathsf{Y}}}_{i}^{\mathsf{T}}\end{pmatrix},\mbox{
with }\begin{pmatrix}\bar{{\mathsf{X}}}\\\
\bar{{\mathsf{Y}}}_{i}\end{pmatrix}\in{\mathcal{K}}_{0}^{r}\times{\mathcal{K}}_{i}^{r},\
i\in[1\\!:\\!S],\ r\in\mathbb{N},$

hence, if and only if

$\displaystyle\left[\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\right]_{i\in[1\\!:\\!S]}$
$\displaystyle\in\mathcal{CMP}\left(\left(\mathbb{R}_{+}\times{\mathcal{K}}_{0}\right),{\mathcal{K}}_{1},\dots,{\mathcal{K}}_{S}\right).$

###### Proof.

Given said decompositions we can create a matrix

$\displaystyle\begin{pmatrix}\bar{{\mathsf{X}}}\\\ \bar{{\mathsf{Y}}}_{1}\\\
\vdots\\\ \bar{{\mathsf{Y}}}_{S}\end{pmatrix}\mbox{ for which
}\begin{pmatrix}\bar{{\mathsf{X}}}\\\ \bar{{\mathsf{Y}}}_{1}\\\ \vdots\\\
\bar{{\mathsf{Y}}}_{S}\end{pmatrix}\begin{pmatrix}\bar{{\mathsf{X}}}\\\
\bar{{\mathsf{Y}}}_{1}\\\ \vdots\\\
\bar{{\mathsf{Y}}}_{S}\end{pmatrix}^{\mathsf{T}}=\begin{pmatrix}\bar{{\mathsf{X}}}\bar{{\mathsf{X}}}^{\mathsf{T}}&\bar{{\mathsf{X}}}\bar{{\mathsf{Y}}}_{1}^{\mathsf{T}}&\dots&\bar{{\mathsf{X}}}\bar{{\mathsf{Y}}}_{S}^{\mathsf{T}}\\\
\bar{{\mathsf{Y}}}_{1}\bar{{\mathsf{X}}}^{\mathsf{T}}&\bar{{\mathsf{Y}}}_{1}\bar{{\mathsf{Y}}}_{1}^{\mathsf{T}}&\dots&\bar{{\mathsf{Y}}}_{1}\bar{{\mathsf{Y}}}_{S}^{\mathsf{T}}\\\
\vdots&\vdots&\ddots&\vdots\\\
{\mathsf{Y}}_{S}\bar{{\mathsf{X}}}^{\mathsf{T}}&\bar{{\mathsf{Y}}}_{S}\bar{{\mathsf{Y}}}_{1}^{\mathsf{T}}&\dots&\bar{{\mathsf{Y}}}_{S}\bar{{\mathsf{Y}}}_{S}^{\mathsf{T}}\end{pmatrix}\in\mathcal{CPP}(\times_{i=0}^{S}{\mathcal{K}}_{i}),$

is the desired completion of ${\mathsf{M}}_{*}$. Conversely, if
${\mathsf{M}}_{*}$ has a completion ${\mathsf{M}}\in\
\mathcal{CPP}(\times_{i=0}^{S}{\mathcal{K}}_{i})$ then by definition of the
latter cone we have

$\displaystyle{\mathsf{M}}=\begin{pmatrix}\bar{{\mathsf{X}}}\bar{{\mathsf{X}}}^{\mathsf{T}}&\bar{{\mathsf{X}}}\bar{{\mathsf{Y}}}_{1}^{\mathsf{T}}&\dots&\bar{{\mathsf{X}}}\bar{{\mathsf{Y}}}_{S}^{\mathsf{T}}\\\
\bar{{\mathsf{Y}}}_{1}\bar{{\mathsf{X}}}^{\mathsf{T}}&\bar{{\mathsf{Y}}}_{1}\bar{{\mathsf{Y}}}_{1}^{\mathsf{T}}&\dots&\bar{{\mathsf{Y}}}_{1}\bar{{\mathsf{Y}}}_{S}^{\mathsf{T}}\\\
\vdots&\vdots&\ddots&\vdots\\\
{\mathsf{Y}}_{S}\bar{{\mathsf{X}}}^{\mathsf{T}}&\bar{{\mathsf{Y}}}_{S}\bar{{\mathsf{Y}}}_{1}^{\mathsf{T}}&\dots&\bar{{\mathsf{Y}}}_{S}\bar{{\mathsf{Y}}}_{S}^{\mathsf{T}}\end{pmatrix},$

so that

$\displaystyle\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}=\begin{pmatrix}\bar{{\mathsf{X}}}\bar{{\mathsf{X}}}^{\mathsf{T}}&\bar{{\mathsf{X}}}\bar{{\mathsf{Y}}}_{i}^{\mathsf{T}}\\\
\bar{{\mathsf{Y}}}_{i}\bar{{\mathsf{X}}}^{\mathsf{T}}&\bar{{\mathsf{Y}}}_{i}\bar{{\mathsf{Y}}}_{i}^{\mathsf{T}}\end{pmatrix},\mbox{
with }\begin{pmatrix}\bar{{\mathsf{X}}}\\\
\bar{{\mathsf{Y}}}_{i}\end{pmatrix}\left({\mathcal{K}}_{0}\times{\mathcal{K}}_{i}\right)^{r},\
i\in[1\\!:\\!S],\ r\in\mathbb{N}.$

∎

######  Remark 3.

The lemma is easily derived, but it highlights the key difficulty for the
construction of a completion of the arrow-head arrangement of a set of matrix
blocks connected by a common submatrix ${\mathsf{X}}$. If all of the blocks
have representations as convex-conic combinations (i.e. nonnegative linear
combinations) where the parts of the representations that form the connecting
${\mathsf{X}}$-component are identical for all blocks, obtaining the
completion is simply a matter of concatenating the individual factors of the
decompositions. However, there is no guarantee that decompositions that are
coordinated in this manner do exist.

Now, it is clear that the following optimization problem is equivalent to (2):

$\displaystyle\begin{split}\min_{{\mathsf{X}},{\mathsf{Y}}_{i},{\mathsf{Z}}_{i},\mathbf{x},\mathbf{y}_{i}}&{\mathsf{A}}_{i}\bullet{\mathsf{X}}+\mathbf{a}^{\mathsf{T}}\mathbf{x}+\sum_{i=1}^{S}{\mathsf{B}}_{i}\bullet{\mathsf{Z}}_{i}+{\mathsf{C}}_{i}\bullet{\mathsf{Y}}_{i,i}+\mathbf{c}_{i}^{\mathsf{T}}\mathbf{y}\\\
\mathrm{s.t.:}\ &\mbox{ the linear constraints of
(\ref{eqn:DecomposableQCQPBurer}) hold and }\\\
&\begin{pmatrix}1&\mathbf{x}^{\mathsf{T}}&\mathbf{y}_{1}^{\mathsf{T}}&\dots&\mathbf{y}_{S}^{\mathsf{T}}\\\
\mathbf{x}&{\mathsf{X}}&{\mathsf{Z}}_{1}^{\mathsf{T}}&\dots&{\mathsf{Z}}_{S}^{\mathsf{T}}\\\
\mathbf{y}_{1}&{\mathsf{Z}}_{1}&{\mathsf{Y}}_{1,1}&\dots&*\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
\mathbf{y}_{S}&{\mathsf{Z}}_{S}&*&\dots&{\mathsf{Y}}_{S,S}\end{pmatrix}\mbox{
can be completed to a matrix in
}\mathcal{CPP}(\mathbb{R}_{+}\times_{i=0}^{S}{\mathcal{K}}_{i}),\end{split}$
(10)

but the latter constraint holds whenever the conic constraint in (9) holds.
Thus, we can close the relaxation gap between (9) and (1) by appealing to
Burer’s reformulation and 9. However, we believe it is valuable to have a
direct proof that is solely based on the geometry of $\mathcal{CMP}$ and does
not explicitly reference matrix completion. Firstly, we avoid referencing
something abstract, namely completability, by invoking something relatively
concrete, i.e. the geometry of the respective convex cone. Secondly, the proof
shows that the homogenized feasible set of (9) is a face of the respective
instance of $\mathcal{CMP}$, which may be a useful insight for future
investigations of this object. Finally, the proof is a somewhat unexpected
application of the theory laid out in [11], which may inspire similar
approaches to convex reformulations where a desired property, in our case
completability, is inscribed in the structure of the cone $\mathbb{K}$.

To summarize, the reformulation we obtained is similar to the one obtainable
from [4] in that it is a linear-conic optimization problem over an
appropriately structured convex cone. The advantage of our reformulation is
that the number of variables is $S(n_{1}+n_{2})(n_{1}+n_{2}+1)/2$, while for
the traditional approach this number would be
$(n_{1}+Sn_{2})(n_{1}+Sn_{2}+1)/2$, which is a bigger number if $S$ is big
enough. However, similarly to $\mathcal{CPP}$, we cannot directly optimize
over $\mathcal{CMP}$ since no workable description is yet known for this novel
object. We therefore propose the following strategy.

###  3.3 A new strategy for sparse conic reformulations

As stated before, optimizing over $\mathcal{CMP}$ necessitates the
applications of appropriate inner and outer approximations of that cone. On
the one hand, we thus look for necessary conditions
$[{\mathsf{M}}]\in\SS^{S,k}_{n}$ has to meet lest completing
$\Gamma_{*}\left([{\mathsf{M}}]\right)$ to a matrix in the respective
$\mathcal{CPP}$-cone is impossible, and we denote the subset of connected
components that meet these conditions by
${\mathcal{C}}_{nes}\supseteq\mathcal{CMP}$. On the other hand we look for
subsets ${\mathcal{C}}_{suf}\subseteq\mathcal{CMP}$, in other words, we look
for sufficient conditions on a connected component
$[{\mathsf{M}}]\in\SS^{S,k}_{n}$ so that
$\Gamma_{*}\left([{\mathsf{M}}]\right)$ is in fact completable.

As we will show in the next section such necessary and/or sufficient
conditions can be formulated in terms of $\mathcal{CPP}$ constraints. Such
constraints are again intractable in general so we need an additional step in
order to take advantage of these approximations. Set-compeltely positive
matrix cones are very well studied objects and strong inner and out
approximations feature prominently in the existing literature. These
approximations can thus be used to find tractable approximations of
${\mathcal{C}}_{suf}$ and ${\mathcal{C}}_{nes}$. More precisely, whenever we
describe ${\mathcal{C}}_{nes}$ via set-completely postive constraints, we can
loosen these constraints via tractable outer approximation of $\mathcal{CPP}$
as to obtain a new set ${\mathcal{C}}_{outer}\supseteq{\mathcal{C}}_{nes}$.
Conversely, replacing $\mathcal{CPP}$ in the description ${\mathcal{C}}_{suf}$
with a tractable inner approximation we obtain an inner approximation
${\mathcal{C}}_{inner}\subseteq{\mathcal{C}}_{suf}$. In total we get:

${\mathcal{C}}_{inner}\ \subseteq\ {\mathcal{C}}_{suf}\ \subseteq\
\mathcal{CMP}\ \subseteq{\mathcal{C}}_{nes}\ \subseteq\
{\mathcal{C}}_{outer},$

hence, tractable inner and outer approximations of $\mathcal{CMP}$.

The two step nature of our proposed approximation procedure stems from the
fact that there are two sources of difficulty that necessitate resorting to
approximations. The first one is the requirement of completability, which is
addressed by the inner two of the above inclusions. The second one is the
requirement of set-completely positivity, addressed by the outer two of the
above inclusions.

Hence, whenever we approximately solve (9) by replacing $\mathcal{CMP}$ by its
tractable inner and outer approximations we incur a relaxation gap that
consists of two components. The portion of the gap the results from a failure
of meeting the completability requirement we henceforth refer to as
complitability gap, while the portion of the gap the stems from the
approximation error caused by the relaxation of the $\mathcal{CPP}$
constraints will be refered to as the completepositivity gap.

In the next section we will mostly be concerned with narrowing the
complitability gap by providing promising examples for ${\mathcal{C}}_{nes}$
and ${\mathcal{C}}_{suf}$. Also, most of the discussion in the rest of the
article will focus on the quality of this gap. We will, however, also provide
some references to approximations of $\mathcal{CPP}$, in order to give some
orientation on how to narrow the completepositivity gap as well. In the
section on our numerical experiments we will also show some strategies on how
to bypass this gap entirely, albeit in limited cases.

##  4 Inner and outer approximation of $\mathcal{CMP}$ based on set-completely
positive matrix cones

Our goal in this section is to identify conditions on an element
$[{\mathsf{M}}]\in\SS^{S,k}_{n}$ that are either suffiecient or necessary for
$\Gamma_{*}([{\mathsf{M}}])$ to have a set-completely positive completion. In
the following discussion we will show that many such conditions can be given
in terms of set-completely positive

###  4.1 An outer approximation via necessary conditions

For a vector of ground cones
$\bar{{\mathcal{K}}}\coloneqq\left({\mathcal{K}}_{0},\dots,{\mathcal{K}}_{S}\right)$,
we define yet another generalization of the set-completely positive matrix
cone

$\displaystyle\mathcal{CPI}\left(\bar{{\mathcal{K}}}\right)$
$\displaystyle\coloneqq\left\\{\left[\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{1}^{\mathsf{T}}\\\
{\mathsf{Z}}_{1}&{\mathsf{Y}}_{1}\end{pmatrix},\dots,\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{S}^{\mathsf{T}}\\\
{\mathsf{Z}}_{S}&{\mathsf{Y}}_{S}\end{pmatrix}\right]\colon\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\in\mathcal{CPP}({\mathcal{K}}_{0}\times{\mathcal{K}}_{i}),\
i\in[1\\!:\\!S]\right\\},$

where $k<n$.

######  Theorem 10.

We have that
$\mathcal{CPI}\left(\bar{{\mathcal{K}}}\right)\supseteq\mathcal{CMP}\left(\bar{{\mathcal{K}}}\right)$.

###### Proof.

By setting ${\mathsf{X}}=\mathbf{x}\mathbf{x}^{\mathsf{T}},\
{\mathsf{Z}}_{i}=\mathbf{y}_{i}\mathbf{x},\
{\mathsf{Y}}_{i}=\mathbf{y}_{i}\mathbf{y}_{i}^{\mathsf{T}}$ we see that the
generators of $\mathcal{CMP}$ are contained in $\mathcal{CPI}$ and by
convexity $\mathcal{CMP}$ itself is contained. ∎

We thus have an outer approximations of $\mathcal{CMP}$ in terms of set-
completely positive matrix blocks, which is convinient for approximately
optimizing of over $\mathcal{CMP}$ since set-completely positive optimization
is a well researched field.

###  4.2 Inner approximations via sufficient conditions

We define

$\displaystyle\mathcal{CPS}\left(\bar{{\mathcal{K}}}\right)$
$\displaystyle\coloneqq\left\\{\left[\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\right]_{i\in[1\\!:\\!S]}\colon\begin{pmatrix}{\mathsf{W}}_{i}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\in\mathcal{CPP}({\mathcal{K}}_{0}\times{\mathcal{K}}_{i}),\
i\in[1\\!:\\!S],\ \sum_{i=1}^{S}{\mathsf{W}}_{i}={\mathsf{X}}\right\\},$

where $k<n$. While it is not immediately obvious, the above cone is in fact a
subset of $\mathcal{CMP}$. In fact the generators of $\mathcal{CPS}$ are a
subset of the generators of $\mathcal{CMP}$ as we will now show.

######  Theorem 11.

$\mathcal{CPS}\left(\bar{{\mathcal{K}}}\right)\subseteq\mathcal{CMP}\left(\bar{{\mathcal{K}}}\right)$
if ${\mathcal{K}}_{i},\ i\in[1\\!:\\!S]$ contain the origin.

###### Proof.

Let $[\bar{{\mathsf{X}}}]\in\mathcal{CPS}$, we need to to show that

$\displaystyle\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}=\sum_{k=1}^{r}\begin{pmatrix}\mathbf{x}^{k}\\\
\mathbf{y}_{i}^{k}\end{pmatrix}\begin{pmatrix}\mathbf{x}^{k}\\\
\mathbf{y}_{i}^{k}\end{pmatrix}^{\mathsf{T}},\ \mbox{with
}\begin{pmatrix}\mathbf{x}^{k}\\\
\mathbf{y}_{i}^{k}\end{pmatrix}\in{\mathcal{K}}_{0}\times{\mathcal{K}}_{i},\
k\in[1\\!:\\!r],\ i\in[1\\!:\\!S].$

for some fixed $r\in\mathbb{N}$. The important aspect is that the
decomposition of the ${\mathsf{X}}$-component does not change across
$i\in[1\\!:\\!S]$. We have

$\displaystyle\begin{pmatrix}{\mathsf{W}}_{i}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}=\sum_{k=1}^{r_{i}}\begin{pmatrix}\mathbf{w}_{i}^{k}\\\
\mathbf{y}_{i}^{k}\end{pmatrix}\begin{pmatrix}\mathbf{w}_{i}^{k}\\\
\mathbf{y}_{i}^{k}\end{pmatrix}^{\mathsf{T}}\mbox{with
}\begin{pmatrix}\mathbf{w}^{k}_{i}\\\
\mathbf{y}_{i}^{k}\end{pmatrix}\in{\mathcal{K}}_{0}\times{\mathcal{K}}_{i},\
k\in[1\\!:\\!r_{i}],\ i\in[1\\!:\\!S].$

We can set $r=\sum_{i=1}^{S}r_{i}$ and we have
${\mathsf{X}}=\sum_{i=1}^{S}{\mathsf{W}}_{i}=\sum_{i=1}^{S}\sum_{k=1}^{r_{i}}\mathbf{w}_{i}^{k}(\mathbf{w}_{i}^{k})^{\mathsf{T}}$
so that

$\displaystyle\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}=\sum_{k=1}^{r_{i}}\begin{pmatrix}\mathbf{w}_{i}^{k}\\\
\mathbf{y}_{i}^{k}\end{pmatrix}\begin{pmatrix}\mathbf{w}_{i}^{k}\\\
\mathbf{y}_{i}^{k}\end{pmatrix}^{\mathsf{T}}+\sum_{j\in[1\\!:\\!S]\setminus\left\\{i\right\\}}\sum_{k=1}^{r_{j}}\begin{pmatrix}\mathbf{w}_{j}^{k}\\\
\mathbf{o}\end{pmatrix}\begin{pmatrix}\mathbf{w}_{j}^{k}\\\
\mathbf{o}\end{pmatrix}^{\mathsf{T}}.$

with

$\displaystyle\begin{pmatrix}\mathbf{w}_{i}^{k}\\\
\mathbf{y}_{i}^{k}\end{pmatrix}\in{\mathcal{K}}_{0}\times{\mathcal{K}}_{i},\
k\in[1\\!:\\!r_{i}],\ \begin{pmatrix}\mathbf{w}_{j}^{k}\\\
\mathbf{o}\end{pmatrix}\in{\mathcal{K}}_{0}\times{\mathcal{K}}_{i},\
k\in[1\\!:\\!r_{j}],\ j\in[1\\!:\\!S]\setminus\left\\{i\right\\},$

where the last inclusion holds, since ${\mathcal{K}}_{i}$ contain the origin.
∎

For obtaining a second approximation, we can use a slight generalization of
known results on matrix completion to obtain another inner approximation for
the case
${\mathcal{K}}_{0}\in\left\\{\mathbb{R}^{n_{1}}_{+},\mathbb{R}^{n_{1}}\right\\}$
that can be used in conjunction with $\mathcal{CPS}$. We define

$\displaystyle\mathcal{CBC}_{k}\left(\bar{{\mathcal{K}}}\right)$
$\displaystyle\coloneqq\left\\{\left[\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\right]_{i\in[1\\!:\\!S]}\colon\begin{pmatrix}x&\mathbf{z}_{i}^{\mathsf{T}}\\\
\mathbf{z}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\in\mathcal{CPP}(\mathbb{R}_{+}\times{\mathcal{K}}_{i}),\begin{array}[]{l}{\mathsf{Z}}_{i}=\mathbf{z}_{i}\mathbf{e}_{k}^{\mathsf{T}}\\\
{\mathsf{X}}=x\mathbf{e}_{k}\mathbf{e}_{k}^{\mathsf{T}}\end{array},\
i\in[1\\!:\\!S]\ \right\\},$

and

$\displaystyle\mathcal{CBC}\left(\bar{{\mathcal{K}}}\right)\coloneqq\sum_{k=1}^{n_{1}}\mathcal{CBC}_{k}\left(\bar{{\mathcal{K}}}\right).$

Then we can prove the containment

######  Theorem 12.

$\mathcal{CBC}\left(\bar{{\mathcal{K}}}\right)\subseteq\mathcal{CMP}\left(\bar{{\mathcal{K}}}\right)$
for
${\mathcal{K}}_{0}\in\left\\{\mathbb{R}^{n_{1}}_{+},\mathbb{R}^{n_{1}}\right\\}$.

###### Proof.

Since convex cones are closed under addition the statement will follow if we
show that
$\mathcal{CBC}_{k}\left(\bar{{\mathcal{K}}}\right)\subseteq\mathcal{CMP}\left(\bar{{\mathcal{K}}}\right)$
for any $k\in[1\\!:\\!n_{1}]$. We will discuss the case, where
${\mathcal{K}}_{0}=\mathbb{R}^{n_{1}}_{+}$ first. For an element of
$\mathcal{CBC}_{k}$ consider the partial matrix

$\displaystyle{\mathsf{M}}\coloneqq\begin{pmatrix}x&\mathbf{z}_{1}^{\mathsf{T}}&\dots&\mathbf{z}_{S}^{\mathsf{T}}\\\
\mathbf{z}_{1}&{\mathsf{Y}}_{1}&\dots&*\\\ \vdots&\vdots&\ddots&\vdots\\\
\mathbf{z}_{S}&*&\dots&{\mathsf{Y}}_{S}\end{pmatrix},\mbox{for which by
construction }\begin{pmatrix}x&\mathbf{z}_{i}^{\mathsf{T}}\\\
\mathbf{z}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\mathcal{CPP}\left(\mathbb{R}_{+}\times{\mathcal{K}}_{i}\right)\mbox{
holds.}$

W.l.o.g. we cann assume $x=1$. We will proof that ${\mathsf{M}}$ can be
completed to a member in
$\mathcal{CPP}(\mathbb{R}_{+}\times_{i=1}^{S}{\mathcal{K}}_{i})$. The desired
inclusion then follows since zero rows and columns can be added in oder to
obtain a member of
$\mathcal{CPP}(\mathbb{R}_{+}^{n_{1}}\times_{i=1}^{S}{\mathcal{K}}_{i})$. Our
proof involves merely a slight adaptation of the argument used for the
completion of partial completely positive matrices given in [6], who
considered the case where ${\mathcal{K}}_{i}$ are all positive orthants. We
show that such an assumption is unnecessary. We proceed by induction and start
by showing that the first $(2n_{2}+1)\times(2n_{2}+1)$ principal submatrix of
${\mathsf{M}}$ can be completed to a matrix in
$\mathcal{CPP}\left(\mathbb{R}_{+}\times{\mathcal{K}}_{1}\times{\mathcal{K}}_{2}\right)$.
After a perturbation, this matrix can be written as

$\displaystyle\bar{{\mathsf{M}}}\coloneqq\begin{pmatrix}{\mathsf{Y}}_{1}&\mathbf{z}_{1}&{\mathsf{X}}^{\mathsf{T}}\\\
\mathbf{z}_{1}^{\mathsf{T}}&1&\mathbf{z}_{2}^{\mathsf{T}}\\\
{\mathsf{X}}&\mathbf{z}_{2}&{\mathsf{Y}}_{2}\end{pmatrix}$

where we replaced the unspecified entries by ${\mathsf{X}}$. Observe that the
submatrices

$\displaystyle{\mathsf{M}}_{1}\coloneqq\begin{pmatrix}{\mathsf{Y}}_{1}&\mathbf{z}_{1}\\\
\mathbf{z}_{1}^{\mathsf{T}}&1\end{pmatrix}\in\mathcal{CPP}\left({\mathcal{K}}_{1}\times\mathbb{R}_{+}\right),\
{\mathsf{M}}_{2}\coloneqq\begin{pmatrix}1&\mathbf{z}_{2}^{\mathsf{T}}\\\
\mathbf{z}_{2}&{\mathsf{Y}}_{2}\end{pmatrix}\in\mathcal{CPP}\left(\mathbb{R}_{+}\times{\mathcal{K}}_{2}\right),$

so that

$\displaystyle{\mathsf{M}}_{1}=\sum_{l=1}^{m_{1}}\begin{pmatrix}\mathbf{f}_{l}\\\
f^{0}_{l}\end{pmatrix}\begin{pmatrix}\mathbf{f}_{l}\\\
f^{0}_{l}\end{pmatrix}^{\mathsf{T}}\mbox{ with
}\begin{pmatrix}\mathbf{f}_{i}\\\
f^{0}_{i}\end{pmatrix}\in{\mathcal{K}}_{1}\times\mathbb{R}_{+},$
$\displaystyle{\mathsf{M}}_{2}=\sum_{k=1}^{m_{2}}\begin{pmatrix}g^{0}_{k}\\\
\mathbf{g}_{k}\end{pmatrix}\begin{pmatrix}g^{0}_{k}\\\
\mathbf{g}_{k}\end{pmatrix}^{\mathsf{T}}\mbox{ with
}\begin{pmatrix}g^{0}_{k}\\\
\mathbf{g}_{k}\end{pmatrix}\in\mathbb{R}_{+}\times{\mathcal{K}}_{2}.$

Define $m_{1}m_{2}$ vectors

$\displaystyle\mathbf{v}_{lk}\coloneqq\begin{pmatrix}g^{0}_{k}\mathbf{f}_{l}\\\
f^{0}_{l}g^{0}_{k}\\\
f^{0}_{l}\mathbf{g}_{k}\end{pmatrix}\in{\mathcal{K}}_{1}\times\mathbb{R}_{+}\times{\mathcal{K}}_{2},\
l\in[1\\!:\\!m_{1}],\ k\in[1\\!:\\!m_{2}],$ (11)

then the matrix $\sum_{k,l}\mathbf{v}_{lk}\mathbf{v}_{lk}^{\mathsf{T}}$ is the
matrix $\bar{{\mathsf{M}}}$ with
${\mathsf{X}}=\mathbf{z}_{2}\mathbf{z}_{1}^{\mathsf{T}}$. Hence, after undoing
the perturbation, we generate the desired completion. For the $j$-th induction
step we can repeat the argument with ${\mathcal{K}}_{1}$ replaced by
$\times_{i=1}^{j-1}{\mathcal{K}}_{1}$ and ${\mathcal{K}}_{2}$ replaced by
${\mathcal{K}}_{j}$. For the case, where
${\mathcal{K}}_{0}=\mathbb{R}^{n_{1}}$ the proof proceeds analogously with
$\mathbb{R}_{+}$ replaced by $\mathbb{R}$. ∎

Finally, we present a simple, yet, as we will see in the numerical
experiments, very effective inner approximation, which is applicable whenever
${\mathcal{K}}_{i}\in\left\\{\mathbb{R}^{n_{2}}_{+},\
\mathbb{R}^{n_{2}}\right\\},\ i\in[1\\!:\\!S]$. Again, we express it as the
sum of simpler cones given by

$\displaystyle\mathcal{DDC}_{k,s}\left(\bar{{\mathcal{K}}}\right)$
$\displaystyle\coloneqq\left\\{\left[\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\right]_{i\in[1\\!:\\!S]}\colon\begin{pmatrix}{\mathsf{X}}&\mathbf{z}_{i}^{\mathsf{T}}\\\
\mathbf{z}_{i}&y_{i}\end{pmatrix}\in\mathcal{CPP}({\mathcal{K}}_{0}\times\mathbb{R}_{+}),\begin{array}[]{l}{\mathsf{Z}}_{s}=\mathbf{z}_{i}\mathbf{e}_{k}^{\mathsf{T}}\\\
{\mathsf{Y}}_{s}=y\mathbf{e}_{k}\mathbf{e}_{k}^{\mathsf{T}}\\\
{\mathsf{Y}}_{i}={\mathsf{O}},\ i\in[1\\!:\\!S]\setminus\left\\{s\right\\}\\\
{\mathsf{Z}}_{i}={\mathsf{O}},\
i\in[1\\!:\\!S]\setminus\left\\{s\right\\}\end{array}\right\\}.$

We can then define

$\displaystyle\mathcal{DDC}\left(\bar{{\mathcal{K}}}\right)\coloneqq\sum_{s=1}^{S}\sum_{k=1}^{n_{2}}\mathcal{DDC}_{k,s}\left(\bar{{\mathcal{K}}}\right),$

about which the following statement is easily proved.

######  Theorem 13.

We have
$\mathcal{DDC}\left(\bar{{\mathcal{K}}}\right)\subseteq\mathcal{CMP}\left(\bar{{\mathcal{K}}}\right)$
if ${\mathcal{K}}_{i}\in\left\\{\mathbb{R}^{n_{2}}_{+},\
\mathbb{R}^{n_{2}}\right\\},\ i\in[1\\!:\\!S]$.

###### Proof.

Since $\mathcal{CMP}$ is convex, it is enough to proof that
$\mathcal{DDC}_{s,k}\left(\bar{{\mathcal{K}}}\right)\subseteq\mathcal{CMP}\left(\bar{{\mathcal{K}}}\right)$
for any $k\in[1\\!:\\!n_{2}],\ s\in[1\\!:\\!S]$. For any
$[{\mathsf{M}}]\in\mathcal{DDC}_{s,k}\left(\bar{{\mathcal{K}}}\right)$ the
required completion of $\Gamma_{*}([{\mathsf{M}}])$ is easily obtained by
obtained filling out the uncspecified entries with zeros. ∎

Note, that the statement remains true if we merely work with a selection of
$\mathcal{DDC}_{k,s}$ in order to alleviate some if the numerical burden.

All these inner and outer approximations we now discussed represent an effort
to tackle the completability gap. But, as we laid out at the beginning of this
section, they all have it in common that they are constructed using set-
completely positive matrix cones, over which we cannot optimized directly. In
this text we will give discuss some instances where the completepositivity gap
can be bypassed conveniently, so that we can focus on assessing the extent of
the completability gap.

####  4.2.1 Limitations of the inner approximations of $\mathcal{CMP}$

We will now critically asses the strength of the inner approximations
discussed above. Of course, an obvious limitation of $\mathcal{CBC}$ and
$\mathcal{DDC}$ is that the ${\mathsf{X}}$ and the ${\mathsf{Y}}_{i}$
components respectively can only be diagonal matrices. In case of
$\mathcal{CBC}$, this has some undesirable consequences when approximating an
exact reformulation of (1) based on 8.

Obviously, if $\mathcal{CMP}$ is replaced by $\mathcal{CBC}$, then
$\mathbf{x}=\mathbf{o}$, since these values reside in off-diagonal of the
north-west blocks. But then 8 implies that $\mathbf{x}$ is the convex
combination of some $\mathbf{x}_{j},j\in[1\\!:\\!k]$ that are part of a
feasible solution to (1). Since the feasible set is bounded we get
$\mathbf{x}_{j}=\mathbf{o}$ as well, which eventually yields
${\mathsf{Z}}_{i}=\sum_{j=1}^{k}\lambda_{j}\mathbf{y}^{i}_{j}\mathbf{x}_{j}^{\mathsf{T}}={\mathsf{O}}$,
so that the approximations eliminates these components entirely.

A similar deficiency can be identified for $\mathcal{CPS}$. To see this, note
the from the proof of 11 we have that all extreme rays of $\mathcal{CPS}$ are
in fact rank one, in the sense that all matrix components are rank one
matrices. In other words the generators of $\mathcal{CPS}$ are a subset of the
generators of $\mathcal{CMP}$. Hence, if $\mathcal{CMP}$ is replaced by
$\mathcal{CPS}$ in (8) the extreme point of the feasible can be shown to be
rank one as well, by invoking a similar argument as in 8. If
${\mathsf{Y}}_{i},\mathbf{y}_{i},{\mathsf{W}}_{i},\ i\in[1\\!:\\!S]$ are part
of feasible extremal solution of the respective approximation we get

$\displaystyle\begin{pmatrix}w_{0}^{i}&\mathbf{y}_{i}^{\mathsf{T}}\\\
\mathbf{y}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\in\SS^{n_{2}+1}_{+},\
i\in[1\\!:\\!S],\quad\sum_{i=1}^{S}w^{i}_{0}=1,$

where $w_{0}^{i}$ are the north-west entries of ${\mathsf{W}}_{i},\
i\in[1\\!:\\!S]$. By Schur complementation we get $\SS^{n_{1}}_{+}\ni
w_{0}^{i}{\mathsf{Y}}_{i}-\mathbf{y}_{i}\mathbf{y}_{i}^{\mathsf{T}}=w_{0}^{i}\mathbf{y}_{i}\mathbf{y}_{i}^{\mathsf{T}}-\mathbf{y}_{i}\mathbf{y}_{i}^{\mathsf{T}}$,
for any fixed $i\in[1\\!:\\!S]$, which implies that either $w^{0}_{i}=1$ or
$\mathbf{y}_{i}=\mathbf{o}$. Thus, the approximations based on $\mathcal{CPS}$
eliminates all but one of the ${\mathsf{Y}}_{i}$ components and as a
consequence all but one of the ${\mathsf{Z}}_{i}$ components. Depending on the
model at hand, this can be an advantage as we will see in the numerical
experiments in Section 5. However, in case $({\mathsf{F}}_{i},\
{\mathsf{G}}_{i},{\mathbf{r}}_{i})$ is identical across $i\in[1\\!:\\!S]$, the
approximations actually eliminates all ${\mathsf{Y}}_{i}$ and
${\mathsf{Z}}_{i}$ components. To see this, consider that in said case we have
that
$\operatorname{diag}({\mathsf{G}}_{i}{\mathsf{Y}}_{i}{\mathsf{G}}_{i}^{\mathsf{T}})={\mathsf{O}}$
for one $i$ forces the same for all $i$, which by boundedness implies
${\mathsf{Y}}_{i}={\mathsf{O}}$, entailing ${\mathsf{Z}}_{i}={\mathsf{O}}$ for
all $i\in[1\\!:\\!S]$.

Despite these limitations we have found instances of (1) where the inner
approximations yield favorable results. We will discuss these instances in the
next section, where we conduct numerical experiments assessing the efficacy of
the inner and outer approximations.

##  5 Numerical experiments

As discussed in the introduction, the authors of [3] tried to solve (2St3QP)
using copositive reformulations, where they compared the traditional model
akin to (2), with what we can now conceptualize as the $\mathcal{CPI}$
relaxation of the $\mathcal{CMP}$ reformulation of (2St3QP). For both models,
they used their respective $\mathcal{DNN}$ relaxations in order to produce
solutions. For the purpose of certifying optimality, they exploited the fact
that either relaxation also produces feasible solutions, hence upperbounds,
since both leave the original space of variables in tact. For many instances,
these bounds alone closed the optimality gap, but for some gaps persisted,
even thought they were narrowed by extensive polishing procedures, about which
we will not go into detail here. What we are setting out to do in this section
is revisiting these instances and new variants of them, in order to see if the
bounds we introduced in this article can further narrow the optimality gap.

In what follows we will use Mosek as a conic optimization solver, and Gurobi
as a global optimization solver, to both of which we interface via the YALMIP
enviroment in Matlab. All experiments are run on a Intel Core i5-9300H CPU
with 2.40GHz and 16GB of ram.

In our epxeriments consider the following problem

$\displaystyle
v({\mathcal{F}})\coloneqq\min_{\mathbf{x}\in\mathbb{R}^{n_{1}},\mathbf{y}_{i}\in\mathbb{R}^{n_{2}}}\left\\{\mathbf{x}^{\mathsf{T}}{\mathsf{A}}\mathbf{x}+\sum_{i=1}^{S}p_{i}\left(\mathbf{x}^{\mathsf{T}}{\mathsf{B}}_{i}\mathbf{y}_{i}+\mathbf{y}_{i}^{\mathsf{T}}{\mathsf{C}}_{i}\mathbf{y}_{i}\right)\colon(\mathbf{x},\bar{\mathbf{y}})\in{\mathcal{F}},\right\\},$
(12)

with the following specifications for ${\mathcal{F}}$:

$\displaystyle{\mathcal{F}}_{1}$
$\displaystyle\coloneqq\left\\{\begin{pmatrix}\mathbf{x}\\\
\bar{\mathbf{y}}\end{pmatrix}\in\mathbb{R}^{n_{1}+Sn_{2}}_{+}\colon\mathbf{e}^{\mathsf{T}}\mathbf{x}+\mathbf{e}^{\mathsf{T}}\mathbf{y}_{i}=1,\
i\in[1\\!:\\!S]\right\\},$ $\displaystyle{\mathcal{F}}_{2}$
$\displaystyle\coloneqq\left\\{\begin{pmatrix}\mathbf{x}\\\
\bar{\mathbf{y}}\end{pmatrix}\in\left\\{0,1\right\\}^{S}\times\mathbb{R}^{Sn_{2}}\colon\mathbf{e}^{\mathsf{T}}\mathbf{x}=(S-1),\
\sum_{i=1}^{S}\mathbf{y}_{i}^{\mathsf{T}}\mathbf{y}_{i}=1,\
\mathbf{y}_{i}x_{i}=\mathbf{o},\ i\in[1\\!:\\!S]\right\\},$
$\displaystyle{\mathcal{F}}_{3}$
$\displaystyle\coloneqq\left\\{\begin{pmatrix}\mathbf{x}\\\
\bar{\mathbf{y}}\end{pmatrix}\in\mathbb{R}^{n_{1}}\times\mathbb{R}^{Sn_{2}}_{+}\colon\mathbf{x}^{\mathsf{T}}\mathbf{x}=1,\
\sum_{i=1}^{S}\mathbf{y}_{i}^{\mathsf{T}}\mathbf{y}_{i}=1\right\\}.$

where
$\bar{\mathbf{y}}\coloneqq\left(\mathbf{y}_{1},\dots,\mathbf{y}_{S}\right)$.

The data for the objective functions coefficients were generated using the
same two approaches as in [3]. Next to setting $p_{i}=1/S,\ i\in[1\\!:\\!S]$,
the following two schemes for generating the problem data have been
implemented:

  * Scheme 1:

For the first one, we sample $n_{1}+n_{2}$ points from the unit square. The
first $n_{1}$ points are fixed and their mutual distances are used to populate
the entries in ${\mathsf{A}}$. For the other $n_{2}$ points we assume that
they are only known to lie in square with side length $2\varepsilon$, where
their position follows a uniform distribution. For these points $S$ samples
are generated and for the $s$-th sample, the distances between them and
between them and the first $n_{1}$ points populate the entries of
${\mathsf{C}}_{s}$ and ${\mathsf{B}}_{s}$ respectively.

  * Scheme 2:

For the second one, we choose $A_{ij}\sim\mathcal{U}_{\left\\{0,1\right\\}}$,
$B_{ij}\sim\mathcal{U}_{[0:10]}$, $C_{ij}\sim\mathcal{U}_{[0,0.1]}$,
independently of each other, where $\mathcal{U}_{\mathcal{M}}$ is the uniform
distribution with support $\mathcal{M}$.

We will now proceed with a discussion of the different instances of
${\mathcal{F}}_{i},\ i\in[1\\!:\\!4]$, where we present the conic respective
reformulation/relaxation and the inner and outer approximations of its sparse
counterpart. Regarding the inner approximations, note that if one combines
them as suggested above, there will only ever be one non-redundant
approximation. The reason is that the linear functions attain the optimum at
an extreme point of the feasible set and the extreme rays of a sum of cones
are a subset of the extreme rays of the individual cones. Thus, for every
${\mathcal{F}}_{i},\ i\in[1\\!:\\!4]$ we will discuss the merits of only one
specific inner approximation at a time. The upperbounds will be obtained by
using $\mathcal{CPI}$ by default. The focus of the discussion will be the
quality of the bounds obtained. Specifically, we are interested in assessing
the completability gap, which necessitates guaranteeing a completepositivity
gap of zero. We will discuss how the latter was achieved case by case.

###  5.1 Using $\mathcal{DDC}$ under ${\mathcal{F}}_{1}$

By choosing ${\mathcal{F}}={\mathcal{F}}_{1}$ we are recovering the scenario
problem for the two-stage stochastic standard quadratic optimization problem
introduced in [3]. In the experiments conducted there, a conic lower bound was
used that is equivalent to the outer approximation of (8) based on
$\mathcal{CPI}$. Since the original space of variables is preserved, the conic
relaxation also yielded an upper bound that conveniently closed the optimality
gap for all instances generated by sc heme 1. However, the gaps generated by
the $\mathcal{CPI}$-approximation were typically large. In this section we
will test whether the gap can be also be improved by using the inner
approximations introduced here.

Due to the limitations discussed in Section 4.2.1, the only inner
approximation that is meaningfully applicable here is the one based on
$\mathcal{DDC}$. Thus, the approximation will involve $Sn_{2}$ constraints
involving $\mathcal{CPP}(\mathbb{R}^{n_{1}+1}_{+}\times\mathbb{R}_{+})$. In
case $n_{1}+2\leq 4$ these constraints can be represented via semidefinite
constraints, since
$\mathcal{CPP}(\mathbb{R}^{n}_{+})=\SS^{n}_{+}\cap{\mathcal{N}}^{n}\eqqcolon\mathcal{DNN}^{n}$
whenever $n\leq 4$, so that the completepositivity gap can be conveniently
bypassed. If $n_{1}+2>4$ the relaxation based on $\mathcal{DNN}$ is an outer
approximation of $\mathcal{DDC}$, which itself is an inner approximation of
$\mathcal{CMP}$ so that we cannot qualify the resulting approximation as
neither outer nor inner. However, the original space of variables stays in
tact regardless so that in cases where $n_{1}+2>4$ we can still obtain another
upper bound that potentially narrows the optimality gap.

###  5.2 Using $\mathcal{CPS}$ under ${\mathcal{F}}_{2}$

The model encodes selecting one out of $S$ groups of variables to be nonzero
and optimizing the objective using just these variables. While there are more
straightforward ways of encoding this process, the one presented here is the
one for which the conic bounds behaved most favorably.

In order to obtain an $\mathcal{CMP}$ reformulation for computing
$v({\mathcal{F}}_{2})$ via 8 we would have to do some prior adaption of the
problem. First of all, $x_{i}\in\\{0,1\\},i\in[1\\!:\\!S]$ can be reformulated
as quadratic constraints $x^{2}_{i}-x_{i}=0$, so that in order for the
assumptions of the theorem to hold, we would have to introduce redundant
constraints and additional variables given by $x_{i}+s_{i}=1,\ s_{i}\geq 0,\
i\in[1\\!:\\!S]$. Secondly, in order for $\mathbf{y}_{i}x_{i}=0$ to fulfill
said assumptions we would have to split each $\mathbf{y}_{i}$ into a positive
and a negative component and enforce the constraints for both components.
Lastly, the quadratic constraints would need to be absorbed into the a second
order cone constraint. Due to the introduction of this many variables, we
would have no chance at bypassing the completepositivity gap. Thus, we will
merely work with the the following $\mathcal{CMP}$ based relaxation:

$\displaystyle\begin{split}\min_{{\mathsf{X}},{\mathsf{Y}}_{i},{\mathsf{Z}}_{i},\mathbf{x},\mathbf{y}_{i}}{\mathsf{A}}_{i}\bullet{\mathsf{X}}+\mathbf{a}^{\mathsf{T}}\mathbf{x}&+\sum_{i=1}^{S}{\mathsf{B}}_{i}\bullet{\mathsf{Z}}_{i}+{\mathsf{C}}_{i}\bullet{\mathsf{Y}}_{i,i}+\mathbf{c}_{i}^{\mathsf{T}}\mathbf{y}\\\
\mathrm{s.t.:}\ \mathbf{e}^{\mathsf{T}}\mathbf{x}&=(S-1),\\\
\mathbf{e}\mathbf{e}^{\mathsf{T}}\bullet{\mathsf{X}}&=(S-1)^{2},\\\
\sum_{i=1}^{S}{\mathsf{Y}}_{i}&=1,\\\ {\mathsf{Z}}_{i}\mathbf{e}_{1}&=0,\
i\in[1\\!:\\!S],\\\
\left[\begin{pmatrix}1&\mathbf{x}^{\mathsf{T}}&\mathbf{y}_{i}^{\mathsf{T}}\\\
\mathbf{x}&{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
\mathbf{y}_{i}&{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\right]_{i\in[1\\!:\\!S]}&\in\mathcal{CMP}\left(\mathbb{R}_{+}^{n_{1}+1},\mathbb{R}^{n_{2}},\dots,\mathbb{R}^{n_{2}}\right).\end{split}$
(13)

When working with teh $\mathcal{CPS}$ based lower bound, we obtain a problem
with $S$ conic constraints involving
$\mathcal{CPP}(\mathbb{R}_{+}^{n_{1}+1}\times\mathbb{R}^{n_{2}})$. Here we can
use a result from [12, Theorem 1], which states that

$\displaystyle\mathcal{CPP}(\mathbb{R}_{+}^{n_{1}+1}\times\mathbb{R}^{n_{2}})=\left\\{\begin{pmatrix}{\mathsf{M}}_{1}&{\mathsf{M}}_{2}^{\mathsf{T}}\\\
{\mathsf{M}}_{2}&{\mathsf{M}}3\end{pmatrix}\in\SS^{n_{1}+n2+1}\colon{\mathsf{M}}_{1}\in\mathcal{CPP}(\mathbb{R}^{n_{1}+1}_{+})\right\\}.$

This allows us to bypass the completepositivity gap whenever $n_{1}+1\leq 4$.
However, since the above conic problem is already a lower bound, the bounds we
obtain from further approximating it can merely be used to asses how well that
lower bound hast been approximated. We will see, however, that the results we
obtain seem to indicate that (13) is at the very least a very tight bound,
that is very well approximated via $\mathcal{CPI}$ and $\mathcal{CPS}$.

###  5.3 Using $\mathcal{CBC}$ under ${\mathcal{F}}_{3}$

In order to bypass the weakness of $\mathcal{CBC}$ outlined in Section 4.2.1
we will work with a simplified, sparse, conic reformulation given by

$\displaystyle\begin{split}\min_{{\mathsf{X}},{\mathsf{Y}}_{i},{\mathsf{Z}}_{i},\mathbf{x},\mathbf{y}_{i}}{\mathsf{A}}_{i}\bullet{\mathsf{X}}+\sum_{i=1}^{S}{\mathsf{B}}_{i}\bullet{\mathsf{Z}}_{i}&+{\mathsf{C}}_{i}\bullet{\mathsf{Y}}_{i,i}\\\
\mathrm{s.t.:}\
{\mathsf{I}}\bullet{\mathsf{X}}+\sum_{i=1}^{S}{\mathsf{I}}\bullet{\mathsf{Y}}_{i}&=1,\\\
\left[\begin{pmatrix}{\mathsf{X}}&{\mathsf{Z}}_{i}^{\mathsf{T}}\\\
{\mathsf{Z}}_{i}&{\mathsf{Y}}_{i}\end{pmatrix}\right]_{i\in[1\\!:\\!S]}&\in\mathcal{CMP}\left(\mathbb{R}^{n_{1}}_{+},\mathbb{R}^{n_{2}},\dots,\mathbb{R}^{n_{2}}\right).\end{split}$
(14)

The fact that this is in fact a valid reformulation and not just a lower bound
can be deduced from 6 by choosing $\mathbb{H}$ to be the hyperplane
corresponding to the one linear constraint that is present in (14), and
$\mathbb{J}$ to be all of $\mathcal{CMP}$. The boundedness of
$\mathbb{J}\cap\mathbb{H}$ follows from the fact that the identity matrix
${\mathsf{I}}$ is positive definite. In this reformulation $\mathbf{x}$ is
absent so that the problem lined out in Section 4.2.1 is mute. Of course, this
comes at the cost, of having merely a single upper bound given by the optimal
solution of the $\mathcal{CBC}$ approximation. However, since
${\mathcal{K}}_{i}=\mathbb{R}^{n_{2}},\ i\in[1\\!:\\!S]$ we can use the fact
that $\mathcal{CPP}(\mathbb{R}_{+}\times\mathbb{R}^{n})=\SS^{n}_{+}$ (see [2,
Section 2]) in order to close the completepositivity gap regardless of the
dimension of the problem. We also like to note, that there always is a
feasible value with optimal value equal to zero, which leads to optimality
gaps being equal to infinity if the lower bound is at zero precisely. In order
to avoid this inconvenience we added 1 as a constant to the objective
function.

###  5.4 Design of the experiments and results

For each of the models we conduct two types of experiments. For the first one
we choose the dimension of the problem such, that the completepositivity gap
could be bypassed and one where that is not the case. For the latter
instances, we worked with outer approximations of the respective set-
completely positive constraints. Hence, the $\mathcal{CPI}$ relaxation was
further relaxed, so that the resulting problem can be qualified as a valid
lower bound. The relaxation of the inner approximation does not allow for such
a qualification, since we obtain lower bound to an upper bound. However, the
relaxation yields valid upperbounds as a byproduct since the original space of
variables stays in tact for all but the $\mathcal{CBC}$ relaxation of
${\mathcal{F}}_{3}$. But for the latter, the completepositivity gap can be
bypassed regardless of the dimension of the problem data. For every choice on
$(n_{1},n_{2},S)$ and ${\mathcal{F}}_{i},\ i=1,2,3$ we generated 10 instances
from t scheme 1 and 2 respectively. For every instance we calculated the
$\mathcal{CPI}$ lower bound, the bounds and approximations based on the
respective inner approximations, and in addition we used upper and lower
bounds achieved by Gurobi within a 5 minute time limit.

The results are summarized in Table 1. The "instance-types" are indicated by a
quadruple of the form $n_{1}\\_n_{2}\\_S\\_s$, where
$s\in\left\\{1,2\right\\}$ indicates the scheme by which we constructed the
instances. In the multi-column "Conic Gaps" we report the average gap between
the $\mathcal{CPI}$ lower bound and the feasible solution generated from the
$\mathcal{CPI}$ bound (UB), the optimal value of the inner approximations (I)
and the feasible solution generated from the latter approximations (IUB). For
"Gurobi Gaps" we calculate these gaps with respect to the lower bound fond by
Gurobi instead of the one obtained from $\mathcal{CPI}$. In addition we
present the gap between the $\mathcal{CPI}$ based lower bound and the
upperbound generated by Gurobi (O), and we also report the optimality gap
obtained by Gurobi itself within the 5 minute time limit (G). All the gaps are
reported in percentages relative to the respective lower bound. Finally, in
the last two multi-columns, we count the number of times the conic and the
gurobi gaps were smaller then $0.01\%$, at which point we consider the
instance solved.

For the experiments on ${\mathcal{F}}_{1}$ we see that phenomenon already
documented in [3] persists: instances from scheme 1 are regularly solved via
$\mathcal{CPI}$ alone, while that is not the case for the scheme 2 instances.
However, for these instances the feasible solutions from the $\mathcal{DDC}$
approximation yield excellent bounds, revealing that both approximations are
very good, albeit not quite good enough to solve the instance on $0.01\%$
tolerance threshold. We also note that $\mathcal{CPI}$ yields a much better
lower bound than Gurobi does within the time limit, sometimes even certifying
optimality of Gurobi’s feasible solution. The upper bound provided by
$\mathcal{DDC}$ performs similar to Gurobi’s upperbound, when measured
relative to Gurobi’s lower bound.

Regarding ${\mathcal{F}}_{2}$ we see that the conic gaps were narrowed quite
substantially by the inner approximation and regularly closed. Gurobi on its
own performed similarly except for the largest instance types, for which it
was outperformed quite substantially. What is remarkable is the fact that the
upper bounds of the approximations of the $\mathcal{CMP}$ relaxation seem to
also upper bound Gurobi’s lower bounds. Conversely, Gurobis upper bounds seem
to live close to the $\mathcal{CPI}$ based lower bounds on average. This might
indicate that the $\mathcal{CMP}$ relaxation may in fact be tight despite the
fact that 8 is not applicable. We hope we can address this phenomenon in
future research. Again, instances from scheme 2 seemed to be a greater
challenge. Note that the smallest gaps are regularly produced by the feasible
solution of the inner approximation.

Finally we can see that for ${\mathcal{F}}_{3}$ the upper bound based on
$\mathcal{CBC}$, unfortunately, performed quite poorly, which is surprising,
given that the derivation of $\mathcal{CBC}$ is the one that is closest to
classical results in matrix completion. On the brighter side, we see that the
$\mathcal{CPI}$ produced good lower bounds that narrow the gap to Gurobi’s
feasible solution better than Gurobi itself.

We also recorded the average time spent on the different approaches in Table
2. We decomposed these running times into the time the respective solver used
to produce the bounds (solver time), the internal model-building time reported
by Yalmip (yalmip time) and the time our implementation used for building the
model that is passed to yalmip (model time). We like to point out a couple of
things. Firstly, for the majority of the instance types Gurobi ran into the
time limit on average. Also, on average the $\mathcal{DDC}$ approximations are
more demanding for Mosek than the other approximations. Still, the models were
solved quite quickly, certainly quicker than 5 minutes. Hence, our methods can
produce good bounds with reasonable effort. Finally we would like to point out
that there are also spikes in the model time for some of the inner
approximations. This, however, is an artifact of our implementation that can
potentially be avoided with better programming.

## Conclusion

In this text we presented a new approach to sparse conic optimization based on
a generalization of the set-completely positive matrix cone, which was
motivated by the study of the two-stage stochastic standard quadratic
optimization problem. Using innner and outer approximations of said cone
allows for certificates of exactness of a sparsification outside of
traditional matrix completion approaches. We demonstrate in numerical
experiments, that this approach can close or at least narrow the optimality
gap in interesting cases. We think that this provides a prove of concept that
may motivate future research. Interesting questions remain, for example, about
the quality of the inner approximations and whether they can be proven to be
exact for special cases.

#### Data availability statement

The datasets generated during and/or analysed during the current study are
available from the corresponding author on reasonable request.

|  | Conic Gaps | Gurobi Gaps | # Gurobi Gaps | # Conic Gaps
---|---|---|---|---|---
| instance-types | UB | I | IUB | G | UB | I | IUB | O | UB | I | IUB | O | UB | I | IUB
${\mathcal{F}}_{1}$ | 10_10_10_1 | 0,00 | (2,57) | 0,02 | 27,20 | 25,59 | (28,93) | 28,44 | 1,27 | 0 | (0) | 0 | 0 | 10 | (0) | 4
20_20_20_1 | 0,00 | (3,42) | 0,03 | 164,45 | 95,96 | 102,58 | (102,19) | 35,32 | 0 | (0) | 0 | 0 | 10 | (0) | 1
2_10_10_1 | 0,00 | 18,36 | 0,18 | 23,16 | 21,63 | 44,12 | 43,31 | 1,24 | 0 | 0 | 0 | 0 | 10 | 0 | 1
2_5_5_1 | 0,00 | 16,97 | 0,16 | 6,68 | 6,58 | 24,76 | 23,97 | 0,09 | 0 | 0 | 0 | 1 | 10 | 0 | 0
10_10_10_2 | 39,57 | (0,29) | 0,37 | 40,36 | 94,88 | (40,36) | 91,35 | 0,30 | 0 | (0) | 0 | 0 | 0 | (0) | 1
20_20_20_2 | 67,37 | (0,32) | 0,46 | 117,23 | 216,92 | (89,96) | 177,13 | 14,72 | 0 | (0) | 0 | 0 | 0 | (0) | 1
2_10_10_2 | 1,66 | 0,25 | 0,23 | 0,48 | 2,15 | 0,73 | 24,04 | 0,00 | 0 | 0 | 0 | 10 | 1 | 0 | 4
2_5_5_2 | 2,53 | 0,18 | 0,19 | 0,08 | 2,61 | 0,25 | 18,77 | 0,00 | 0 | 0 | 1 | 10 | 1 | 0 | 4
${\mathcal{F}}_{2}$ | 10_10_10_1 | 0,06 | (0,01) | 0,00 | 0,01 | 0,06 | (0,01) | 0,03 | 0,01 | 8 | (1) | 1 | 8 | 8 | (8) | 10
20_20_20_1 | 0,01 | (0,00) | 0,00 | 4,53 | 4,36 | (4,35) | 4,38 | 0,17 | 0 | (0) | 0 | 0 | 7 | (10) | 10
3_10_3_1 | 0,00 | 0,00 | 0,00 | 0,01 | 0,01 | 0,01 | 0,03 | 0,00 | 7 | 7 | 0 | 10 | 10 | 10 | 10
3_5_3_1 | 0,19 | 0,00 | 0,00 | 0,00 | 0,20 | 0,01 | 0,14 | 0,00 | 9 | 9 | 7 | 10 | 9 | 9 | 9
10_10_10_2 | 3,73 | (1,48) | 0,02 | 0,01 | 2,21 | (0,00) | 0,06 | 1,48 | 2 | (7) | 3 | 2 | 2 | (2) | 4
20_20_20_2 | 1,22 | (0,48) | 0,01 | 11,84 | 11,49 | (10,67) | 10,78 | 1,54 | 0 | (0) | 0 | 0 | 2 | (3) | 8
3_10_3_2 | 15,09 | 2,66 | 0,03 | 0,01 | 11,90 | 0,01 | 0,07 | 2,66 | 2 | 10 | 2 | 3 | 3 | 3 | 5
3_5_3_2 | 7,73 | 1,21 | 0,01 | 0,00 | 6,31 | 0,00 | 0,01 | 1,21 | 6 | 10 | 10 | 6 | 6 | 6 | 7
${\mathcal{F}}_{3}$ | 10_10_10_1 | - | 404,20 | - | 1,97 | - | 412,79 | - | 0,27 | - | 0 | - | 0 | - | 0 | -
20_20_20_1 | - | 484,57 | - | 1302,01 | - | 954,89 | - | 675,72 | - | 0 | - | 0 | - | 0 | -
10_3_10_1 | - | 907,85 | - | 0,62 | - | 914,15 | - | 0,00 | - | 0 | - | 10 | - | 0 | -
5_3_5_1 | - | 257,07 | - | 0,21 | - | 257,83 | - | 0,00 | - | 0 | - | 10 | - | 0 | -
10_10_10_2 | - | 149,54 | - | 1,79 | - | 153,92 | - | 0,04 | - | 0 | - | 0 | - | 0 | -
10_3_10_2 | - | 164,45 | - | 0,62 | - | 166,06 | - | 0,01 | - | 0 | - | 5 | - | 0 | -
20_20_20_2 | - | 278,50 | - | 1909,44 | - | 304,09 | - | 1781,02 | - | 0 | - | 0 | - | 0 | -
5_3_5_2 | - | 60,58 | - | 0,22 | - | 60,93 | - | 0,00 | - | 0 | - | 10 | - | 0 | -
Table 1: Results on the quality of bounds |  | Solver time | Yalmip time | Model time | Total
---|---|---|---|---|---
| instanctypes | Exact | Inner | Outer | Exact | Inner | Outer | Exact | Inner | Outer | Exact | Inner | Outer
${\mathcal{F}}_{1}$ | 10_10_10_1 | 300,088 | 1,269 | 0,149 | 0,126 | 0,280 | 0,132 | 0,229 | 1,419 | 0,176 | 300,443 | 2,969 | 0,457
20_20_20_1 | 300,076 | 54,426 | 4,898 | 0,191 | 1,880 | 0,262 | 2,550 | 27,699 | 0,968 | 302,817 | 84,004 | 6,128
2_10_10_1 | 300,339 | 0,102 | 0,036 | 0,105 | 0,176 | 0,108 | 0,097 | 0,638 | 0,116 | 300,540 | 0,916 | 0,259
2_5_5_1 | 300,630 | 0,026 | 0,010 | 0,084 | 0,100 | 0,088 | 0,029 | 0,152 | 0,050 | 300,742 | 0,278 | 0,147
10_10_10_2 | 300,052 | 1,093 | 0,159 | 0,098 | 0,228 | 0,106 | 0,176 | 1,072 | 0,148 | 300,326 | 2,394 | 0,412
20_20_20_2 | 300,169 | 72,279 | 4,340 | 0,035 | 1,685 | 0,199 | 2,265 | 25,130 | 0,806 | 302,469 | 99,094 | 5,346
2_10_10_2 | 300,767 | 0,103 | 0,043 | 0,102 | 0,203 | 0,111 | 0,118 | 0,710 | 0,130 | 300,987 | 1,016 | 0,283
2_5_5_2 | 260,024 | 0,022 | 0,011 | 0,100 | 0,116 | 0,101 | 0,046 | 0,173 | 0,055 | 260,170 | 0,311 | 0,167
${\mathcal{F}}_{2}$ | 10_10_10_1 | 102,145 | 0,137 | 0,132 | 0,141 | 0,108 | 0,087 | 0,432 | 0,146 | 0,088 | 102,718 | 0,391 | 0,308
20_20_20_1 | 311,688 | 4,922 | 4,596 | 0,882 | 0,358 | 0,117 | 9,657 | 0,600 | 0,291 | 322,228 | 5,879 | 5,004
3_10_3_1 | 31,109 | 0,013 | 0,014 | 0,103 | 0,084 | 0,085 | 0,079 | 0,046 | 0,030 | 31,291 | 0,143 | 0,128
3_5_3_1 | 0,298 | 0,006 | 0,008 | 0,086 | 0,081 | 0,080 | 0,042 | 0,043 | 0,026 | 0,427 | 0,129 | 0,113
20_20_20_2 | 302,046 | 4,701 | 8,235 | 0,844 | 0,350 | 0,114 | 9,204 | 0,550 | 0,244 | 312,094 | 5,600 | 8,593
10_10_10_2 | 168,211 | 0,148 | 0,216 | 0,146 | 0,112 | 0,089 | 0,459 | 0,149 | 0,087 | 168,816 | 0,409 | 0,392
3_10_3_2 | 12,291 | 0,016 | 0,045 | 0,090 | 0,083 | 0,083 | 0,056 | 0,044 | 0,027 | 12,437 | 0,142 | 0,155
3_5_3_2 | 0,130 | 0,007 | 0,015 | 0,088 | 0,080 | 0,082 | 0,035 | 0,044 | 0,026 | 0,252 | 0,131 | 0,122
${\mathcal{F}}_{3}$ | 10_10_10_1 | 300,266 | 0,247 | 0,116 | 0,102 | 0,216 | 0,097 | 0,221 | 1,294 | 0,056 | 300,589 | 1,758 | 0,269
20_20_20_1 | 300,395 | 6,348 | 4,149 | 0,190 | 1,554 | 0,178 | 3,291 | 31,444 | 0,256 | 303,876 | 39,346 | 4,583
10_3_10_1 | 300,270 | 0,062 | 0,027 | 0,099 | 0,193 | 0,092 | 0,134 | 0,940 | 0,050 | 300,503 | 1,194 | 0,169
5_3_5_1 | 300,432 | 0,014 | 0,008 | 0,100 | 0,121 | 0,092 | 0,032 | 0,188 | 0,027 | 300,564 | 0,324 | 0,127
10_10_10_2 | 300,194 | 0,279 | 0,125 | 0,098 | 0,224 | 0,104 | 0,221 | 1,416 | 0,056 | 300,513 | 1,919 | 0,284
20_20_20_2 | 300,096 | 4,593 | 2,919 | 0,169 | 1,373 | 0,161 | 2,822 | 22,726 | 0,173 | 303,087 | 28,692 | 3,253
10_3_10_2 | 300,422 | 0,074 | 0,032 | 0,103 | 0,207 | 0,100 | 0,118 | 1,015 | 0,057 | 300,643 | 1,295 | 0,189
5_3_5_2 | 300,451 | 0,024 | 0,014 | 0,134 | 0,154 | 0,124 | 0,038 | 0,255 | 0,036 | 300,624 | 0,433 | 0,173
Table 2: Running times of the models

## References

  * [1] A. Berman and N. Shaked-Monderer.  Completely positive matrices.  World Scientific, 2003.
  * [2] I. Bomze and M. Gabl.  Interplay of non-convex quadratically constrained problems with adjustable robust optimization.  Mathematical Methods of Operations Research, 93:115–151, 2021.
  * [3] I. M. Bomze, M. Gabl, F. Maggioni, and G. C. Pflug.  Two-stage Stochastic Standard Quadratic Optimization.  European Journal of Operational Research, 299(1):21–34, 2022.
  * [4] S. Burer.  On the copositive representation of binary and continuous nonconvex quadratic programs.  Mathematical Programming, 120(2):479–495, 2009.
  * [5] S. Burer.  Copositive programming.  In Handbook on semidefinite, conic and polynomial optimization, pages 201–218. Springer, 2012.
  * [6] J. H. Drew and C. R. Johnson.  The completely positive and doubly nonnegative completion problems.  Linear and Multilinear Algebra, 44(1):85–92, 1998.
  * [7] G. Eichfelder and J. Povh.  On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets.  Optimization Letters, 7(6):1373–1386, 2013.
  * [8] L. Fan, H. G. Aghamolki, Z. Miao, and B. Zeng.  Achieving SDP Tightness Through SOCP Relaxation with Cycle-Based SDP Feasibility Constraints for AC OPF.  arXiv preprint arXiv:1804.05128, 2018.
  * [9] M. Fukuda, M. Kojima, K. Murota, and K. Nakata.  Exploiting sparsity in semidefinite programming via matrix completion I: General framework.  SIAM Journal on Optimization, 11(3):647–674, 2001.
  * [10] S. Kim, M. Kojima, and K.-C. Toh.  Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures.  Journal of Global Optimization, 77:513–541, 2020.
  * [11] S. Kim, M. Kojima, and K.-C. Toh.  A geometrical analysis on convex conic reformulations of quadratic and polynomial optimization problems.  SIAM Journal on Optimization, 30(2):1251–1273, 2020.
  * [12] K. Natarajan and C.-P. Teo.  On reduced semidefinite programs for second order moment bounds with applications.  Mathematical Programming, 161(1):487–518, 2017.
  * [13] D. Padmanabhan, K. Natarajan, and K. Murthy.  Exploiting partial correlations in distributionally robust optimization.  Mathematical Programming, 186(1):209–255, 2021.
  * [14] J. Sliwak, M. Anjos, L. Létocart, J. Maeght, and E. Traversi.  Improving clique decompositions of semidefinite relaxations for optimal power flow problems.  arXiv preprint arXiv:1912.09232, 2019.
  * [15] L. Vandenberghe and M. S. Andersen.  Chordal graphs and semidefinite optimization.  Foundations and Trends in Optimization, 1(4):241–433, 2015.