# Moment-SOS hierarchies for arrow-type polynomial matrix inequalities with applications to structural optimization

Marouan Handa, Marek Tyburec, Giovanni Fantuzzi, Victor Magron, Michal Kočvara

<figure><img src="image_1.png" /></figure>

To cite this version:

Marouan Handa, Marek Tyburec, Giovanni Fantuzzi, Victor Magron, Michal Kočvara. Moment-SOS hierarchies for arrow-type polynomial matrix inequalities with applications to structural optimization. 2025. hal-05240295

HAL Id: hal-05240295

https://laas.hal.science/hal-05240295v1

Preprint submitted on 4 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Moment-SOS hierarchies for arrow-type
polynomial matrix inequalities with applications to
structural optimization

Marouan Handa¹*, Marek Tyburec¹,², Giovanni Fantuzzi³,
Victor Magron⁴, Michal Kočvara¹,⁵

¹* Institute of Information Theory and Automation, Pod Vodárenskou
věží 4, Prague, 18208, Czech Republic.

² Faculty of Civil Engineering, Czech Technical University, Thákurova
7, Prague, 16629, Czech Republic.

³Department of Mathematics, FAU Erlangen-Nürnberg, Erlangen,
91058,Germany.

⁴LAAS-CNRS, 7 avenue du colonel Roche, Toulouse, 31400, France.

⁵School of Mathematics, University of Birmingham, B15 2TT,
Birmingham, 610101,UK.

*Corresponding author(s). E-mail(s): handa@utia.cas.cz;
Contributing authors: marek.tyburec@cvut.cz;
giovanni.fantuzzi@fau.de; vmagron@laas.fr; m.kocvara@bham.ac.uk;

Abstract

The Arrow Decomposition (AD) technique, initially introduced in Kočvara (2020), demonstrated superior scalability over the classical chordal decomposition in the context of Linear Matrix Inequalities (LMIs) if the matrix in question satisfied suitable assumptions. The primary objective of this paper is to extend the AD method to address Polynomial Optimization Problems (POPs) involving large-scale Polynomial Matrix Inequalities (PMIs), with the solution framework relying on moment-sum of square (mSOS) hierarchies. As a first step, we revisit the LMI case and weaken the conditions necessary for the key AD theorem presented in Kočvara (2020). This modification allows the method to be applied to a broader range of problems. Next, we propose a practical procedure that reduces the number of additional variables, drawing on physical interpretations often found in structural optimization applications. For the PMI case, we explore two distinct approaches to combine the AD technique with mSOS hierarchies. One
approach involves applying AD to the original POP before implementing the mSOS relaxation. The other approach applies AD directly to the mSOS relaxations of the POP. We establish convergence guarantees for both approaches and prove that theoretical properties extend to the polynomial case. Finally, we illustrate the significant computational advantages offered by the application of AD, particularly in the context of structural optimization problems.

**Keywords:** Arrow decomposition · Polynomial optimization · Polynomial matrix inequalities · Semidefinite programming · Structural optimization

**Mathematics Subject Classification (2020):** 74P05 · 90C23 · 90C22 · 65F50

# 1 Introduction

Global minimization of multivariate polynomials subject to polynomial inequalities (POP) is a fundamental mathematical optimization problem. While generally NP-hard, POPs can be solved using the moment-sum of squares (mSOS) hierarchy. Relying on representation of positive polynomials on basic semialgebraic sets [2], the mSOS hierarchy generates increasingly tighter linear semidefinite programming (SDP) relaxations of increasing size, and hence a non-decreasing sequence of lower bounds for POP. Under a mild assumption called the Archimedean assumption [3], these relaxations converge asymptotically to the global minimum of POP. In addition, the convergence often occurs generically in a finite number of steps [4].

However, the relaxations can result in large size of SDP matrices and thus the mSOS does not scale well for problems with large number of variables and/or for problems that require high relaxation degrees. To improve the scalability one can exploit sparsity in the monomial coefficients of involved polynomials, which leads to correlative sparsity [5], term sparsity [6, 7], their combination [8], and ideal sparsity [9]. For more general exploitation of symmetry invariance under finite groups, see [10]. For more details on correlative/term sparsity and their multiple applications, we refer the interested reader to the recent monograph [11]. Convergence rates for hierarchies exploiting correlative sparsity have been obtained in [12].

While POPs with scalar constraints are well studied, many applications require polynomial matrix inequalities (PMIs), i.e., matrices whose entries are multivariate polynomials (see [13–15]). Assuming that these matrices are dense, analogous convergent hierarchies to the scalar case were developed in [16] based on the representation of positive definite polynomial matrices [17]. As in the scalar case, scalability can be improved by exploiting the sparsity occurring in the polynomial nature of the PMI. This includes correlative sparsity and term sparsity as shown in the very recent works [18, 19]. Contrary to the scalar case, the PMI settings also allows one to exploit structural sparsity of the matrix entries through, e.g., chordal sparsity [20, 21].

As an alternative to chordal structural sparsity, the concept of arrow decomposition (AD) method has recently been developed to speed up the solution of problems subject to linear matrix inequalities (LMIs) with matrices having an arrow structure [1]. The arrow structure naturally appears in linear elliptic self-adjoint variational
problems discretized by finite elements. In these problems, the equilibrium equation
can be reformulated either as an LMI or as a PMI involving a positive semidefi-
nite stiffness matrix, which takes an arrow form due to the Schur complement [14].
Rather than requiring chordal sparsity of these LMIs, the AD method requires posi-
tive semidefiniteness of the top-left block and bottom-right block of the LMI, making
it particularly suitable for such problems by requiring fewer additional variables than
the classical chordal decomposition method. Thus, it maintains a better scalability of
the decomposed problems with a linear growth in complexity (CPU time vs number of
variables), unlike the chordal decomposition which typically scales worse than cubic.
In addition, in [1], a connection between AD method applied to topology optimiza-
tion problems and the domain decomposition method was provided. This connection
allows one, on the one hand, to physically interpret the additional variables. On the
other hand, techniques from domain decomposition can be directly used to formalize
the matrix decomposition of the LMI.

***Contribution and organization of the manuscript.***

So far, the AD method has been restricted to linear matrix inequality (LMI) prob-
lems, constrained to cases where both the top-left and bottom-right blocks of the
main matrix are positive definite. Furthermore, it has not been applicable to degen-
erate problems—that is, cases in which at least one of the decomposed matrices is
rank-deficient. This paper makes three main contributions. First, we extend arrow
decomposition to PMI problems. Second, we provide more general results for the lin-
ear case that allow one treatment of degenerate problems. Third, we demonstrate
significant computational benefits through applications in structural optimization.

The paper is structured as follows. We begin in Section 2 by introducing all
necessary definitions and notation and recalling the moment sum-of-squares method
for the PMI case. Section 3 is dedicated to the AD method in the linear case: We
present the AD method and extend the results from [1] by providing weaker con-
ditions for the applicability of the AD method. This allows for a proper treatment
of zero-stiffness design elements in topology optimization problems. Furthermore, we
demonstrate that AD typically leads to degenerate problems without an interior point,
i.e., violating Slater condition. To fix this, we propose a projection-based method to
postprocess resulting SDPs. Remarkably, this post-processing also reduces the number
of additional variables and the size of matrix inequalities.

In Section 4, we present our main results on extending AD theory to the PMI
case, combining it with the mSOS method. We first prove that, analogously to the
linear case, AD can be applied directly to POP problems ("prior to mSOS"). How-
ever, because this approach increases the number of variables in the polynomial basis,
it typically does not improve scalability. Its presentation is nonetheless insightful and
serves as a bridge to the subsequent approach. To address scalability, we show that
AD can also be applied at the relaxation level ("posterior to mSOS") and establish
a corresponding convergence result. In addition, we show that the decomposed relax-
ations conserve the post-processing results from the linear case. We finally show that
AD applied posterior to mSOS can be seen as special instance of AD applied prior to
mSOS, allowing to perform AD prior to mSOS without including additional variables in the polynomial basis while maintaining the same theoretical convergence.

Next, we apply the developed theory to topology optimization problems of frame structures. In particular, in Section 5, we present compliance and weight optimization problems in frame structure design and provide, through examples, a physical interpretation of the additional variables in the context of structural engineering as well as of the post-processing procedure. In Section 6, we provide numerical illustrations demonstrating the benefits of AD: reduced solution times and improved numerical accuracy of the SDP relaxation. Moreover, the detailed examples in Sections 5 and 6 aim to make the techniques presented in this paper more accessible to readers from the structural engineering community. Finally, we summarize our contributions and suggest directions for future research in Section 7.

# 2 Notations and background

In this section, we first introduce all the notations needed for this paper. We further provide the definition of polynomial optimization problems constrained by polynomial matrix inequalities (PMIs), followed by a brief overview of Lasserre's moment sum-of-squares (mSOS) hierarchy.

## 2.1 Notation and definitions

All the vectors considered in this paper are row vectors. For a given integer $n$, we denote by $[n]$ the set $\{1, \cdots, n\}$. We denote by $|B|$ the dimension of a given real square matrix $B$, i.e. if $B \in \mathbb{R}^{n \times n}$ then $|B| = n$. We use the same notation for vector lengths and set cardinalities. We denote by $(B)_{ij}$ the $(i, j)$th component of $B$. We denote by $0_{\mathbb{R}^{n \times m}}$ (resp. $I_{\mathbb{R}^{n}}$) the $n \times m$ zero matrix (resp. the identity matrix of size $n$). When the dimensions are clear, we simply use $0$ (resp. $I$). Let $\mathbb{S}^n$ be the space of $n \times n$ symmetric matrices and let $\mathcal{I} \subset [n]$. For $A \in \mathbb{S}^n$, we denote by $A_{\mathcal{I}}$ the sub-matrix of $A$ whose rows and columns are indexed by the elements in $\mathcal{I}$. We denote by $A^{\dagger}$ the Moore-Penrose inverse of $A$ [22, Lemma 14.1]. Recall that by definition we have $AA^{\dagger}A = A$ and $A^{\dagger}AA^{\dagger} = A^{\dagger}$. Given $A, B \in \mathbb{S}^n$, the notation $A \succeq B$ (resp. $A \succ B$) stands for $A - B$ being positive semidefinite (resp. definite). Given a vector $y \in \mathbb{R}^m$ and matrices $A_0, A_1, \dots, A_m$ a relation of the form $A_0 + \sum_{i=1}^m y_i A_i \succeq 0$ is called a Linear Matrix Inequality (LMI).

Let $A = [a_{ij}] \in \mathbb{R}^{n \times m}$ and $B = [b_{rs}] \in \mathbb{R}^{p \times q}$. The Kronecker product of $A$ and $B$, denoted as $A \otimes B$, is a matrix in $\mathbb{R}^{np \times mq}$, defined element-wise by: $(A \otimes B)_{uv} = a_{ij}b_{rs}$, such that $u = (i-1)p+r$ and $v = (j-1)q+s$, for $i \in [n], j \in [m], r \in [p],$ and $s \in [q]$. We recall here some key properties of the Kronecker product which will be used in this paper: $A \otimes (B+C) = A \otimes B + A \otimes C$, $(A \otimes B) \otimes C = A \otimes (B \otimes C)$, $(A \otimes B)(C \otimes D) = (AC) \otimes (BD)$, $(A \otimes B)^{\dagger} = A^{\dagger} \otimes B^{\dagger}$, $(A \otimes B)^T = A^T \otimes B^T$. Additionally, for $A \in \mathbb{R}^{n \times m}$ and $B \in \mathbb{R}^{p \times q}$, the Kronecker product can be expressed as: $A \otimes B = (I_n \otimes B)(A \otimes I_q) = (A \otimes I_p)(I_m \otimes B)$. We denote by $\text{Vec}$ the column-wise vectorization operator that transforms a matrix $A \in \mathbb{R}^{n \times m}$ into a vector $\text{Vec}(A) \in \mathbb{R}^{nm \times 1}$ by stacking the columns $A$ on top of each other. We recall the following property of vectorization operator with Kronecker product: $\text{Vec}(ABC) = (C^T \otimes A)\text{Vec}(B)$.
Further, let $\boldsymbol{x} \in \mathbb{R}^{n_x}$. A real matrix polynomial $\boldsymbol{G}$ in the variable $\boldsymbol{x}$ is a matrix function of the form $\boldsymbol{G}(\boldsymbol{x}) = \sum_{\boldsymbol{\alpha} \in \mathbb{N}^{n_x}} \boldsymbol{G}_{\boldsymbol{\alpha}} \boldsymbol{x}^{\boldsymbol{\alpha}}$, with each $\boldsymbol{G}_{\boldsymbol{\alpha}} \in \mathbb{R}^{n \times m}$. Moreover, we denote by $\mathbb{R}[\boldsymbol{x}] := \{\sum_{\boldsymbol{\alpha} \in \mathbb{N}^{n_x}} g_{\boldsymbol{\alpha}} \boldsymbol{x}^{\boldsymbol{\alpha}} : g_{\boldsymbol{\alpha}} \in \mathbb{R}\}$ the set of scalar real valued polynomials, by $\mathbb{R}^{n \times m}[\boldsymbol{x}] := \{\sum_{\boldsymbol{\alpha} \in \mathbb{N}^{n_x}} \boldsymbol{G}_{\boldsymbol{\alpha}} \boldsymbol{x}^{\boldsymbol{\alpha}} : \boldsymbol{G}_{\boldsymbol{\alpha}} \in \mathbb{R}^{n \times m}\}$ the set of polynomial matrices of size $n \times m$, by $\mathbb{S}^n[\boldsymbol{x}] := \{\sum_{\boldsymbol{\alpha} \in \mathbb{N}^{n_x}} \boldsymbol{G}_{\boldsymbol{\alpha}} \boldsymbol{x}^{\boldsymbol{\alpha}} : \boldsymbol{G}_{\boldsymbol{\alpha}} \in \mathbb{S}^n\}$ the set of symmetric polynomial matrices of size $n$, by $\mathbb{N}_d^{n_x} := \{\boldsymbol{\alpha} \in \mathbb{N}^{n_x} : \sum_i \alpha_i \le d\}$ the set of $n_x$-tuples of natural numbers for which the sum is bounded by a degree $d$, by $\mathbb{R}[\boldsymbol{x}]_d := \{\sum_{\boldsymbol{\alpha} \in \mathbb{N}_d^{n_x}} g_{\boldsymbol{\alpha}} \boldsymbol{x}^{\boldsymbol{\alpha}} : g_{\boldsymbol{\alpha}} \in \mathbb{R}\}$ the set of scalar polynomials of degree at most $d$, by $\mathbb{S}^n[\boldsymbol{x}]_d := \{\sum_{\boldsymbol{\alpha} \in \mathbb{N}_d^{n_x}} \boldsymbol{G}_{\boldsymbol{\alpha}} \boldsymbol{x}^{\boldsymbol{\alpha}} : \boldsymbol{G}_{\boldsymbol{\alpha}} \in \mathbb{S}^n\}$, the set of symmetric polynomial matrices of size $n$ and of degree at most $d$. A relation of the form $\boldsymbol{G}(\boldsymbol{x}) \ge 0$ where $\boldsymbol{G} \in \mathbb{S}^n[\boldsymbol{x}]$ is called a *Polynomial Matrix Inequality* (PMI).

We say that a sequence $\boldsymbol{y} = (y_\alpha)_{\alpha \in \mathbb{N}^{n_x}}$ has a representing measure if there exists a finite Borel measure $\mu$ supported on $\mathcal{K} \subset \mathbb{R}^{n_x}$ such that $y_\alpha = \int_{\mathcal{K}} \boldsymbol{x}^{\boldsymbol{\alpha}} d\mu$ for all $\boldsymbol{\alpha} \in \mathbb{N}^{n_x}$. In this case we say that $\boldsymbol{y}$ is a sequence of moments. For $\boldsymbol{x} \in \mathbb{R}^{n_x}$, we denote by $\boldsymbol{b}_d(\boldsymbol{x})$ the standard monomial basis of the vector space $\mathbb{R}[\boldsymbol{x}]_d$, i.e.

$$ \boldsymbol{b}_d(\boldsymbol{x}) = (\boldsymbol{x}^{\boldsymbol{\alpha}})_{\alpha \in \mathbb{N}_d^{n_x}} = (1 \ x_1 \ x_2 \ \dots \ x_1^2 \ x_1x_2 \ \dots \ x_1^d \ \dots \ x_n^d). $$

Let $\boldsymbol{y} = (y_\alpha)_{\alpha \in \mathbb{N}^{n_x}}$, $p(\boldsymbol{x}) = \sum_{\boldsymbol{\alpha} \in \mathbb{N}^{n_x}} p_\alpha \boldsymbol{x}^{\boldsymbol{\alpha}} \in \mathbb{R}[\boldsymbol{x}]$ and $\boldsymbol{G}(\boldsymbol{x}) = \sum_{\boldsymbol{\alpha} \in \mathbb{N}^{n_x}} \boldsymbol{G}_\alpha \boldsymbol{x}^{\boldsymbol{\alpha}} \in \mathbb{S}[\boldsymbol{x}]$. Let us further define the linear operator $\mathcal{L}_y(p) := \sum_{\boldsymbol{\alpha} \in \mathbb{N}^{n_x}} p_\alpha y_\alpha$. In general, for any $\boldsymbol{P} \in \mathbb{R}^{n \times m}[\boldsymbol{x}]$, $\mathcal{L}_y(\boldsymbol{P}(\boldsymbol{x}))$ is applied entry-wise on the matrix $\boldsymbol{P}(\boldsymbol{x})$. Moreover, we define

* the $d$-th order pseudo-moment matrix associated with $\boldsymbol{y}$ by

$$ \boldsymbol{M}_d(\boldsymbol{y}) = \mathcal{L}_y (\boldsymbol{b}_d(\boldsymbol{x})^T \boldsymbol{b}_d(\boldsymbol{x})) = (y_{\alpha+\beta})_{\alpha,\beta}; $$

* the $d$-th order localizing matrix $^1$ associated with $\boldsymbol{y}$ and $\boldsymbol{G}$ by

$$ \boldsymbol{M}_d(\boldsymbol{G}\boldsymbol{y}) = \mathcal{L}_y (\boldsymbol{G}(\boldsymbol{x}) \otimes \boldsymbol{b}_d(\boldsymbol{x})^T \boldsymbol{b}_d(\boldsymbol{x})) = \left( \sum_{\gamma \in \mathbb{N}_s^n} y_{\alpha+\beta+\gamma} \boldsymbol{G}_\gamma \right)_{\alpha,\beta}. $$

## 2.2 The moment sum-of-squares hierarchy

We consider the following polynomial optimization problem (POP)

$$ p^* = \min_{\boldsymbol{x} \in \mathcal{K}} p(\boldsymbol{x}), \qquad (\text{POP}) $$

where $p \in \mathbb{R}[\boldsymbol{x}]_d$, $\boldsymbol{G} \in \mathbb{S}^s[\boldsymbol{x}]_{d_G}$ and $\mathcal{K} := \{\boldsymbol{x} \in \mathbb{R}^{n_x} : \boldsymbol{G}(\boldsymbol{x}) \ge 0\}$ is a compact set. Notice that this setting does not limit itself to a single constraint: a collection of constraints $\boldsymbol{G}_j(\boldsymbol{x}) \ge 0, j \in [m]$, can be concatenated into a single constraint $\boldsymbol{G}(\boldsymbol{x}) \ge 0$ by forming a block diagonal matrix $\boldsymbol{G}(\boldsymbol{x}) = \text{diag}(\boldsymbol{G}_1(\boldsymbol{x}), \dots, \boldsymbol{G}_m(\boldsymbol{x}))$. On the other hand, for $s = 1$, $\boldsymbol{G}(\boldsymbol{x}) \ge 0$ constitutes a polynomial scalar inequality. Finally, here

<footnote n="1">¹Notice that $\boldsymbol{M}_d(\boldsymbol{G}\boldsymbol{y})$ is a block matrix.</footnote>
we consider the matrix $G$ in a general context, without assuming any specific arrow structure. The combination of mSOS with arrow type matrices will be discussed in Section 4.

Let $\mathcal{M}(\mathcal{K})$ be the space of finite signed Borel measures on $\mathcal{K}$, and let $\mathcal{M}(\mathcal{K})_+ \subset \mathcal{M}(\mathcal{K})$ denote the convex cone of nonnegative finite Borel measures on $\mathcal{K}$. If $p^*$ is a global minimum to (POP), then

$$ 
\begin{aligned}
p^* &= \inf_{\mu \in \mathcal{M}(\mathcal{K})_+} \int_{\mathcal{K}} p d\mu, \\
\text{s.t. } \mu(\mathcal{K}) &= 1.
\end{aligned} 
\quad (1) $$

One can write (1) in terms of the sequence $\mathbf{y}$ as

$$ 
\begin{aligned}
p^* &= \inf_{\mathbf{y}} \mathcal{L}_{\mathbf{y}}(p) \\
\text{s.t. } \mathbf{y}_0 &= 1,
\end{aligned} 
\quad (2) $$
$\mathbf{y}$ has a representing measure $\mu$ on $\mathcal{K}$.

In practice, one can only solve finite dimensional truncations of (2). To show convergence of a sequence of truncations, let us first recall that a matrix $G \in \mathbb{S}^s[x]$ is sum-of-squares (SOS) if there exists $H \in \mathbb{R}^{s \times l}[x]$ such that $G(x) = H(x)H(x)^T$. Further, let us assume the following algebraic compactness condition:

**Assumption 1** (Archimedean condition). There exist an SOS polynomial $p_0: \mathbb{R}^{n_x} \to \mathbb{R}$ and a matrix SOS polynomial $R: \mathbb{R}^{n_x} \to \mathbb{S}^N$ such that the set $\{x \in \mathbb{R}^n: p_0(x) + \langle R(x), G(x) \rangle \ge 0\}$ is compact.

For this setting, the following convergence result then holds:

**Theorem 1** (Dual facet of Putinar's Positivstellensatz [23, Theorem 2.44]). If Assumption 1 holds, then the sequence $\mathbf{y} = (y_\alpha)_{\alpha \in \mathbb{N}^{n_x}}$ has a representing measure $\mu$ supported on $\mathcal{K}$ if and only if

$$ M_d(\mathbf{y}) \ge 0 \text{ and } M_d(G\mathbf{y}) \ge 0, \forall d \in \mathbb{N}. \quad (3) $$

Hence, we obtain the following equivalent infinite-dimensional linear program

$$ 
\begin{aligned}
p^* &= \inf_{\mathbf{y}} \mathcal{L}_{\mathbf{y}}(p) \\
\text{s.t. } \mathbf{y}_0 &= 1, \\
M_d(\mathbf{y}) &\ge 0, \forall d \in \mathbb{N}, \\
M_d(G\mathbf{y}) &\ge 0, \forall d \in \mathbb{N}.
\end{aligned} 
\quad (4) $$
Let $d_p = \deg(p)$, $d_G = \deg(G)$, $r_G = \lceil \frac{d_G}{2} \rceil$ and $r \ge r_{\min} := \max(r_G, \lceil \frac{d_p}{2} \rceil)$. The hierarchy of its finite-dimensional truncations then reads as

$$
\begin{array}{ll}
p_r = \inf_{\mathbf{y} \in \mathbb{R}^{|b_{2r}(\boldsymbol{x})|}} \mathcal{L}_{\mathbf{y}}(p) & \\
\text{s.t. } \mathbf{y}_0 = 1, & \text{(mSOS)} \\
\mathbf{M}_r(\mathbf{y}) \succeq 0, & \\
\mathbf{M}_{r-r_G}(\mathbf{G}\mathbf{y}) \succeq 0 &
\end{array}
$$

and is controlled by the relaxation order $r \in \mathbb{N}$. The problem (mSOS) is called Lasserre moment sum-of-squares hierarchy. By solving (mSOS) for a sequence of increasing relaxation orders, we obtain a non-decreasing sequence of lower bounds to (POP).

**Theorem 2** ([16, Theorem 2.2]). Under Assumption 1, we have $p_r \le p_{r+1} \le \dots \le p^*$ and $\lim_{r \to \infty} p_r = p^*$

As stated in [16], Assumption 1 is not very restrictive: it suffices that one of the constraints of problem (POP) is of the form $\rho^2 - \|\mathbf{x}\|^2 \ge 0$ with a suitable $\rho \in \mathbb{R}$. If this is not the case, it can be added as a redundant constraint by choosing $\rho$ so that it does not affect the solution of the problem (POP). Finite convergence occurs when the rank of the pseudo-moment matrix stabilizes [24], i.e.,

$$ \mathrm{Rank}(\mathbf{M}_r(\mathbf{y}^*)) = \mathrm{Rank}(\mathbf{M}_{r-r_G}(\mathbf{y}^*)), \quad (5) $$

where $\mathbf{y}^*$ is a solution to (mSOS) at a fixed $r$. Based on this flatness condition, one can extract from (mSOS) $\tau = \mathrm{Rank}(\mathbf{M}_r(\mathbf{y}^*))$ distinct global minimizers of the problem (POP) using a linear algebra routine detailed in [25]. Depending on the nature of the problem, one can also have other types of conditions for finite convergence, see for instance [26], or [14, 27, 28] for conditions developed particularly for topology optimization problems.

### 3 The arrow decomposition method

We start this section by recalling the notion of a so-called arrow-type matrix

$$ \mathbf{G} = \begin{bmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{B}^T & \Gamma \end{bmatrix}, \qquad (6) $$

in which $\mathbf{A} \in \mathbb{S}^n$, $\mathbf{\Gamma} \in \mathbb{S}^m$, and $\mathbf{B} \in \mathbb{R}^{n \times m}$ and where

$$ \mathbf{A} = \sum_{k=1}^{p} \mathbf{A}_k \quad \text{and} \quad \mathbf{A}_k \in \mathbb{S}^n, \forall k \in [p]. \qquad (7) $$

Further, let $\mathcal{I} := [n]$ denote the row/column index set of $\mathbf{A}$ and let $(\mathcal{I}_k)_{k \in [p]}$ be a partition of the set $\mathcal{I}$, where $\mathcal{I}_k$ corresponds to the index set of the non-zero rows and
columns of $\mathbf{A}_k$. For example, if

$$ \mathbf{A} = \mathbf{A}_1 + \mathbf{A}_2 = \begin{bmatrix} 2 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix}, $$

we have $\mathcal{I} = \{1, 2, 3\}$, $\mathcal{I}_1 = \{1, 2\}$, and $\mathcal{I}_2 = \{2, 3\}$.

Now, for each subset $\mathcal{I}_k$, we define a matrix $\mathcal{E}_{\mathcal{I}_k} \in \mathbb{R}^{|\mathcal{I}_k| \times n}$ as

$$ (\mathcal{E}_{\mathcal{I}_k})_{ij} = \begin{cases} 1, & \text{if } \mathcal{I}_k(i) = j, \\ 0, & \text{otherwise,} \end{cases} $$

where the notation $\mathcal{I}_k(i)$ stands for the i-th element of $\mathcal{I}_k$. This definition allows a compact representation of a sparse matrix. For example, for the matrix $\mathbf{A}_1$ defined above, we have $\mathcal{E}_{\mathcal{I}_1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$ and $\mathbf{A}_1 = \mathcal{E}_{\mathcal{I}_1}^T \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix} \mathcal{E}_{\mathcal{I}_1}$.

In what follows, we denote the intersection of the sets $\mathcal{I}_k$ and $\mathcal{I}_\ell$ by $\mathcal{I}_{k,\ell} = \mathcal{I}_k \cap \mathcal{I}_\ell$ with $k, \ell \in [p]$ and $k < \ell$.

Using the index sets $\mathcal{I}_k$ related to the matrices $\mathbf{A}_k$, let us now decompose a rectangular matrix $\mathbf{B} \in \mathbb{R}^{n \times m}$ as

$$ \mathbf{B} = \sum_{k=1}^{p} \mathbf{B}_k \text{ and } \mathbf{B}_k \in \mathbb{R}^{n \times m}, \forall k \in [p], \quad (8) $$

such that $(\mathbf{B}_k)_{ij} = 0$ for $i \notin \mathcal{I}_k$.

Then, the so-called arrow type matrix $\mathbf{G} \in \mathbb{S}^{n+m}$ reads as

$$ \mathbf{G} = \begin{bmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{B}^T & \mathbf{\Gamma} \end{bmatrix} = \sum_{i=1}^{p} \mathbf{G}_k + \begin{bmatrix} \mathbf{0} & \mathbf{0} \\ \mathbf{0} & \mathbf{\Gamma} \end{bmatrix} \quad \text{where} \quad \mathbf{G}_k = \begin{bmatrix} \mathbf{A}_k & \mathbf{B}_k \\ \mathbf{B}_k^T & \mathbf{0} \end{bmatrix}, k \in [p] \quad (9) $$

with $\mathbf{\Gamma} \in \mathbb{S}^m$. By definition, we have

$$ (\mathbf{G}_k)_{ij} = 0 \text{ for } (i, j) \notin \mathcal{I}_k \cup \{n+1, \dots, n+m\}, k \in [p]. \quad (10) $$

In the following, we aim to replace the condition $\mathbf{G} \succeq 0$ with a set of LMIs $\mathbf{G}_k \succeq 0$ where each $\mathbf{G}_k$ is potentially of reduced size (see Section 3.1). In general, the matrix $\mathbf{G}$, even when endowed with the arrow structure described above, can only be decomposed using classical chordal sparsity graph techniques (see [29, 30]). To enable the arrow decomposition technique, we introduce the following assumption on the matrices $\mathbf{A}_k$ and $\mathbf{\Gamma}$:

**Assumption 2 (Positive semidefiniteness).** $\mathbf{A}_k \succeq 0, \forall k \in [p]$ and $\mathbf{\Gamma} \succeq 0$.
Before stating the result allowing for an arrow decomposition of the matrix $G$, let us first recall the generalized Schur complement for positive semidefinite (PSD) matrices.

**Lemma 1** ([22], Theorem 16.1). Let $A \in \mathbb{S}^n$, $\Gamma \in \mathbb{S}^m$, and $B \in \mathbb{R}^{n \times m}$. Then, the following conditions are equivalent:

• $\begin{bmatrix} A & B \\ B^T & \Gamma \end{bmatrix} \succeq 0$,

• $A \succeq 0$, $\Gamma - B^T A^\dagger B \succeq 0$, $AA^\dagger B = B$.

The following theorem ensures that we can replace an LMI involving arrow type matrices by smaller LMIs at the cost of introducing additional variables.

**Theorem 3.** Let $G$ be a matrix defined as in (9). Suppose that Assumption 2 holds. Then the following statements are equivalent:

• $G \succeq 0$

• there exist matrices $D_{k,\ell} \in \mathbb{R}^{n \times m}$ such that $(D_{k,\ell})_{ij} = 0$ whenever $(i,j) \notin \mathcal{I}_{k,\ell} \times [m], k < \ell$, and symmetric matrices $(C_k)_{k \in [p]}$, such that $G = \sum_{k=1}^p \tilde{G}_k(D_k, C_k)$, and

$$ \tilde{G}_k(D_k, C_k) = G_k + \begin{bmatrix} 0 & D_k \\ D_k^T & C_k \end{bmatrix} \succeq 0, k \in [p], \quad (11) $$

where

$$ D_k = - \sum_{\ell: \ell < k} D_{\ell,k} + \sum_{\ell: \ell > k} D_{k,\ell}, \quad (12) $$

$$ \sum_{k=1}^{p} C_k = \Gamma, \quad (13) $$

**Remark 1.** To keep notation simple, in the rest of this paper we will omit the dependency of the matrices $\tilde{G}_k$ on the additional variables $D_k$ and $C_k$, and will write $\tilde{G}_k := \tilde{G}_k(D_k, C_k)$.

Theorem 3 generalizes [1, Theorem 3] where the assumptions $A \succ 0$ and $\Gamma \succ 0$ where needed. These requirements, however, can be restrictive in certain applications, such as structural optimization (see Section 5). Although the proof of Theorem 3 closely follows that of [1, Theorem 3], we provide it here explicitly for the reader's convenience.

*Proof* Suppose that $G \succeq 0$. We will construct the matrices $D_{k,\ell}$ and $C_k$ that satisfy the conditions stated in the theorem. To this goal, let us first define $X = A^\dagger B$. According to Lemma 1, we have $AA^\dagger B = B$ so that

$$ \sum_{k=1}^{p} A_k X = \sum_{k=1}^{p} B_k. \quad (14) $$
Thus, the entries of $A_k X$ corresponding to row indices in $\mathcal{I}_k$ that do not appear in any intersection with other index sets are uniquely determined. Specifically, for all $j \in [p]$ and $i \in \mathcal{I}_k \setminus (\bigcup_{\ell: \ell > k} (\mathcal{I}_{k, \ell}) \cup \bigcup_{\ell: \ell < k} (\mathcal{I}_{\ell, k}))$, we have

$$ (A_k X)_{ij} = (B_k)_{ij}. \qquad (15) $$

For each $k \in [p-1]$, we define successively $D_{k, \ell}$ such that $\ell > k$, by selecting a solution of the equation

$$ A_k X - B_k = - \sum_{\substack{\ell: \ell < k \\ \mathcal{I}_{\ell, k} \neq \emptyset}} D_{\ell, k} + \sum_{\substack{\ell: \ell > k \\ \mathcal{I}_{k, \ell} \neq \emptyset}} D_{k, \ell}. \qquad (16) $$

The solutions of (16) are obviously not unique, however any selected solution $D_{k, \ell}$ is consistent with the last equation

$$ A_p X - B_p = - \sum_{\substack{\ell: \ell < p \\ \mathcal{I}_{\ell, p} \neq \emptyset}} D_{\ell, p}, $$

because of Equality (14). Moreover, by (10) and (15), each $(D_{k, \ell})_{ij} = 0$ when $(i, j) \notin \mathcal{I}_{k, \ell} \times [m]$ as desired.

Next, let us define $C_k = S + X^T A_k X$, $k \in [p]$, where $S = \frac{1}{p}(\Gamma - X^T B)$. We have $\sum_{k=1}^p C_k = pS + X^T (\sum_{k=1}^p A_k) X = \Gamma - X^T B + X^T A X = \Gamma$.

Moreover, we have

$$ \begin{aligned} \tilde{G}_k &= G_k - \sum_{\substack{\ell: \ell < k \\ \mathcal{I}_{\ell, k} \neq \emptyset}} \begin{bmatrix} \mathbf{0} & D_{\ell, k} \\ D_{\ell, k}^T & \mathbf{0} \end{bmatrix} + \sum_{\substack{\ell: \ell > k \\ \mathcal{I}_{k, \ell} \neq \emptyset}} \begin{bmatrix} \mathbf{0} & D_{k, \ell} \\ D_{k, \ell}^T & \mathbf{0} \end{bmatrix} + \begin{bmatrix} \mathbf{0} & \mathbf{0} \\ \mathbf{0} & C_k \end{bmatrix} \\ &= \begin{bmatrix} A_k & A_k X \\ X^T A_k^T & X^T A_k X + S \end{bmatrix}. \end{aligned} $$

Since $A_k \succeq 0$ by assumption, we conclude that $\tilde{G}_k \succeq 0$ by using Lemma 1.

The reversed assertion holds by summing over $k$ the PSD matrices $\tilde{G}_k$. $\square$

<figure><img src="image_3.png" /></figure>

Practically, the conditions (12) and (13) will not be defined explicitly as in the proof of Theorem 3. Instead, the matrices $D_{k, \ell}$ and $C_k$ are determined numerically via semidefinite programming, such that the constraints (12) and (13) are embedded directly into the formulation (11) as

$$ \begin{aligned} & G_k + \begin{bmatrix} \mathbf{0} & -\sum_{\ell: \ell < k} D_{\ell, k} + \sum_{\ell: \ell > k} D_{k, \ell} \\ -\sum_{\ell: \ell < k} D_{\ell, k}^T + \sum_{\ell: \ell > k} D_{k, \ell} & C_k \end{bmatrix} \succeq 0, \forall k \in [p-1], \\ & G_p + \begin{bmatrix} \mathbf{0} & -\sum_{\ell: \ell < k} D_{\ell, p}^T \Gamma - \sum_{k=1}^p C_k \\ -\sum_{\ell: \ell < k} D_{\ell, p}^T \Gamma + \sum_{k=1}^p C_k & C_k \end{bmatrix} \succeq 0. \end{aligned} \qquad (17) $$

Let us notice that the choice of the decomposed matrices $B_k$ is not unique. There is complete freedom in selecting them, as the positive semidefiniteness of $\tilde{G}_k$ can always be ensured by appropriately choosing the matrices $D_{k, \ell}$. Similarly, the parametrization of the blocks $C_k$ is not unique, as any parametrization satisfying $\sum_{k=1}^p C_k = \Gamma$ is valid.

For clarity and consistency, we adopt the compact formulation (17) in the sequel.
**Example 1.** Let $G = \begin{bmatrix} A & B \\ B^T & \gamma \end{bmatrix}$, where

$$A = \begin{bmatrix} 2a_1 + a_2 & a_1 & a_1 + a_2 & a_2 & 0 \\ a_1 & 2a_1 & a_1 & 0 & 0 \\ a_1 + a_2 & a_1 & a_1 + a_2 & a_2 & 0 \\ a_2 & 0 & a_2 & a_2 + a_3 & a_3 \\ 0 & 0 & 0 & a_3 & 2a_3 \end{bmatrix},$$

$B = [b_1 \ b_2 \ b_3 \ b_4 \ b_5]^T$, with $a_1, a_2, a_3, \gamma \in \mathbb{R}_{>0}$ and $b_1, b_2, b_3, b_4, b_5 \in \mathbb{R}$. Using the index subsets $\mathcal{I}_1 = \{1, 2, 3\}$, $\mathcal{I}_2 = \{1, 3, 4\}$ and $\mathcal{I}_3 = \{4, 5\}$, we can extract from $A$ the corresponding PSD matrices:

$$A_1 = a_1 \mathcal{E}_{\mathcal{I}_1}^T \begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 1 \end{bmatrix}, \quad A_2 = a_2 \mathcal{E}_{\mathcal{I}_2}^T \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}, \quad A_3 = a_3 \mathcal{E}_{\mathcal{I}_3}^T \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}, \quad \mathcal{E}_{\mathcal{I}_1}, \mathcal{E}_{\mathcal{I}_2}, \mathcal{E}_{\mathcal{I}_3}$$

The intersections of the index subsets are $\mathcal{I}_{1,2} = \{1,3\}$, $\mathcal{I}_{1,3} = \emptyset$ and $\mathcal{I}_{2,3} = \{4\}$. According to the index subsets, we choose $B_1 = \mathcal{E}_{\mathcal{I}_1}^T [b_1 \ b_2 \ b_3]^T$, $B_2 = \mathcal{E}_{\mathcal{I}_2}^T [0 \ 0 \ b_4]^T$, and $B_3 = [0 \ b_5]^T$. In contrast, $D_1 = D_{1,2} = \mathcal{E}_{\mathcal{I}_1}^T [d_{1,2}^{(1)} \ 0 \ d_{1,2}^{(2)}]^T$, $D_2 = -D_{1,2} + D_{2,3} = \mathcal{E}_{\mathcal{I}_2}^T [-d_{1,2}^{(1)} - d_{1,2}^{(2)} \ d_{2,3}^{(1)}]^T$ and $D_3 = -D_{2,3} = \mathcal{E}_{\mathcal{I}_2}^T [-d_{2,3}^{(1)} \ 0]^T$ are unique, with the notation $d_{k,l}^{(i)}$ expressing that it is an i-th unknown component of the $D_{k,l}$ matrix. Using Theorem 3, we can find $d_{1,2}^{(1)}, d_{1,2}^{(2)}, d_{2,3}^{(1)}, c_1$ and $c_2$ such that the condition $G \succeq 0$ is equivalent to

$$\hat{G}_1 = \begin{bmatrix} A_1 & B_1 + D_1 \\ B_1^T + D_1^T & c_1 \end{bmatrix} \succeq 0,$$

$$\hat{G}_2 = \begin{bmatrix} A_2 & B_2 + D_2 \\ B_2^T + D_2^T & c_2 \end{bmatrix} \succeq 0,$$

and

$$\hat{G}_3 = \begin{bmatrix} A_3 & B_3 + D_3 \\ B_3^T + D_3^T & \gamma - c_1 - c_2 \end{bmatrix} \succeq 0.$$

## 3.1 Computational considerations

We start this section by noting that, although not required for the validity of the theoretical results, certain structural properties of the index sets $\mathcal{I}_k$ and of the sub-matrices $A_k, B_k$ tend to improve numerical performance. In particular, the following properties help reduce the size of the decomposed matrices $\hat{G}_k$ and limit the number of additional variables introduced during decomposition:

* **Non-nesting subsets.** $\mathcal{I}_k \cup \mathcal{I}_l \neq \mathcal{I}_k$, for all $1 \le k \ne l \le p$.

*Comment:* If this property fails, one matrix $A_1$ is contained as a submatrix in another $A_2$, leading to $|G| = |G_2|$ and the decomposition will have no computational advantage.
* **Sparse intersection.** For each $k \in [p]$, there are at most $p_k$ indices $\ell_i$ such that $\mathcal{I}_{k,\ell_i} \neq \emptyset$, $i \in [p_k]$ where $1 \le p_k \ll p$.

*Comment:* This limits the number of additional variables introduced when using the arrow decomposition technique. Unlike chordal decomposition methods which follow the chordal sparsity pattern and give little control over the number of extra variables [31], this property allows a more efficient decomposition. Unless the matrices $A_k$ are fully dense, it is generally possible to choose a decomposition satisfying this property.

Moreover, for each $k \in [p]$, at least one of the following properties should hold:

* **Sparse submatrices.** $A_k$ and $B_k$ are sparse.

*Comment:* This property clearly shrinks the size of $\hat{G}_k$ by removing the zero rows and columns, as seen in Example 1.

* **Low rank submatrices.** $A_k$ is low rank.

*Comment:* This property allows in one hand, to reduce the size $\hat{G}_k$ by adequate projection procedure, on the other hand, it allows to reduce the number of additional variables needed to parametrize $B_k+D_k$ while maintaining positive semidefiniteness of $\hat{G}_k$. It will be explained in more details in Proposition 1.

In practice, when decomposing the main matrix $G$, it is preferable to select a decomposition that satisfies as many of these properties as possible, thereby balancing matrix size reduction with computational efficiency.

Furthermore, as Example 1 revealed, it is convenient to maintain a component-wise representation of (12). To this end, we define $D_k = \Pi_k D$, where $D$ is a dense matrix formed by concatenating all entries of $D_k$ for every $k \in [p]$, and $\Pi_k$ is a binary (zero-one) matrix of appropriate dimensions that selects the relevant entries of $D$ corresponding to each $k \in [p]$. The existence of such a construction is established in Lemma 4 in Appendix A. This reformulation facilitates handling the component-wise relationship between $D_k$ and $D_{k,\ell}$ and also simplifies implementation.

**Example 2.** Consider the matrices $D_k$, $k \in \{1,2,3\}$, in Example 1. Let $D = [d_{1,2}^{(1)} d_{1,2}^{(2)} d_{2,3}^{(1)}]^T$. We can write $D_1 = \mathcal{E}_{\mathcal{I}_1}^T \Pi_1 D$, $D_2 = \mathcal{E}_{\mathcal{I}_2}^T \Pi_2 D$ and $D_3 = \mathcal{E}_{\mathcal{I}_3}^T \Pi_3 D$, in which

$$ \Pi_1 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}, \quad \Pi_2 = \begin{bmatrix} -1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad \Pi_3 = \begin{bmatrix} 0 & 0 & -1 \\ 0 & 0 & 0 \end{bmatrix}. $$

Now, when determining the additional matrix variables $D_k$ and $C_k$ via semidefinite programming, it often occurs that one or more matrices $A_k$ are rank-deficient. This implies that the constraint $\hat{G}_k \succeq 0$ may lack an interior point, potentially leading to numerical instability in interior-point methods. The following result offers a further refinement of the approach in [1]: it systematically removes potential rank deficiencies in the matrices $A_k$, yielding smaller LMIs that are equivalent to (11). Additionally, it provides conditions under which the resulting LMIs admit strict feasibility.
**Proposition 1.** Suppose that Assumption 2 holds. For each $k \in [p]$, let $\mathbf{P}_k \in \mathbb{R}^{n_k \times s_k}$, $s_k \le n_k$, be a matrix with full column rank such that $\mathbf{P}_k^T \mathbf{P}_k = \mathbf{I}_{s_k}$, $\text{Span}(\mathbf{A}_k) \subseteq \text{Span}(\mathbf{P}_k)$. The condition (11) is equivalent to the conditions

$$ 
\begin{gathered}
\begin{bmatrix} \mathbf{P}_k^T \mathbf{A}_k \mathbf{P}_k & \mathbf{P}_k^T (\mathbf{B}_k + \mathbf{D}_k) \\ (\mathbf{B}_k + \mathbf{D}_k)^T \mathbf{P}_k & \mathbf{C}_k \end{bmatrix} \ge 0, \forall k \in [p-1], \\
\begin{bmatrix} \mathbf{P}_p^T \mathbf{A}_p \mathbf{P}_p & \mathbf{P}_p^T (\mathbf{B}_p + \mathbf{D}_p) \\ (\mathbf{B}_p + \mathbf{D}_p)^T \mathbf{P}_k & \mathbf{\Gamma} - \sum_{k=1}^{p-1} \mathbf{C}_k \end{bmatrix} \ge 0, \\
\text{Span}(\mathbf{B}_k + \mathbf{D}_k) \subseteq \text{Span}(\mathbf{P}_k).
\end{gathered} 
\tag{18} $$

Moreover, if $\text{Span}(\mathbf{A}_k) = \text{Span}(\mathbf{P}_k)$ and $\mathbf{\Gamma} - \mathbf{B}^T \mathbf{A}^\dagger \mathbf{B} > 0$, then the above matrix inequalities in (18) are strict.

*Proof* Let $k \in [p]$ and define $\mathbf{D}_k$ as in (16). According to Theorem 3, it suffices to show that

$$ \begin{bmatrix} \mathbf{A}_k & (\mathbf{B}_k + \mathbf{D}_k) \\ (\mathbf{B}_k + \mathbf{D}_k)^T & \mathbf{C}_k \end{bmatrix} \ge 0 \Leftrightarrow \begin{bmatrix} \mathbf{P}_k^T \mathbf{A}_k \mathbf{P}_k & \mathbf{P}_k^T (\mathbf{B}_k + \mathbf{D}_k) \\ (\mathbf{B}_k + \mathbf{D}_k)^T \mathbf{P}_k & \mathbf{C}_k \end{bmatrix} \ge 0. $$

⇒ We have

$$ \begin{bmatrix} \mathbf{P}_k^T \mathbf{A}_k \mathbf{P}_k & \mathbf{P}_k^T (\mathbf{B}_k + \mathbf{D}_k) \\ (\mathbf{B}_k + \mathbf{D}_k)^T \mathbf{P}_k & \mathbf{C}_k \end{bmatrix} = \begin{bmatrix} \mathbf{P}_k & \mathbf{0} \\ \mathbf{0} & \mathbf{I} \end{bmatrix}^T \begin{bmatrix} \mathbf{A}_k & (\mathbf{B}_k + \mathbf{D}_k) \\ (\mathbf{B}_k + \mathbf{D}_k)^T & \mathbf{C}_k \end{bmatrix} \begin{bmatrix} \mathbf{P}_k & \mathbf{0} \\ \mathbf{0} & \mathbf{I} \end{bmatrix} \ge 0. $$

Moreover, we have $\text{Span}(\mathbf{B}_k + \mathbf{D}_k) \subseteq \text{Span}(\mathbf{A}_k)$ by Lemma 1, and thus $\text{Span}(\mathbf{B}_k + \mathbf{D}_k) \subseteq \text{Span}(\mathbf{P}_k)$ using the assumption on $\mathbf{P}_k$.

Let $\mathbf{u} \in \mathbb{R}^{n_k}$ and $\mathbf{v} \in \mathbb{R}^m$.

– If $\mathbf{u} \in \text{Span}(\mathbf{P}_k)$, there exists $\mathbf{w}$ such that $\mathbf{u} = \mathbf{P}_k \mathbf{w}$. Then, we have

$$ \begin{bmatrix} \mathbf{u} \\ \mathbf{v} \end{bmatrix}^T \begin{bmatrix} \mathbf{A}_k & (\mathbf{B}_k + \mathbf{D}_k) \\ (\mathbf{B}_k + \mathbf{D}_k)^T & \mathbf{C}_k \end{bmatrix} \begin{bmatrix} \mathbf{u} \\ \mathbf{v} \end{bmatrix} = \begin{bmatrix} \mathbf{w} \\ \mathbf{v} \end{bmatrix}^T \begin{bmatrix} \mathbf{P}_k^T \mathbf{A}_k \mathbf{P}_k & \mathbf{P}_k^T (\mathbf{B}_k + \mathbf{D}_k) \\ (\mathbf{B}_k + \mathbf{D}_k)^T \mathbf{P}_k & \mathbf{C}_k \end{bmatrix} \begin{bmatrix} \mathbf{w} \\ \mathbf{v} \end{bmatrix} \ge 0. $$

– if $\mathbf{u} \notin \text{Span}(\mathbf{P}_k)$ then $\mathbf{u} \notin \text{Span}(\mathbf{A}_k)$, so that $\mathbf{u}^T \mathbf{A}_k \mathbf{u} = 0$. Since $\text{Span}(\mathbf{B}_k + \mathbf{D}_k) \subseteq \text{Span}(\mathbf{P}_k)$, we have also $\mathbf{u}^T (\mathbf{B}_k + \mathbf{D}_k) \mathbf{v} = 0$. Thus, we have

$$ \begin{bmatrix} \mathbf{u} \\ \mathbf{v} \end{bmatrix}^T \begin{bmatrix} \mathbf{A}_k & (\mathbf{B}_k + \mathbf{D}_k) \\ (\mathbf{B}_k + \mathbf{D}_k)^T & \mathbf{C}_k \end{bmatrix} \begin{bmatrix} \mathbf{u} \\ \mathbf{v} \end{bmatrix} = \mathbf{v}^T \mathbf{C}_k \mathbf{v} \ge 0, \text{ by Assumption 2.} $$

Now, if $\text{Span}(\mathbf{A}_k) = \text{Span}(\mathbf{P}_k)$, we have $\mathbf{P}_k^T \mathbf{A}_k \mathbf{P}_k > 0$. Similarly to the proof of Theorem 3, we can define the matrices $\mathbf{D}_{k,l}$ so that it solves Equation (16), and $\mathbf{C}_k = \frac{1}{p} \mathbf{S} + \mathbf{X}^T \mathbf{A}_k \mathbf{X}$ with $\mathbf{X} = \mathbf{A}^\dagger \mathbf{B}$ and $\mathbf{S} = \mathbf{\Gamma} - \mathbf{B}^T \mathbf{A}^\dagger \mathbf{B}$. Using the assumption $\mathbf{S} > 0$ and Lemma 1, we conclude that

$$ \begin{bmatrix} \mathbf{A}_k & \mathbf{B}_k + \mathbf{D}_k \\ (\mathbf{B}_k + \mathbf{D}_k)^T & \mathbf{C}_k \end{bmatrix} \ge 0 \Leftrightarrow $$
$$ \begin{bmatrix} P_k^T A_k P_k & P_k^T (B_k + D_k) \\ (B_k + D_k)^T P_k & C_k \end{bmatrix} = \begin{bmatrix} P_k^T A_k P_k & P_k^T A_k X \\ X^T A_k^T P_k & X^T A_k X + S \end{bmatrix} > 0. $$

□

Proposition 1 is particularly useful when one of the matrices $A_k$ is rank-deficient for some $k \in [p]$. In such cases, by the spectral theory for positive semidefinite matrices, we can find a matrix $P_k \in \mathbb{R}^{s_k \times n_k}$ with $P_k^T P_k = I_{s_k}$, $\mathrm{Span}(A_k) \subseteq \mathrm{Span}(P_k)$ and $s_k < n_k$, to which we impose the condition $\mathrm{Span}(B_k + D_k) \subseteq \mathrm{Span}(P_k)$. This allows for a dimensionality reduction of one or more of the matrices involved the LMIs (18).

Moreover, since the condition $\mathrm{Span}(B_k + D_k) \subseteq \mathrm{Span}(P_k)$ is equivalent to $B_k + \Pi_k D \in \mathrm{Im}(P_k)$, it suffices to impose $B_k + \Pi_k D \in \mathrm{Im}(A_k)$. This constraint can be incorporated implicitly by reparameterizing $B_k + D_k$: choose a matrix $W_k$ such that $\mathrm{Span}(W_k) = \mathrm{Null}(A_k)$, and solve for $D$ the system

$$ \{(B_k + \Pi_k D)^T W_k = 0, k \in [p]\}. $$

This approach allows elimination of some (or all) entries of $D$ thereby improving numerical stability related to the interior point method while handling the LMI $\tilde{G}_k \succeq 0$; see, e.g., [32, Chapter 2].

**Remark 2.** If the matrix $\Gamma$ is rank-deficient, the same procedure can be applied by finding a matrix $P_\Gamma \in \mathbb{R}^{m \times s}$ with $s < m$, such that $P_\Gamma^T P_\Gamma = I_s$, $\mathrm{Span}(\Gamma) \subseteq \mathrm{Span}(P_\Gamma)$ and $\mathrm{Span}(B_k + D_k) \subseteq \mathrm{Span}(P_k)$. One can then work with the transformed matrices $P_\Gamma^T C_k P_\Gamma$ for all $k \in [p]$.

**Example 3.** Consider again the matrices from Example 1. We have $\mathrm{rank}(A_1) = 3$, $\mathrm{rank}(A_2) = 1$, and $\mathrm{rank}(A_3) = 2$. Therefore, while the null space bases of $A_1$, $A_2$ and $A_3$ respectively evaluate as

$$ W_1 = \begin{bmatrix} 0 & 0 \\ 0 & 0 \\ 0 & 0 \\ 1 & 0 \\ 0 & 1 \end{bmatrix}, \quad W_2 = \begin{bmatrix} 0 & -1 & -1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}, \quad W_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, $$

range space bases read as $P_1 = W_3$, $P_2 = \mathcal{E}_{\Gamma_2}^T [1 \ 1 \ 1]^T$ and $P_3 = W_1$.

Solving the system $\{(B_k + \Pi_k D)^T W_k = 0, k = 1, 2, 3\}$, we can reparameterize $D$ using a single variable $d_R^{(1)}$ as

$$ D = \begin{bmatrix} d_{1,2}^{(1)} \\ d_{1,2}^{(2)} \\ d_{2,3}^{(1)} \end{bmatrix} = \begin{bmatrix} -b_4/3 \\ -b_4/3 \\ -2b_4/3 \end{bmatrix} + \begin{bmatrix} -1 \\ -1 \\ 1 \end{bmatrix} d_R^{(1)}. $$
Finally, projection using the range space bases $P_k$ leads to the final matrix inequalities of decreased size,

$$ \begin{bmatrix} 2a_1 & a_1 & a_1 & b_1 - b_4/3 - d_R^{(1)} \\ a_1 & 2a_1 & a_1 & b_2 \\ a_1 & a_1 & a_1 & b_3 - b_4/3 - d_R^{(1)} \\ b_1 - b_4/3 - d_R^{(1)} & b_2 & b_3 - b_4/3 - d_R^{(1)} & c_1 \end{bmatrix} \succeq 0, $$

$$ \begin{bmatrix} 9a_2 & b_4 + 3d_R^{(1)} \\ b_4 + 3d_R^{(1)} & c_2 \end{bmatrix} \succeq 0, \quad \begin{bmatrix} a_3 & a_3 & 2b_4/3 - d_R^{(1)} \\ a_3 & 2a_3 & b_5 \\ 2b_4/3 - d_R^{(1)} & b_5 & \gamma - c_1 - c_2 \end{bmatrix} \succeq 0. $$

# 4 Arrow decomposition and the moment sum-of-squares hierarchy

This section is devoted to exploiting arrow-type structure in polynomial optimization problems. Thus, in what follows, we consider the optimization problem defined in (POP) such that $G \in \mathbb{S}^{n+m}[\mathbf{x}]$ has an arrow shape, i.e.,

$$ G(\mathbf{x}) = \sum_{k=1}^{p} G_k(\mathbf{x}) + \begin{bmatrix} \mathbf{0} & \mathbf{0} \\ \mathbf{0} & \Gamma(\mathbf{x}) \end{bmatrix}, \quad (19) $$

where for all $k \in [p]$, $G_k(\mathbf{x}) = \begin{bmatrix} A_k(\mathbf{x}) & B_k(\mathbf{x}) \\ B_k(\mathbf{x})^T & \mathbf{0} \end{bmatrix}$ with $A_k(\mathbf{x}) \in \mathbb{S}^n[\mathbf{x}]$, $B_k(\mathbf{x}) \in \mathbb{R}^{n \times m}[\mathbf{x}]$, and $\Gamma(\mathbf{x}) \in \mathbb{S}^m[\mathbf{x}]$. Similarly to Section 3, we make the following assumption on the matrices $A_k(\mathbf{x})$ and $\Gamma(\mathbf{x})$:

**Assumption 3 (Positive semidefiniteness).** For all $\mathbf{x} \in \mathcal{K}$ and $k \in [p]$, $A_k(\mathbf{x}) \succeq 0$ and $\Gamma(\mathbf{x}) \succeq 0$.

In this section, we present two different approaches for combining the mSOS and AD method:

* AD prior to the mSOS hierarchy (Section 4.1): AD is applied directly to the original polynomial optimization problem. Although this approach has little practical interest, we include it as it provides an insightful link between the main POP and the second approach.

* AD posterior to the mSOS hierarchy (Section 4.2): AD is applied to the relaxations within the mSOS hierarchy. This is the main focus of the paper.

## 4.1 AD prior to the mSOS hierarchy

First, notice that it follows from the proof of Theorem 3 that if, for all $\mathbf{x}$, the matrix $G(\mathbf{x})$ satisfies the assumptions for which Theorem 3 holds, then the additional matrices $D_k$ and $C_k$ can be expressed as rational functions in $\mathbf{x}$. Indeed, from Equation (16),
we would need to find a matrix $D$ such that $D_k = A_k(x)A(x)^\dagger B(x) - B_k(x)$ for all $k \in [p]$. However, this can not be exploited easily, because we would need to symbolically evaluate $A(x)^\dagger B(x)$. Instead, we introduce linear variables and require that their values match the fractional expressions at the optimum solution $x^*$ of Problem (POP). More specifically, set $C = \{C_k\}_{k \in [p-1]}$ and consider the following problem

$$p_{AD} = \inf_{x, D, C} p(x), \\ \text{s.t. } G_k(x) + \begin{pmatrix} 0 & \Pi_k D \\ D^T \Pi_k^T & C_k \end{pmatrix} \ge 0, \quad k \in [p-1], \qquad (\text{POP-AD}) \\ G_p(x) + \begin{pmatrix} 0 & \Pi_p D \\ D^T \Pi_p^T & \Gamma(x) - \sum_{k=1}^{p-1} C_k \end{pmatrix} \ge 0,$$

**Proposition 2.** Under Assumptions 1 and 3, we have $p_{AD} = p^*$.

*Proof* If $(x^*, D^*, C^*)$ is a solution to (POP-AD) then according to Theorem 3, $x^*$ is feasible to (POP) so that $p_{AD} \ge p^*$. Conversely, if $x^*$ is a solution to (POP), then by Theorem 3 we can find $D^*, C^*$ such that Equation (11) holds and $\tilde{G}_k(x^*) \ge 0$, for all $k \in [p]$. Thus, $p_{AD} \le p^*$. $\square$

Now, we apply AD directly to the problem (POP), then apply the mSOS naively on the resulting problem while taking into account the additional variables when constructing the pseudo-moment sequence. More precisely, we consider the relaxations

$$p_{AD,r}^{\text{prior}} = \min_{\tilde{y}=(y.y_D.y_C)} \mathcal{L}_y(p), \\ \text{s.t. } y_0 = 1, \\ M_r(\tilde{y}) \ge 0, \\ M_{r-r_G}(G_k \tilde{y}) + M_{r-r_G} \left( \begin{bmatrix} 0 & \Pi_k D \\ D^T \Pi_k^T & C_k \end{bmatrix} \tilde{y} \right) \ge 0, \quad k \in [p-1], \\ M_{r-r_G}(G_p \tilde{y}) + M_{r-r_G} \left( \begin{bmatrix} 0 & \Pi_p D \\ D^T \Pi_p^T & \Gamma(x) - \sum_{k=1}^{p-1} C_k(x) \end{bmatrix} \tilde{y} \right) \ge 0, \qquad (\text{ADmSOS}_1)$$

where $\tilde{y}$ is the pseudo-moment sequence associated with the variables $(x, D, C)$, and $r \ge r_{\min}$ with $r_{\min}$ defined in Section 2.2. Under Assumptions 1 and 3, and according to Proposition 2 and Theorem 2, we can show that $p_{AD,r}^{\text{prior}} = p_r$ for any relaxation order $r \ge r_{\min}$. However, the sizes of the moment and localizing matrices in $(\text{ADmSOS}_1)$ will typically be larger than in (mSOS). In order to illustrate this, let $\tilde{x} = (x, D, C)$ and $b_r(\tilde{x})$ the monomial basis associated to $\tilde{x}$ at the relaxation order $r$. We denote by $n_D$ and $n_C$ the number of distinct the component-wise additional variables $D$ and $C$ respectively. Recall that $|b_r(x)| = \binom{n+r}{n}$. We have $\frac{|b_{r+1}(x)|}{|b_r(x)|} = 1 + \frac{n_x}{r+1}$ and
$\frac{|b_{r+1}(\tilde{x})|}{|b_r(\tilde{x})|} = 1 + \frac{n_x+n_C+n_D}{r+1}$. This shows that, for a relatively large $n_C+n_D$, the size of the monomial basis $b_r(\tilde{x})$ used for building the moment and localizing matrices grows much faster than the basis $b_r(x)$ as $r$ increases.

Moreover, let $y$ be a pseudo-moment vector defined for (mSOS), and $\tilde{G}_k(x) = G_k(x) + \begin{bmatrix} 0 & \Pi_k D \\ D^T \Pi_k^T & C_k \end{bmatrix}$. The following result shows the conditions under which the matrix $M_{r-r_G}(\tilde{G}_k \tilde{y})$ could have smaller size than $M_{r-r_G}(Gy)$.

**Proposition 3.** Let $p \in [p]$. We have $|M_{r-r_G}(\tilde{G}_k \tilde{y})| \le |M_{r-r_G}(Gy)|$ if and only if

$$ \prod_{i=1}^{n_D+n_C} \left( 1 + \frac{r-r_G}{n_x+i} \right) \le \frac{|G|}{|\tilde{G}_k|}. \quad (20) $$

*Proof* On the one hand, we have $|M_{r-r_G}(\tilde{G}_k \tilde{y})| \le |M_{r-r_G}(Gy)|$ is equivalent to

$$ |\tilde{G}_k| \begin{pmatrix} n_x + n_D + n_C + r - r_G \\ n_x + n_D + n_C \end{pmatrix} \le |G| \begin{pmatrix} n_x + r - r_G \\ n_x \end{pmatrix}. $$

On the other hand, we have $\binom{n_x+n_D+n_C+r-r_G}{n_x+n_D+n_C} = \binom{n_x+r-r_G}{n_x} \prod_{i=1}^{n_D+n_C} \frac{n_x+r-r_G+i}{n_x+i}$. We obtain $\prod_{i=1}^{n_D+n_C} \frac{n_x+r-r_G+i}{n_x+i} = \prod_{i=1}^{n_D+n_C} \left(1 + \frac{r-r_G}{n_x+i}\right) \le \frac{|G|}{|\tilde{G}_k|}$. $\square$

The inequality (20) holds if $r-r_G = 0$ or $(r-r_G > 0$ and $n_D = n_C = 0)$ or $(n_D + n_C > 0$ and $0 < r-r_G \ll n_x)$. In particular, if we have significantly large number of variables $n_D+n_C$, then the previous inequality will more likely not hold. These conditions render solving numerically (ADmSOS$_1$) not very interesting, unless the decomposition reveals additional sparse structure in the POP such as correlative sparsity [11]. However, this aspect lies beyond the scope of the present work.

**Example 4.** Let $x \in \mathbb{R}_+^3$ and $G(x) = \begin{bmatrix} 2x_1^2 & x_1 & 0 & b_1 \\ x_1 & x_1^2 + 2x_2^2 & x_2 & b_2 \\ 0 & x_2 & x_2^2 & b_3 \\ b_1 & b_2 & b_3 & x_3 \end{bmatrix}$. It can be decomposed

as

$$ \tilde{G}_1(x) = \begin{bmatrix} 2x_1^2 & x_1 & b_1 \\ x_1 & x_1^2 & b_2 + d_{1,2}^{(1)} \\ b_1 & b_2 + d_{1,2}^{(1)} & c_1 \end{bmatrix}, \quad \tilde{G}_2(x) = \begin{bmatrix} 2x_2^2 & x_2 & -d_{1,2}^{(1)} \\ x_2 & x_2^2 & b_3 \\ -d_{1,2}^{(1)} & b_3 & x_3 - c_1 \end{bmatrix}. $$

For $r=2$, we have $|M_{r-r_G}(Gy)| = 16$ and $|M_{r-r_G}(\tilde{G}_1 \tilde{y})| = |M_{r-r_G}(\tilde{G}_2 \tilde{y})| = 15$. Then for $r=3$, we get $|M_{r-r_G}(Gy)| = 40$ and $|M_{r-r_G}(\tilde{G}_1 \tilde{y})| = |M_{r-r_G}(\tilde{G}_2 \tilde{y})| = 45$.

## 4.2 AD posterior to the mSOS hierarchy

The approach here is to apply the AD on the relaxations (4) and derive its tractable truncations. Specifically, we provide new necessary and sufficient conditions for a
sequence $\mathbf{y} = (y_{\alpha})_{\alpha \in \mathbb{N}^{n_x}}$ to have a representing measure on $\mathcal{K} = \{\mathbf{x} \in \mathbb{R}^{n_x} : \mathbf{G}(\mathbf{x}) \succeq 0\}$ that exploit the arrow structure of $\mathbf{G}$. These new conditions have two advantages:

* it avoids including the component-wise auxiliary variables introduced by the decomposition (i.e., those in $\mathbf{D}$ and $\mathbf{C}$) in the monomial basis, as was required in the previous section, and thus leading to smaller localizing matrix inequalities;

* when truncated, they give tighter lower bounds to (POP) compared to the standard approach (mSOS).

We consider again (POP) such that the matrix $\mathbf{G}(\mathbf{x}) \in \mathbb{S}^{n+m}[\mathbf{x}]$ has an arrow structure as in (19). Let $d \in \mathbb{N}$ be an arbitrary degree, $L_d = |\mathbf{b}_d(\mathbf{x})|$ and $\mathbf{y} \in \mathbb{R}^{L_{2d}}$ a vector. By Equation (19), the matrix $\mathbf{M}_d(\mathbf{G}\mathbf{y})$ can be written as

$$ \mathbf{M}_d(\mathbf{G}\mathbf{y}) = \sum_{k=1}^{p} \mathbf{M}_d(\mathbf{G}_k\mathbf{y}) + \begin{bmatrix} \mathbf{0} & \mathbf{0} \\ \mathbf{0} & \hat{\mathbf{\Gamma}}_d(\mathbf{y}) \end{bmatrix}, \quad (21) $$

with

$$ \mathbf{M}_d(\mathbf{G}_k\mathbf{y}) = \begin{bmatrix} \hat{\mathbf{A}}_{d,k}(\mathbf{y}) & \hat{\mathbf{B}}_{d,k}(\mathbf{y}) \\ \hat{\mathbf{B}}_{d,k}(\mathbf{y})^T & \mathbf{0} \end{bmatrix}, $$

and $\hat{\mathbf{A}}_{d,k}(\mathbf{y}) = \mathcal{L}_{\mathbf{y}}(\mathbf{A}_k(\mathbf{x}) \otimes \mathbf{b}_d(\mathbf{x})^T \mathbf{b}_d(\mathbf{x}))$, $\hat{\mathbf{B}}_{d,k}(\mathbf{y}) = \mathcal{L}_{\mathbf{y}}(\mathbf{B}_k(\mathbf{x}) \otimes \mathbf{b}_d(\mathbf{x})^T \mathbf{b}_d(\mathbf{x}))$, and $\hat{\mathbf{\Gamma}}_d(\mathbf{y}) = \mathcal{L}_{\mathbf{y}}(\mathbf{\Gamma}(\mathbf{x}) \otimes \mathbf{b}_d(\mathbf{x})^T \mathbf{b}_d(\mathbf{x}))$.

We denote by $(\hat{\mathcal{I}}_k)_{k \in [p]}$ the index set of the matrices $\hat{\mathbf{A}}_{d,k}(\mathbf{y})$, that can be defined explicitly by

$$ \hat{\mathcal{I}}_k = \{(i_k - 1)L_d + i_b : (i_k, i_b) \in \mathcal{I}_k \times [L_d]\}, \quad (22) $$

where the index $i_b$ enumerates the element in the monomial basis $\mathbf{b}_d(\mathbf{x})$.

Notice that the block sparsity of the matrix $\mathbf{M}_d(\mathbf{G}\mathbf{y})$ is the same as the sparsity of the matrix $\mathbf{G}(\mathbf{x})$.

Furthermore, we consider the matrices $\hat{\mathbf{\Pi}}_k$ defined in (36) for the sets $\hat{\mathcal{I}}_k$. We establish in Lemma 5 (Appendix A.1) a direct link between the matrix $\mathbf{\Pi}_k$ associated to $\mathcal{I}_k$, and the matrix $\hat{\mathbf{\Pi}}_k$ associated to $\hat{\mathcal{I}}_k$ via the equation $\hat{\mathbf{\Pi}}_k = \mathbf{\Pi}_k \otimes \mathbf{I}_{L_d}$.

The following result is an arrow decomposed version of Theorem 1.

**Theorem 4.** Suppose that Assumptions 1 and 3 hold and let $\mathbf{y} = (y_{\alpha})_{\alpha \in \mathbb{N}^{n_x}}$ be a pseudo-moment vector. The following statements are equivalents:

1. $\mathbf{y}$ has a representing measure supported on $\mathcal{K}$

2. For all $d \in \mathbb{N}$, $\mathbf{M}_d(\mathbf{y}) \succeq 0$ and there exists matrices $\hat{\mathbf{D}}_d \in \mathbb{R}^{L_d n_x \times L_d m}$ and $\hat{\mathbf{C}}_{d,k} \in \mathbb{S}^{m L_d}$ for all $k \in [p]$, such that

$$ \begin{align} \mathbf{M}_d(\mathbf{G}_k\mathbf{y}) + \begin{bmatrix} \mathbf{0} & (\mathbf{\Pi}_k \otimes \mathbf{I}_{L_d})\hat{\mathbf{D}}_d \\ \hat{\mathbf{D}}_d^T(\mathbf{\Pi}_k \otimes \mathbf{I}_{L_d})^T & \hat{\mathbf{C}}_{d,k} \end{bmatrix} &\succeq 0, k \in [p-1], \tag{23} \\ \mathbf{M}_d(\mathbf{G}_p\mathbf{y}) + \begin{bmatrix} \mathbf{0} & (\mathbf{\Pi}_p \otimes \mathbf{I}_{L_d})\hat{\mathbf{D}}_d \\ \hat{\mathbf{D}}_d^T(\mathbf{\Pi}_p \otimes \mathbf{I}_{L_d})^T & \hat{\mathbf{\Gamma}}_d(\mathbf{y}) - \sum_{k=1}^{p-1} \hat{\mathbf{C}}_{d,k} \end{bmatrix} &\succeq 0. \nonumber \end{align} $$
Proof Suppose that the first statement holds. According to Theorem 1, we have $M_d(y) \succeq 0$ and $M_d(Gy) \succeq 0$ for all $d \in \mathbb{N}$. We claim that $\hat{A}_{d,k}(y) \succeq 0, \forall k \in [p]$ and $\hat{\Gamma}_d(y) \succeq 0$. To prove this claim, fix $k \in [p]$, $v \in \mathbb{R}^{nL_d}$, and define the polynomial vector $w(x) = (I_n \otimes b_d(x))v$. We have

$$v^T \hat{A}_{d,k}(y)v = \mathcal{L}_y \left( \langle A_k(x) \otimes I_{L_d}, w(x)^T w(x) \rangle \right).$$

By assumption, the matrix $A_k(x)$ is positive semidefinite on $\mathcal{K}$, and thus we have $\langle A_k(x) \otimes I_{L_d}, w(x)^T w(x) \rangle = w(x)^T (A_k(x) \otimes I_{L_d}) w(x) \geq 0$. Now, since $y$ has representing measure supported on $\mathcal{K}$, we have $\mathcal{L}_y (\langle A_k(x) \otimes I_{L_d}, w(x)^T w(x) \rangle) = \int_{\mathcal{K}} \langle A_k(x) \otimes I_{L_d}, w(x)^T w(x) \rangle d\mu \geq 0$ (see section 2.1), so that $\hat{A}_{d,k}(y) \succeq 0$. Similarly, we prove that $\hat{\Gamma}_d(y) \succeq 0$. Now, according to Proposition 1, we have $M_d(Gy) \succeq 0$, we can then conclude using Theorem 3.

Conversely, suppose that the second statement holds. By Theorem 3, we have $M_d(Gy) \succeq 0$ and $M_d(y) \succeq 0$, for all $d \in \mathbb{N}$, so $y$ has a representing measure by Theorem 1. $\square$

**Remark 3.** To ease the notation in the sequel, we omit the dependency of the matrices $\hat{A}_k$, $\hat{B}_k$, $\hat{D}$, $\hat{C}_k$ and $\hat{\Gamma}$, on the degree $d$. Moreover, we denote in the sequel $\hat{C} = (\hat{C}_k)_{k \in [p-1]}$.

Theorem 4 allows us to state an arrow decomposition version of the infinite relaxations in (4):

**Corollary 1.** Suppose that Assumptions 1 and 3 hold. We have

$$p^* = \min_{y, \hat{D}, \hat{C}} \mathcal{L}_y(p) \\ \text{s.t. } y_0 = 1, \\ M_d(y) \succeq 0, \forall d \in \mathbb{N}, \\ M_d(G_k y) + \begin{bmatrix} 0 & (\Pi_k \otimes I_d)\hat{D} \\ \hat{D}^T(\Pi_k \otimes I_d)^T & \hat{C}_k \end{bmatrix} \succeq 0, k \in [p-1], \forall d \in \mathbb{N}, \\ M_d(G_p y) + \begin{bmatrix} 0 & (\Pi_p \otimes I_d)\hat{D} \\ \hat{D}^T(\Pi_p \otimes I_d)^T \hat{\Gamma}(y) - \sum_{k=1}^{p-1} \hat{C}_k \end{bmatrix} \succeq 0, \forall d \in \mathbb{N}.$$

Proof Straightforward, we can show the equivalence between (24) and (4) by using Theorem 4 and Lemma 5. $\square$

We now consider finite-dimensional relaxations of (24). Let $r \geq r_{\min}$ where $r_{\min}$ is defined in Section 2.2. The resulting arrow-decomposed hierarchy of finite-dimensional semidefinite programs associated with (24) is given by:
$$p_{AD,r}^{\text{post}} = \min_{\mathbf{y}, \hat{\mathbf{D}}, \hat{\mathbf{C}}} \mathcal{L}_{\mathbf{y}}(p),$$

s.t. $y_0 = 1$,

$$M_r(\mathbf{y}) \succeq 0,$$

$$M_{r-r_G}(G_k y) + \left[ \hat{D}^T (\Pi_k \otimes I_{L_{r-r_G}})^T \quad (\Pi_k \otimes I_{L_{r-r_G}}) \hat{D} \right] \succeq 0, k \in [p-1],$$

$$M_{r-r_G}(G_p y) + \left[ \hat{D}^T (\Pi_p \otimes I_{L_{r-r_G}})^T \hat{\Gamma}(y) - \sum_{k=1}^{p-1} \hat{C}_k \right] \succeq 0.$$

(ADmSOS₂)

Next, we show that the relaxations (ADmSOS₂) are at least as tight as (mSOS), and therefore converge as $r \to \infty$.

**Theorem 5.** Suppose that Assumptions 1 and 3 hold. Then for any relaxation order $r \ge r_{min}$, we have $p_r \le p_{AD,r}^{\text{post}} \le p^*$. Moreover, we have $\lim_{r \to \infty} p_{AD,r}^{\text{post}} = \lim_{r \to \infty} p_r = p^*$.

*Proof* If $(y^*, \hat{D}^*, \hat{C}^*)$ is a solution to (ADmSOS₂), then $y^*$ is feasible for (mSOS), so $f_{AD,r}^{\text{post}} \ge f_r$.

Now, if $x^*$ is a solution to (POP), then by Theorem 1, one can find a moment vector $y^*$ solution to Problem 4. By Theorem 4, we can find $(\hat{D}^*, \hat{C}^*)$ such that $(y^*, \hat{D}^*, \hat{C}^*)$ is a solution to (ADmSOS₂) so that $f_{AD,r}^{\text{post}} \le f^*$. Since $\lim_{r \to \infty} f_r = f^*$ by Theorem 2, we conclude that $\lim_{r \to \infty} f_{AD,r}^{\text{post}} = \lim_{r \to \infty} f_r = f^*$. □

Let us notice that the approach presented in this section preserves the applicability of the rank flatness condition and the extraction of minimizers presented in Section 2.2. Indeed, if $y^*$ is a solution of (ADmSOS₂) at a given relaxation order $r$, we have $M_r(y^*) \succeq 0$ and

$$M_{r-r_G}(Gy^*) = \sum_{k=1}^{p} \left( M_{r-r_G}(G_k y^*) + \left[ \hat{D}^T (\Pi_k \otimes I_{L_{r-r_G}})^T \hat{D} \right] \right) \succeq 0,$$

allowing us to get the full information on $y^*$ to test the condition (5).

## 4.3 Computational considerations

Here, as in Section 3.1, we aim to deal with potential rank deficiencies in the matrices $\hat{A}_k(\mathbf{x})$. As the relaxation degree increases, the size of these matrices grows significantly, making it computationally expensive to test for rank deficiency or to compute their range and null spaces. This increased complexity poses practical challenges for directly implementing Proposition 1.

In this section, we consider a special class of polynomial matrices $A_k(\mathbf{x})$ whose range and null spaces are constant (i.e., independent of $\mathbf{x}$). For such matrices, we can
derive a weaker version of Proposition 1 applicable to the associated matrices $\hat{A}_k(y)$, by leveraging the known range and null spaces of $A_k(x)$.

The first two results establish a link between the null space (respectively range space) of a given matrix $A(x)$ and its associated localizing matrix $\hat{A}(y)$.

**Lemma 2.** Let $A \in \mathbb{S}^n[x]$, $b(x)$ be a polynomial vector of length $L$, and $y = (y_\alpha)_\alpha$ a given vector of length $L$. We have

$$ \mathrm{Null}(A(x) \otimes I_L) \subseteq \mathrm{Null}(\mathcal{L}_y(A(x) \otimes b(x)^T b(x))). $$

*Proof* Let $w \in \mathrm{Null}(A(x))$. We have $w \otimes I_L \in \mathrm{Null}(A(x) \otimes I_L)$ and

$$ \mathcal{L}_y(A(x) \otimes b(x)^T b(x))(w \otimes I_L) = \mathcal{L}_y(A(x)w \otimes b(x)^T b(x)) = 0. $$

□

**Lemma 3.** Let $A \in \mathbb{S}^n[x]$ and $P \in \mathbb{R}^{n \times s}$, $s \le n$ with full column rank and such that $P^T P = I_s$. Suppose that $\mathrm{Span}(A(x)) \subseteq \mathrm{Span}(P)$ for all $x \in \mathbb{R}^{n_x}$. Let $b(x)$ be a polynomial vector of length $L$, and $y = (y_\alpha)_\alpha$ a given vector of length $L$. We have

$$ \mathrm{Span}(\mathcal{L}_y(A(x) \otimes b(x)^T b(x))) \subseteq \mathrm{Span}(P \otimes I_L). $$

*Proof* Let $x \in \mathbb{R}^{n_x}$ and $v \in \mathrm{Span}(\mathcal{L}_y(A(x) \otimes b(x)^T b(x)))$. There exists a vector $u \in \mathbb{R}^{n^L}$ such that $v = \mathcal{L}_y(A(x) \otimes b(x)^T b(x))u$. We denote by $U$ and $V$ the matrices such that $u = \mathrm{Vec}(U)$ and $v = \mathrm{Vec}(V)$, where recall $\mathrm{Vec}$ is the vectorization operator. Using Kronecker product and vectorization operator properties, we have $A(x) \otimes b(x)^T b(x)u = \mathrm{Vec}(b(x)^T b(x)UA(x))$ and thus

$$ V = \mathcal{L}_y(b(x)^T b(x)UA(x)). $$

Now, since $\mathrm{Span}(A(x)) \subseteq \mathrm{Span}(P)$, there exists a matrix $W \in \mathbb{R}^{L \times s}[x]$ such that $b(x)^T b(x)UA(x) = W(x)P^T$. We have then $V = \mathcal{L}_y(W(x)P^T) = \mathcal{L}_y(I_L W(x)P^T)$, and therefore

$$ v = (P \otimes I_L) \mathcal{L}_y(w(x)) $$

with $w(x) = \mathrm{Vec}(W(x))$, proving that $v \in \mathrm{Span}(P \otimes I_L)$. □

□

We now state the main result of this section.

**Proposition 4.** Suppose that Assumption 3 holds. For each $k \in [p]$, let $P_k \in \mathbb{R}^{n_k \times s_k}$, $s_k \le n_k$, be a matrix with full column rank satisfying $P_k^T P_k = I_{s_k}$ and such that for all $x \in \mathbb{R}^{n_x}$, we have $\mathrm{Span}(A_k(x)) \subseteq \mathrm{Span}(P_k)$. Moreover, suppose that the vector

<footnote n="2">²This result can be proved in a more general context, without assuming that $P$ has full column rank or that $P^T P = I_s$. However, since the main result in Proposition 4 always relies on these additional assumptions, a general proof is beyond the scope of this paper.</footnote>
$\mathbf{y} = (y_\alpha)_\alpha$ has a representing measure supported on $\mathcal{K}$. Then the condition (23) is equivalent to the conditions

$$ \left[ \begin{array}{cc} \hat{P}_k^T \hat{A}_k(\mathbf{y}) \hat{P}_k & \hat{P}_k^T (\hat{B}_k(\mathbf{y}) + (\mathbf{\Pi}_k \otimes \mathbf{I}_{L_d}) \hat{D}) \\ (\hat{B}_k(\mathbf{y}) + (\mathbf{\Pi}_k \otimes \mathbf{I}_{L_d}) \hat{D})^T \hat{P}_k & \hat{C}_k \end{array} \right] \geq 0, \forall k \in [p-1], \\ \left[ \begin{array}{cc} \hat{P}_p^T \hat{A}_p(\mathbf{y}) \hat{P}_p & \hat{P}_k^T (\hat{B}_k(\mathbf{y}) + (\mathbf{\Pi}_k \otimes \mathbf{I}_{L_d}) \hat{D}) \\ (\hat{B}_p(\mathbf{y}) + (\mathbf{\Pi}_p \otimes \mathbf{I}_{L_d}) \hat{D})^T \hat{P}_p & \hat{\Gamma}(\mathbf{y}) - \sum_{k=1}^{p-1} \hat{C}_k \end{array} \right] \geq 0, \quad (25) $$

$$ \mathrm{Span}(\hat{B}_k(\mathbf{y}) + (\mathbf{\Pi}_k \otimes \mathbf{I}_{L_d})\hat{D}) \subseteq \mathrm{Span}(\hat{P}_k), \forall k \in [p]. $$

with $\hat{P}_k = P_k \otimes I_{L_d}$.

*Proof* Since $\mathbf{y}$ has a representing measure on $\mathcal{K}$, we have that $\hat{A}_k(\mathbf{y}) \geq 0$ for all $k \in [p]$ (see Proof of Theorem 4). The rest of the proof is due to Proposition 1 and Lemma 3. $\square$

Proposition 4 is particularly useful when $\mathbf{A}_k(\mathbf{x})$ is rank-deficient for some $k \in [p]$. In such cases, Lemma 2 ensures that the associated localizing matrix is also rank-deficient. Consequently, one can find $P_k$ satisfying the assumptions of Proposition 4 with $s_k < n_k$, thereby reducing the size of $\hat{G}_k$ while imposing the condition $\mathrm{Span}(\hat{B}_k(\mathbf{y}) + (\mathbf{\Pi}_k \otimes \mathbf{I})\hat{D}) \subseteq \mathrm{Span}(\hat{P}_k)$. This condition is equivalent to $\hat{B}_k(\mathbf{y}) + (\mathbf{\Pi}_k \otimes \mathbf{I}_{L_d})\hat{D} \in \mathrm{Im}(\hat{P}_k(\mathbf{y}))$ and it suffices to replace it by $\hat{B}_k(\mathbf{y}) + (\mathbf{\Pi}_k \otimes \mathbf{I}_{L_d})\hat{D} \in \mathrm{Im}(\hat{A}_k(\mathbf{y}))$. In applications where $\mathbf{A}_k(\mathbf{x})$ has a constant null space, i.e. there exists a subspace $\mathcal{N}_k \subset \mathbb{R}^n$ such that $\mathcal{N}_k \perp \mathrm{Span}(P_k)$ and $\mathrm{Null}(\mathbf{A}(\mathbf{x})) = \mathcal{N}_k$ for all $\mathbf{x} \in \mathcal{K}$ (see, e.g., Section A.2), the condition $\hat{B}_k(\mathbf{y}) + (\mathbf{\Pi}_k \otimes \mathbf{I}_{L_d})\hat{D} \in \mathrm{Im}(\hat{A}_k(\mathbf{y}))$ can be enforced implicitly by solving for $\hat{D}$ the system

$$ \{ (\hat{B}_k(\mathbf{y}) + (\mathbf{\Pi}_k \otimes \mathbf{I}_{L_d})\hat{D}) (\mathbf{W}_k \otimes \mathbf{I}_{L_d}) = 0, k \in [p] \}, $$

where $\mathbf{W}_k$ spans $\mathcal{N}_k$. This procedure also allows eliminating some (or all) of the entries of $\hat{D}$.

## 4.4 A connection between AD posterior and AD prior the mSOS

In this section, we emphasize that the problem (ADmSOS$_2$) can also be obtained from the problem (ADmSOS$_1$) by considering the additional variables $\mathbf{D}$ and $\mathbf{C}$ as external
variables to the hierarchy. More precisely, we consider the problem:

$$ \min_{y, D, C} \mathcal{L}_y(f), $$

s.t. $y_0 = 1$,

$$ M_r(y) \succeq 0, $$

$$ M_{r-r_G}(G_k y) + M_{r-r_G} \left( \begin{bmatrix} 0 & \Pi_k D \\ D^T \Pi_k^T & C_k \end{bmatrix} y \right) \succeq 0, \quad k \in [p-1], $$

$$ M_{r-r_G}(G_p y) + M_{r-r_G} \left( \begin{bmatrix} 0 & \Pi_p D \\ D^T \Pi_p^T & \hat{\Gamma}(y) - \sum_{k=1}^{p-1} C_k \end{bmatrix} y \right) \succeq 0. $$

This problem is non-linear because of the terms

$$ M_{r-r_G} \left( \begin{bmatrix} 0 & \Pi_k D \\ D^T \Pi_k^T & C_k \end{bmatrix} y \right) = \left[ \mathcal{L}_y(b_{r-r_G}(x)^T b_{r-r_G}(x)) \otimes D^T \Pi_k^T \quad \Pi_k D \otimes \mathcal{L}_y(b_{r-r_G}(x)^T b_{r-r_G}(x)) \right]. $$

However, we can see the matrix variables $\hat{D}$ and $\hat{C}$ in Problem (ADmSOS₂) as a component-wise linearization of the previous non-linear terms, i.e., if we replace each entry

$[\Pi_k D \otimes \mathcal{L}_y(b_{r-r_G}(x)^T b_{r-r_G}(x))]_{ij}$ with $(\hat{D})_{ij}$, and each entry

$[C_k \otimes \mathcal{L}_y(b_{r-r_G}(x)^T b_{r-r_G}(x))]_{ij}$ with $(\hat{C}_k)_{ij}$, we recover exactly the problem (ADmSOS₂).

Consequently, this shows that this "relaxation of relaxation" hierarchy is monotonically convergent with the relaxation order $r$, thanks to Theorem 5. Thus, there is no need to add norm constraints to the additional variables in (ADmSOS₁) to maintain convergence.

# 5 Application: topology optimization of frame structures

This section is devoted to illustrating the arrow decomposition method when applied to topology optimization problems. In topology optimization problems, we aim to design structures that provide the optimal mechanical response to external inputs such as forces. Consider a discretized design domain comprising $n_n \in \mathbb{N}$ nodes (representing joints) connected by $n_e \in \mathbb{N}$ potential Euler-Bernoulli finite elements. External forces $f \in \mathbb{R}^{n_{\text{dof}}}$ are applied to specific nodes of the structure, with $n_{\text{dof}}$ denoting the number of degrees of freedom. The optimization task involves finding the continuous cross-sectional areas $x \in \mathbb{R}^{n_e} \ge 0$ of individual finite elements that yield the most efficient design. This efficiency is evaluated with respect to two functions: the compliance $\gamma(x)$, which characterizes the inverse of the structure's stiffness, and the weight $w(x)$, which quantifies the total amount of material used.
For simplicity, here we consider a single-load scenario, i.e., there is only one set of loads applied to the structure. We refer the reader to [14, 27] for an extension to the more general case of multiple loading scenarios. At each element e, the local displacement vector $u_e$ corresponds to three degrees of freedom: translations in the x- and y-directions, and a rotation. The global displacement vector of the structure, denoted by $u$, is obtained by concatenating the local displacements $u_e$ across all elements e. Therefore, here, we define the compliance function as the potential energy of the loads $f$ as

$$ \gamma := f^T u, \qquad (26) $$

in which $u \in \mathbb{R}^{n_{\text{dof}}}$ solves the elastic equilibrium

$$ K(x)u = f(x). \qquad (27) $$

In (27), $K(x) \in S^{n_{\text{dof}}}$ is the corresponding symmetric positive semidefinite stiffness matrix assembled as

$$ K(x) = K_0 + \sum_{e=1}^{n_e} \left[ K_e^{(1)} x_e + K_e^{(2)} x_e^2 + K_e^{(3)} x_e^3 \right]. \qquad (28) $$

Here, the matrix $K_0 \succeq 0$ constitutes a design-independent structural stiffness, $K_e^{(1)}$ represents the element e membrane stiffness, and the matrices $K_e^{(2)}$ and $K_e^{(3)}$ encompass the bending effects. By construction, we have $K_e^{(i)} \succeq 0$ for all e and $i \in \{1, 2, 3\}$. Moreover, we assume that $\forall x > 0: K(x) > 0$ as, otherwise, the structure would behave as a rigid body mechanism.

## 5.1 Compliance minimization problem

Given a maximum weight $\bar{w} \in \mathbb{R}_{>0}$, finding the minimum-compliant structure is formulated as

$$ \gamma^* = \min_{x, u} f(x)^T u \qquad (29a) $$

$$ \text{s.t.} \quad K(x)u - f(x) = 0, \qquad (29b) $$

$$ \bar{w} - \sum_{e=1}^{n_e} \ell_e \rho_e x_e \geq 0, \qquad (29c) $$

$$ x \geq 0, \qquad (29d) $$

where the weight $w(x) = \sum_{e=1}^{n_e} \ell_e \rho_e x_e$ is computed from the element lengths $\ell \in \mathbb{R}_{>0}^{n_e}$ and their densities $\rho \in \mathbb{R}_{>0}^{n_e}$.

The state variables $u$ can be eliminated from the formulations by introducing a slack variable $\gamma$ and by using Equations (27) and (26), leading to the following problem
$$ \min_{\mathbf{x}, \gamma} \gamma \qquad (30a) $$

$$ \text{s.t.} \quad \gamma - \mathbf{f}(\mathbf{x})^T [\mathbf{K}(\mathbf{x})]^\dagger \mathbf{f}(\mathbf{x}) \geq \mathbf{0}, \qquad (30b) $$

$$ \bar{w} - \sum_{e=1}^{n_e} \ell_e \rho_e x_e \geq 0, \qquad (30c) $$

$$ \mathbf{x} \geq \mathbf{0}, \qquad (30d) $$

$$ \mathbf{f}(\mathbf{x}) \in \mathrm{Im}(\mathbf{K}(\mathbf{x})), \qquad (30e) $$

where the constraint (30e) is a necessary and sufficient condition to have $\mathbf{u} = \mathbf{K}(\mathbf{x})^\dagger \mathbf{f}(\mathbf{x})$ (see [14, Lemma 1]). Moreover, it is shown in [14, Proposition 1] that the condition (30e) is equivalent to the condition

$$ \mathbf{K}(\mathbf{x})[\mathbf{K}(\mathbf{x})]^\dagger \mathbf{f}(\mathbf{x}) = \mathbf{f}(\mathbf{x}). \qquad (31) $$

Using Lemma 1, we can derive the equivalent polynomial semidefinite problem

$$ \gamma^* = \min_{\mathbf{x}, \gamma} \gamma \qquad (32a) $$

$$ \text{s.t.} \quad \begin{pmatrix} \mathbf{K}(\mathbf{x}) & -\mathbf{f}(\mathbf{x})^T \\ -\mathbf{f}(\mathbf{x}) & \gamma \end{pmatrix} \geq 0, \qquad (32b) $$

$$ \bar{w} - \sum_{e=1}^{n_e} \ell_e \rho_e x_e \geq 0, \qquad (32c) $$

$$ \mathbf{x} \geq \mathbf{0}, \qquad (32d) $$

in which the polynomial matrix inequality (32b) enforces the equilibrium.

### 5.1.1 Weight minimization problem

Similarly to the compliance minimization problem, we can write a polynomial SDP formulation of the weight minimization problem only in terms of $\mathbf{x}$ as

$$ \min_{\mathbf{x}} \sum_{e=1}^{n_e} \ell_e \rho_e x_e \qquad (33a) $$

$$ \text{s.t.} \quad \begin{pmatrix} \mathbf{K}(\mathbf{x}) & -\mathbf{f}(\mathbf{x}) \\ -\mathbf{f}(\mathbf{x})^T & \bar{\gamma} \end{pmatrix} \geq 0, \qquad (33b) $$

$$ \mathbf{x} \geq \mathbf{0}, \qquad (33c) $$

where $\bar{\gamma}$ here represents a fixed upper bound for the compliance. Moreover, for both problems (32) and (33), it is shown in [14, 27] that the problem (32) can be compactified and individual variables scaled to the [-1, 1] domain. On the one hand, this
improves numerical performance, and, on the other hand, ensures that these problems satisfy the Archimedean assumption 1. Thus, assumptions for the convergence of the moment SOS hierarchy are satisfied (Section 2.2).

In addition to lower bounds obtained by solving relaxations of the Lasserre hierar-
chy, in [14, 27], we also derived a simple procedure for evaluating feasible upper bounds.
When the gap between these bounds is small, the mSOS provides approximately
globally optimal solution.

5.2 Decomposition of the compliance minimization problem

In this section, we explicitly construct the arrow decomposed formulation for the case of
compliance minimization (32). Because the result for the weight optimization settings
(33) is analogous, we do not detail it here.

Let us denote by $\mathcal{D} := [n_e]$ the domain of potential elements and partition $\mathcal{D}$ into $p$ subdomains $\mathcal{D}_k$, $k \in [p]$, where each $\mathcal{D}_k$ can contain one or more elements $e$. For each subdomain $\mathcal{D}_k$, we thus receive the stiffness matrix $\mathbf{K}_k$ that is built as $\mathbf{K}(\mathbf{x}) = \sum_{k \in \mathcal{D}_k} \mathbf{K}_k(\mathbf{x})$. Recall that by construction, we have $\mathbf{K}_k(\mathbf{x}) \succeq 0$, so that the assumption of Theorem 3 holds.

Next, thanks to the link between AD and domain decomposition methods in [1], we can define the partitioning of the matrix $\mathbf{K}_k(\mathbf{x})$ according to the subdomains $\mathcal{D}_k$. Let $\mathcal{L}_k$ denote the set of indices of degrees of freedom $^3$ located in the interior of $\mathcal{D}_k$, i.e., $\mathcal{I}_k = \mathcal{I}_k \setminus \bigcup_{\ell:\ell>k} \mathcal{I}_{k,\ell}$ and the set $\mathcal{J}_k$ of the indices of all remaining degrees of freedom in one of the intersection $\mathcal{I}_{k,\ell}$ or $\mathcal{I}_{\ell,k}$, i.e. $\mathcal{J}_k = \bigcup_{\ell:\ell>k} \mathcal{I}_{k,\ell}$. Then, we can permute and partition each matrix $\mathbf{K}_k(\mathbf{x})$, $\mathbf{f}(\mathbf{x})$ as follows:

$$
\mathbf{K}_k(\mathbf{x}) = \begin{bmatrix} \mathcal{K}_{\mathcal{L}_k} \mathcal{L}_k(\mathbf{x}) & \mathcal{K}_{\mathcal{L}_k} \mathcal{J}_k(\mathbf{x}) \\ \mathcal{K}_{\mathcal{J}_k} \mathcal{L}_k(\mathbf{x}) & \mathcal{K}_{\mathcal{J}_k} \mathcal{J}_k(\mathbf{x}) \end{bmatrix}, \quad \mathbf{f}_k(\mathbf{x}) = \begin{bmatrix} \mathbf{f}_{\mathcal{L}_k} \\ \mathbf{f}_{\mathcal{J}_k} \end{bmatrix}. \qquad (34)
$$

Let $r$ be a relaxation order, and $\mathbf{y}$ a pseudo-moment vector related to the variables $\mathbf{x}$ and $\gamma$. The arrow decomposed mSOS relaxations for the compliance optimization problem (32d) reads as

$$
\gamma_{\text{AD},r}^* = \min_{\mathbf{y},\mathbf{d},\mathbf{c}} \mathcal{L}_{\mathbf{y}}(\gamma),
$$

$$
\text{s.t. } y_0 = 1,
$$

$$
M_r(\mathbf{y}) \succeq 0,
$$

$$
M_{r-r_K}(\mathbf{Z}_k \mathbf{y}) + \left[ \mathbf{d}^T (\mathbf{\Pi}_k \otimes \mathbf{I}_{L_{r-r_K}})^T \quad \begin{array}{c} \mathbf{0} \\ c_k \end{array} (\mathbf{\Pi}_k \otimes \mathbf{I}_{L_{r-r_K}}) \mathbf{d} \right] \succeq 0, k \in [p-1],
$$

$$
M_{r-r_K}(\mathbf{Z}_p \mathbf{y}) + \left[ \mathbf{d}^T (\mathbf{\Pi}_p \otimes \mathbf{I}_{L_{r-r_K}})^T \quad \begin{array}{c} \mathbf{K}_p(\mathbf{x}) \\ \gamma - \sum_{k=1}^{p-1} c_k \end{array} (\mathbf{\Pi}_p \otimes \mathbf{I}_{L_{r-r_K}}) \mathbf{d} \right] \succeq 0,
$$

$$
M_{r-1} \left( \left( \bar{V} - \sum_{i=1}^{n_e} x_i \ell_i \right) \mathbf{y} \right) \succeq 0,
$$

$$
M_{r-1}(x_i \mathbf{y}) \succeq 0, i \in [n_e],
$$

<footnote n="3">³Here, the total degrees of freedom of the problem play the role of the index set of the matrix $\mathbf{K}(\mathbf{x})$.</footnote>
with $Z_k(\boldsymbol{x}) = \begin{bmatrix} \boldsymbol{K}_k(\boldsymbol{x}) & \boldsymbol{f}_k(\boldsymbol{x}) \\ \boldsymbol{f}_k(\boldsymbol{x})^T & \mathbf{0} \end{bmatrix}$ for all $k \in [p]$, and $r_K = \lceil \frac{\deg(\boldsymbol{K})}{2} \rceil$. The convergence of the sequence $\gamma_{AD,r}^*$ to $\gamma^*$ as $r \to \infty$ is ensured by Theorem 5.

An analysis of the additional variables $d_k$ and their physical interpretation in the context of frame structures is provided in Appendix A.2.

# 6 Numerical examples

In this section, we present two numerical examples that demonstrate the computational advantages of arrow decomposition in frame structure optimization problems. We first recall some technical features when working with frame structures and mSOS hierarchies. Specifically, we highlight that a reduced monomial basis can be used to construct the mSOS hierarchies instead of the standard one. Based on the numerical results developed in [19], we additionally adopt the non-mixed term (NMT) basis, which is defined by removing all mixed products from the standard monomial basis, i.e., $b_r^{\text{NMT}}(\boldsymbol{x}) := \{1, x_1, \dots, x_n, x_1^2, \dots, x_n^2, \dots, x_1^r, \dots, x_n^r\}$. Moroever, we define the relative optimality gap $\varepsilon_r = f_{\text{ub}}/f_{\text{lb}} - 1$, where $f_{\text{ub}}$ is an upper bound. For compliance and weight optimization problems, this upper bound is defined in [14] and [27], respectively. This optimality gap provides a global optimum certificate and serves as a measure of solution quality [14, 27, 28]. Furthermore, the optimality gap approach allows us to avoid evaluating the rank of large matrices, which is required for the rank flatness condition in (5).

The first example examines a double-hinged beam under self-weight loading, where we analyze the scalability of AD posterior-to-mSOS approach by varying the number of finite elements from 1 to 15. The second example considers a 24-element modular frame structure, showcasing the method's effectiveness on a more practical engineering problem. For both examples, we compare four solution approaches: standard moment-SOS (mSOS), moment-SOS with arrow decomposition (mSOS+AD), moment-SOS using nonmixed-term basis (mSOS+NMT), and moment-SOS combining both techniques (mSOS+NMT+AD). We evaluate these methods across different relaxation orders, analyzing their performance in terms of computation time, solution quality, and numerical stability. All computations were performed on a workstation equipped with dual Intel® Xeon® E5-2630 v3 processors and 128 GB of RAM using the Mosek optimizer with default parameters. Our implementation of the method and numerical examples are publicly available as a MATLAB package at https://gitlab.com/tyburec/pof-dyna.

## 6.1 Double-hinged beam under selfweight

Consider a symmetric half of a double-hinged beam as our first numerical example, see Fig. 1. The beam features a pinned support at its left end restricting both translations, while its right end has a roller support preventing vertical translation and rotation. The beam is made of a linear-elastic material with Young's modulus $E = 210$ GPa and density $\rho = 7850$ kg/m$^3$. With an I-shaped cross-section, as displayed in Fig. 1b, the stiffness matrix $\boldsymbol{K}(\boldsymbol{x})$ contains polynomials of degree at most 2. The beam is subjected to two types of loads: a uniform distributed load with intensity $\bar{f} = 1$ kN/m,
and self-weight loading that depends on the design variables $\boldsymbol{x} \in \mathbb{R}^{n_e}$ representing the element's cross-sectional areas. The presence of design-dependent self-weight makes this problem numerically more challenging than standard compliance minimization because, typically, a higher relaxation degree is required to solve the problem globally and the relaxation solutions are less accurate.

<figure><img src="image_4.png" /><figcaption>**Fig. 1:** Double-hinged beam under selfweight loads: (a) boundary conditions, (b) cross-section parametrization, and (c) approximately globally-optimal designs for $n_e = \{1, 5, 10, 15\}$.</figcaption></figure>

The optimization objective is to minimize the beam's compliance while respecting a weight constraint $\bar{w} = 785$ kg, which corresponds to 0.1 m$^3$ volume of material. For the numerical study, we discretize the 5 m long beam half into $n_e$ equal-length elements, with $n_e$ ranging from 1 to 15. Each element $i$ thus experiences a total distributed load of $f_i(x_i) = 1 + \frac{385.435}{n_e} x_i$ [kN/m], where the first term represents the external load and the second term accounts for the self-weight, with $x_i$ being the cross-sectional area of element $i$.

For the arrow decomposition, we partition the beam into $n_e - 1$ subdomains, where the first subdomain $D_1$ contains elements $\{1, 2\}$, and each subsequent subdomain $D_k$ contains a single element $k+1$. This leads to index sets $\mathcal{I}_1 = \{1, 2, 3, 4, 5, 6, 7\}$ containing degrees of freedom associated with the first two elements, $\mathcal{I}_2 = \{5, 6, 7, 8, 9, 10\}$ for the third element, and so on. The intersections of consecutive subdomains contain three degrees of freedom each, corresponding to the shared nodes between elements. For instance, $\mathcal{I}_{1,2} = \{5, 6, 7\}$ represents the degrees of freedom at the node shared between the domains $D_1$ and $D_2$.

For all discretizations, the variable reduction procedure from Section A.2 leads to $|D_{\text{red}}| = 1$. This corresponds directly to the single degree of statical indeterminacy in
the double-hinged beam – physically, only one redundant force cannot be determined purely from equilibrium equations.

<figure><img src="image_5.png" /><figcaption>(a) Solving time in function of the number of (b) Total number of relaxation variables and elements size of the largest SDP matrix</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(a) Solving time in function of the number of (b) Total number of relaxation variables and elements size of the largest SDP matrix</figcaption></figure>

<caption>**Fig. 3:** Comparison of mSOS and ADmSOS for the second-order relaxation of a double-hinged beam problem</caption>

The numerical results in Figures 2–8, together with detailed data in Tables 2–5 in Appendix A.3, demonstrate the computational advantages offered by arrow decomposition across different problem sizes and relaxation orders. For the first-order relaxation ($r = 1$), all methods perform comparably on small problems with $n_e \le 9$, requiring
<figure><img src="image_7.png" /><figcaption>Fig. 4: Comparison of mSOS and ADmSOS for the third-order relaxation of a double-hinged beam problem</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 5: Comparison of mSOS+NMT and ADmSOS+NMT for the first-order relaxation of a double-hinged beam problem</figcaption></figure>

less than 0.1 seconds of computation time. However, even at this lowest relaxation order, both AD variants (mSOS+AD and mSOS+NMT+AD) maintain consistent performance as $n_e$ increases to 15 (the running time is less than 0.1 second), while the standard mSOS approach exhibits occasional performance spikes due to a higher number of iterations (up to 0.6 seconds running time).

The benefits of arrow decomposition become particularly evident at higher relaxation orders. For the second-order relaxation ($r = 2$), the standard mSOS approach requires 397 seconds for $n_e = 15$, while mSOS+NMT+AD solves the same problem
<figure><img src="image_9.png" /><figcaption>(a) Solving time in function of the number of (b) Total number of relaxation variables and elements size of the largest SDP matrix</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(a) Solving time in function of the number of (b) Total number of relaxation variables and elements size of the largest SDP matrix</figcaption></figure>

<caption>**Fig. 7:** Comparison of mSOS+NMT and ADmSOS+NMT for the third-order relaxation of a double-hinged beam problem</caption>

in just 33 seconds. Furthermore, both non-AD variants (mSOS and mSOS+NMT) exhibit numerical stability issues for larger problems, as indicated by the + superscript in Figures 4 and 7, and Table 3. These issues manifest as solver convergence problems in Mosek. In contrast, arrow-decomposition-based methods maintain numerical stability and provide reliable results across all problem sizes, offering up to 12× speedup for $n_e = 15$.

The computational advantages of arrow decomposition are most pronounced in the third-order relaxation ($r = 3$). While the AD combined with the standard mSOS
<figure><img src="image_11.png" /><figcaption>**Fig. 8:** Comparison of mSOS+NMT and ADmSOS+NMT for the fourth-order
relaxation of a double-hinged beam problem</figcaption></figure>

approach becomes computationally intractable beyond $n_e = 10$ requiring over 2.5
hours for $n_e = 8$ (Figure 4), the AD combined to mSOS with nonmixed-term basis
(mSOS+NMT+AD) solves the same problem in just 21 seconds, offering a 122×
speedup (Figure 7). The NMT-based approaches continue to solve problems efficiently
up to $n_e = 15$.

However, arrow decomposition alone can be counterproductive at higher relaxation orders. This is evident for $n_e = 9$ where mSOS+AD requires 9275 seconds compared to 3816 seconds for standard mSOS. Such degradation occurs because the number of variables for mSOS+AD is 25695, whereas for mSOS we have significantly less, 8007.

At the fourth relaxation order ($r = 4$), only the NMT-based approaches remain practically viable for problems with $n_e \ge 8$. For instance, solving $n_e = 8$ requires 55.8 hours with standard mSOS but only 36 seconds with mSOS+NMT+AD, representing a 5500× speedup.

For $r = 3$, global optimality for small problems ($n_e \le 3$) is verified, while AD-based approaches maintain global optimality certificates up to $n_e \le 9$. At $r = 4$, AD-based methods achieve tight optimality gaps ($\epsilon_r \le 10^{-5}$) up to $n_e = 10$, while still providing reliable bounds ($\epsilon_r \le 10^{-3}$) for larger problems. This improved numerical stability is evidenced by the absence of solver convergence issues (marked by $^+$) in AD-based approaches.

## 6.2 24-element modular frame

Having demonstrated the benefits of arrow decomposition on a simple structural
component with varying discretization, we now turn to a more realistic engineering
application of weight minimization of a modular frame structure, based on an exam-
ple originally introduced in [27, Section 4.1]. The structure, shown in Fig. 9, features
14 nodes and 24 elements and is subjected to combined horizontal wind loads (mag-
nitudes 1, 1, and 0.5) and vertical unit loads at beam midSpans. For simplicity, we
use normalized material properties (Young's modulus $E = 1$, density $\rho = 1$) and fixed base supports.

To create a practical design that accounts for bidirectional wind loading, we impose symmetry conditions on the structure. This symmetry, combined with structural requirements, leads to several groups of elements that must share the same cross-sectional areas: The columns satisfy $x_1 = x_4$, $x_2 = x_5$, and $x_3 = x_6$, while the horizontal beams must maintain $x_7 = x_8$, $x_9 = x_{10}$, and $x_{11} = x_{12}$. For diagonals within each story, we enforce $x_{13} = x_{14} = x_{15} = x_{16}$, $x_{17} = x_{18} = x_{19} = x_{20}$, and $x_{21} = x_{22} = x_{23} = x_{24}$. These dependencies reduce the number of independent design variables to 9.

As shown in Fig. 9b, we employ different cross-sectional shapes optimized for each element's primary function: H-sections for columns to resist axial loads and bending, I-sections for horizontal beams to maximize bending resistance, and thin-walled circular sections for diagonal braces primarily carrying axial forces. This choice of cross-sections results in a quadratic polynomial stiffness matrix $K(x)$ in the cross-sectional areas $x$.

For the arrow decomposition, we adopt a natural storey-wise partition of elements that reflects the physical structure: The first subdomain $D_1 = \{1, 4, 7, 8, 13, 14, 15, 16\}$ contains all elements of the bottom story, $D_2 = \{2, 5, 9, 10, 17, 18, 19, 20\}$ encompasses the middle story elements, and $D_3 = \{3, 6, 11, 12, 21, 22, 23, 24\}$ includes all elements of the top story. We set the compliance bound to $\bar{c} = 5,000$.

The results in Table 1 compare solution times across different relaxation orders $r$ and the four solution approaches. All methods achieve consistent lower bounds, but their computational efficiency varies significantly. At the first relaxation order ($r = 1$), all approaches perform similarly, requiring only 0.04 – 0.07 seconds. However, the benefits of decomposition become apparent at higher orders. For $r = 2$, both standard mSOS and NMT mSOS combined with AD reduce solution time from 21 seconds to under 9 seconds. The most dramatic differences appear at $r = 3$, where standard mSOS requires nearly 28 minutes while mSOS+NMT+AD completes in just 32 seconds–a 53× speedup.

Interestingly, for $r = 3$, mSOS+AD requires more time than standard mSOS due to additional variables introduced by the decomposition. However, AD consistently provides better numerical stability and tighter optimality guarantees, as evidenced by the relative optimality gaps $\epsilon_r$.

The hierarchy converges at $r = 3$, where we can verify global optimality through different means: the rank flatness condition for mSOS and mSOS+AD, and the relative optimality gap $\epsilon_r$ for NMT-based approaches. The small optimality gaps ($\epsilon_r \le 1.8 \times 10^{-6}$) for NMT methods with AD confirm the advantages of combining these techniques. Fig. 9c then shows the resulting optimal design.

# 7 Conclusion and perspectives

This paper advanced the Arrow Decomposition (AD) method beyond the framework established in [1] by developing weaker applicability conditions and extending its theoretical foundations to handle polynomial matrix inequalities. Our main contribution
<figure><img src="image_12.png" /><figcaption>Fig. 9: 24-elements modular frame: (a) discretization and boundary conditions, (b) cross-section parametrizations, and (c) optimal design.</figcaption></figure>

<table><caption>Table 1: Comparison of four moment-SOS hierarchies for a 24-element frame optimization problem at different relaxation orders *r*. The hierarchies are: standard moment-SOS (mSOS), mSOS with arrow decomposition (mSOS+AD), mSOS using nonmixed-term basis (mSOS+NMT), and mSOS combining nonmixed-term basis with arrow decomposition (mSOS+NMT+AD). For each method and relaxation order, we report: solution time (*t*) in seconds, computed lower bound (l.b.), relative global optimality gap (*ε*<sub>r</sub>), number of variables in the relaxation (*n*), and sizes of matrix constraints (where *a* × *b* indicates *a* matrix inequalities of the size S<sup>b</sup>).</caption><thead><tr><th>r</th><th>mSOS</th><th>mSOS+AD</th><th>mSOS+NMT</th><th>mSOS+NMT+AD</th></tr></thead><tbody><tr><td>1t | s|</td><td>0.07</td><td>0.04</td><td>0.07</td><td>0.04</td></tr><tr><td>1b.</td><td>5.15 × 10<sup>-2</sup></td><td>5.15 × 10<sup>-2</sup></td><td>5.15 × 10<sup>-2</sup></td><td>5.15 × 10<sup>-2</sup></td></tr><tr><td>ε<sub>r</sub></td><td>1.3</td><td>1.3</td><td>1.3</td><td>1.3</td></tr><tr><td>n</td><td>54</td><td>62</td><td>54</td><td>62</td></tr><tr><td>size</td><td>10 × 1, 1 × 10, 1 × 37</td><td>10 × 1, 1 × 10, 1 × 13, 2 × 16</td><td>10 × 1, 1 × 10, 1 × 37</td><td>10 × 1, 1 × 10, 1 × 13, 2 × 16</td></tr><tr><td>2t | s|</td><td>21.82</td><td>8.83</td><td>20.18</td><td>8.40</td></tr><tr><td>1b.</td><td>1.09 × 10<sup>-2</sup></td><td>1.09 × 10<sup>-2</sup></td><td>1.09 × 10<sup>-2</sup></td><td>1.09 × 10<sup>-2</sup></td></tr><tr><td>ε<sub>r</sub></td><td>8.2 × 10<sup>-2</sup></td><td>8.2 × 10<sup>-2</sup></td><td>8.3 × 10<sup>-2</sup></td><td>8.3 × 10<sup>-2</sup></td></tr><tr><td>n</td><td>714</td><td>1424</td><td>588</td><td>1298</td></tr><tr><td>size</td><td>10 × 10, 1 × 55, 1 × 370</td><td>10 × 10, 1 × 55, 1 × 130, 2 × 160</td><td>10 × 10, 1 × 19, 1 × 370</td><td>10 × 10, 1 × 19, 1 × 130, 2 × 160</td></tr><tr><td>3t | s|</td><td>1679.34</td><td>1913.92</td><td>46.27</td><td>31.69</td></tr><tr><td>1b.</td><td>1.18 × 10<sup>-2</sup></td><td>1.18 × 10<sup>-2</sup></td><td>1.18 × 10<sup>-2</sup></td><td>1.18 × 10<sup>-2</sup></td></tr><tr><td>ε<sub>r</sub></td><td>1.5 × 10<sup>-3</sup></td><td>3.3 × 10<sup>-4</sup></td><td>1.8 × 10<sup>-6</sup></td><td>3.0 × 10<sup>-7</sup></td></tr><tr><td>n</td><td>5004</td><td>26234</td><td>1194</td><td>3740</td></tr><tr><td>size</td><td>10 × 55, 1 × 220, 1 × 2035</td><td>10 × 55, 1 × 220, 1 × 715, 2 × 880</td><td>10 × 19, 1 × 28, 1 × 703</td><td>10 × 19, 1 × 28, 1 × 247, 2 × 304</td></tr></tbody></table>
was showing how AD could be effectively combined with moment-SOS relaxations in ways that preserve computational advantages while ensuring theoretical convergence.

To these goals, we established several theoretical improvements to the AD framework. First, we weakened the conditions for AD applicability to handle problems where the LMI/PMI need only be positive semidefinite instead of positive definite. We then showed that AD potentially produces degenerate problems without interior points and addressed this issue by developing a projection-based preprocessing method. This not only resolved the Slater condition violation but also reduced computational complexity by decreasing both the number of additional variables and matrix inequality sizes.

In extending AD to PMIs, we provided two approaches: direct application to POP problems ("prior to mSOS") and application at the relaxation level ("posterior to mSOS"). Notably, we proved that the posterior approach can achieve the benefits of prior application without the computational overhead of additional variables in the monomial basis.

Our numerical experiments focused on compliance and weight minimization problems in structural engineering. These examples provided physical interpretations for the additional variables introduced by AD. The results showed that mSOS+AD and its variants significantly improve both solution times and numerical accuracy, particularly for problems combining high dimensionality with low relaxation orders.

This work opens several promising directions for future research. One possibility is to extend the results of Section 4.3 to cases where the range and null space of the matrices $A_k(x)$ may depend on $x$. Another key area is the development of automated methods for generating optimal decompositions that balance matrix sizes against additional variable counts. Further opportunities lie in extending applications to other optimization problems with arrow-type LMI/PMIs, particularly in continuum topology optimization across various physical domains. The integration of AD with the correlative sparsity method presents another avenue for investigation, as does the study of potential combinations with the finest block diagonal decomposition technique presented in [33]. These extensions could further enhance the practical applicability and computational efficiency of the AD method.

# A Appendix

## A.1 Technical lemmas

Here, we present few technical lemmas that are focused more on the sparsity in the arrow decomposition technique presented in this paper. In order to do so, let $\mathbf{G}$ be a matrix with an arrow shape (recall Section 3) and let $\mathcal{I}$ be the index set of the matrix $\mathbf{A}$, and $(\mathcal{I}_k)_{k \in [p]}$ its partition.

The first result shows the existence and the construction of a matrix $\mathbf{\Pi}_k$ for each $k \in [p]$, such that the equality $\mathbf{D}_k = \sum_{\mathcal{I}_{k,l} \neq \emptyset} (\mathbf{D}_{k,l})_{ij} - \sum_{\mathcal{I}_{l,k} \neq \emptyset} (\mathbf{D}_{l,k})_{ij}$, can be written in the compact form $\mathbf{D}_k = \mathbf{\Pi}_k \mathbf{D}$.

**Lemma 4.** Let $n_{\mathcal{I}} = \sum_{k=1}^p \sum_{\ell>k} |\mathcal{I}_{k,\ell}|$ and $\mathbf{D} \in \mathbb{R}^{n_{\mathcal{I}} \times m}$ be a matrix containing all the variables involved in each matrix $\mathbf{D}_{k,\ell}$, i.e., $\mathbf{D} = \{(\mathbf{D}_{k,\ell})_{ij} \neq 0 : k < \ell, (i,j) \in$
$\mathcal{I}_{k,\ell} \times [m]$}. Then there exists a matrix $\Pi_k \in \mathbb{R}^{|\mathcal{I}_k| \times n_\mathcal{I}}$ such that Equation (12) can be written in the compact form

$$D_k = \Pi_k D. \qquad (35)$$

*Proof* Let $\bar{D}_{k,\ell} = \{(\bar{D}_{k,\ell})_{ij} \neq 0 : (i,j) \in \mathcal{I}_{k,\ell} \times [m]\}$. By choosing the order $<$ defined by $(a,b) < (k,\ell) \Leftrightarrow a \le k$ and $b < \ell$, we can write the matrix $D$ as a block-wise concatenation of the matrices $\bar{D}_{k,\ell}$, i.e., $D = [\dots \bar{D}_{k,\ell} \dots]^T$. Now, we define the matrix $\Pi_k \in \mathbb{R}^{|\mathcal{I}_k| \times n_\mathcal{I}}$ by

$$ (\Pi_k)_{ij} = \begin{cases} 1 & \text{if } \exists \ell > k : \mathcal{I}_{k,\ell} \neq \emptyset, i \in \mathcal{P}_{k,\ell} \text{ and } j \in \mathcal{S}_{k,\ell}, \\ -1 & \text{if } \exists \ell < k : \mathcal{I}_{\ell,k} \neq \emptyset, i \in \mathcal{P}_{k,\ell} \text{ and } j \in \mathcal{S}_{\ell,k}, \\ 0 & \text{otherwise,} \end{cases} \qquad (36) $$

where the set $\mathcal{S}_{k,\ell}$ enumerates the row positions of the block $\bar{D}_{k,\ell}$ in $D$, and is defined by $\mathcal{S}_{k,\ell} = \{s_{k,\ell} + 1, \dots, s_{k,\ell} + |\bar{\mathcal{I}}_{k,\ell}|\}$ with $\bar{\mathcal{I}}_{k,\ell} = \{i \in \mathcal{I}_{k,\ell} : (\bar{D}_{k,\ell})_{i,j} \neq 0\}$ and $s_{k,\ell} = \sum_{(a,b)<(k,\ell)} |\bar{\mathcal{I}}_{k,\ell}|$; and the set $\mathcal{P}_{k,\ell}$ enumerates the positions of the elements of $\mathcal{I}_{k,\ell}$ in $\mathcal{I}_k$, i.e. $\mathcal{P}_{k,\ell} = \{e \in [|\mathcal{I}_k|] : \exists j \in \mathcal{I}_{k,\ell} \text{ s.t. } j = j_e\}$. Notice that, for $s \in \mathcal{S}_{k,\ell}$ and $i \in [|\mathcal{S}_{k,\ell}|]$, we have $(\bar{D})_{sj} = (\bar{D}_{k,\ell})_{ij}$ for all $j \in [m]$.

Now, for all $k \in [p]$ and $j \in [m]$, we have

$$ \begin{aligned} (\Pi_k D)_{ij} &= \sum_{s=1}^{n_\mathcal{I}} (\Pi_k)_{is} (D)_{sj} \\ &= \sum_{\substack{k:k<\ell \\ \mathcal{I}_{k,\ell} \neq \emptyset}} \sum_{s \in \mathcal{S}_{k,\ell}} (D)_{sj} - \sum_{\substack{\ell:\ell<k \\ \mathcal{I}_{\ell,k} \neq \emptyset}} \sum_{s \in \mathcal{S}_{\ell,k}} (D)_{sj} \\ &= \sum_{\substack{k:k<\ell \\ \mathcal{I}_{k,\ell} \neq \emptyset}} (\bar{D}_{k,\ell})_{ij} - \sum_{\substack{\ell:\ell<k \\ \mathcal{I}_{\ell,k} \neq \emptyset}} (\bar{D}_{\ell,k})_{ij}, \\ &= \sum_{\substack{k:k<\ell \\ \mathcal{I}_{k,\ell} \neq \emptyset}} (\bar{D}_{k,\ell})_{ij} - \sum_{\substack{\ell:\ell<k \\ \mathcal{I}_{\ell,k} \neq \emptyset}} (\bar{D}_{\ell,k})_{ij}, \text{ with } (\bar{D}_{k,\ell})_{ij} = \emptyset \text{ whenever } i \notin \mathcal{P}_{k,\ell}, \\ &= (\bar{D}_k)_{ij}. \end{aligned} \qquad \square $$

Next, we present a link between the matrices $\Pi_k$ defined by (4) for the sets $\hat{\mathcal{I}}_k$, and $\hat{\Pi}_k$ defined by (4) for the sets $\hat{\mathcal{I}}_k$.

**Lemma 5.** Let $d \in \mathbb{N}^*$ and $n_{\hat{\mathcal{I}}} = L_d n_\mathcal{I}$, where $n_\mathcal{I} = \sum_{k=1}^p \sum_{\ell>k} |\mathcal{I}_{\ell,k}|$. For $k \in [p]$, consider the matrix $\hat{\Pi}_k \in \mathbb{R}^{|\hat{\mathcal{I}}_k| \times n_{\hat{\mathcal{I}}}}$ defined by (4) for the set $\hat{\mathcal{I}}_k$. Then, we have $\hat{\Pi}_k = \Pi_k \otimes I$, where the matrix $\Pi_k$ is associated to $\mathcal{I}_k$ as in (35), and $I \in \mathbb{S}^{L_d}$.

*Proof* First, recall that the matrix $\hat{\Pi}_k \in \mathbb{R}^{|\hat{\mathcal{I}}_k| \times n_{\hat{\mathcal{I}}}}$ is defined by

$$ (\hat{\Pi}_k)_{\hat{\hat{i}}\hat{\hat{j}}} = \begin{cases} 1 & \text{if } \exists \ell > k : \hat{\mathcal{I}}_{k,\ell} \neq \emptyset, \hat{i} \in \hat{\mathcal{P}}_{k,\ell} \text{ and } \hat{j} \in \hat{\mathcal{S}}_{k,\ell}, \\ -1 & \text{if } \exists \ell < k : \hat{\mathcal{I}}_{\ell,k} \neq \emptyset, \hat{i} \in \hat{\mathcal{P}}_{\ell,k} \text{ and } \hat{j} \in \hat{\mathcal{S}}_{\ell,k}, \\ 0 & \text{otherwise,} \end{cases} $$
where $\hat{S}_{k,l} = \{\hat{s}_{k,l} + 1, \dots, \hat{s}_{k,l} + |\hat{\mathcal{I}}_{k,l}|\}$ with $\hat{\mathcal{I}}_{k,l} = \{i \in \mathcal{I}_{k,l} : (\hat{D}_{k,l})_{ij} \neq 0\}$, $\hat{s}_{k,l} = \sum_{(a,b)<(k,l)} |\hat{\mathcal{I}}_{k,l}|$, and $\hat{P}_{k,l} = \{\hat{j} \in [[\hat{\mathcal{I}}_{k,l}]] : \exists \hat{e} \in \hat{\mathcal{I}}_{k,l} \text{ such that } \hat{e} = \hat{e}_{\hat{j}}\}$.

Let $(\hat{i}, \hat{j}) \in |\hat{\mathcal{I}}_k| \times [n_{\hat{I}}]$, $(i, j) \in |\mathcal{I}_k| \times [n_{\mathcal{I}}]$ and $i_d, j_d \in [d]$ such that $\hat{i} = (i-1)L_d + i_d$ and $\hat{j} = (j-1)L_d + j_d$. Because the identity matrix $\mathbf{I}_d$ is nonzero only when $i_d = j_d$, we have

$$ (\mathbf{\Pi}_k \otimes \mathbf{I}_d)_{\hat{i}\hat{j}} = \begin{cases} (\mathbf{\Pi}_k)_{ij} & \text{if } \hat{i} = (i-1)L_d + i_d \text{ and } \hat{j} = (j-1)L_d + i_d \\ 0 & \text{otherwise.} \end{cases} \quad (37) $$

Moreover, we will show that $\hat{j} \in \hat{\mathcal{P}}_{k,l}$ whenever $j \in \mathcal{P}_{k,l}$, and $\hat{i} \in \hat{\mathcal{S}}_{k,l}$ whenever $i \in \mathcal{S}_{k,l}$. Let $j \in \mathcal{P}_{k,l}$, then $j \in [[\mathcal{I}_k]]$ and $\exists e \in \mathcal{I}_{k,l}$ such that $e = e_j$. Therefore, we have $\hat{j} \in [[\hat{\mathcal{I}}_k]]$, and for $\hat{e} = (e-1)L_d + j_d \in \hat{\mathcal{I}}_{k,l}$, we have $\hat{e} = \hat{e}_{\hat{j}}$. It follows that $\hat{j} \in \hat{\mathcal{P}}_{k,l}$. Now, let $i \in \mathcal{S}_{k,l}$. There exists $i_{k,l} \in [[\bar{\mathcal{I}}_{k,l}]]$ such that $i = s_{k,l} + i_{k,l}$. Thus we have $\hat{i} = (s_{k,l} + i_{k,l} - 1)L_d + i_d = L_d s_{k,l} + (i_{k,l} - 1)L_d + i_d$. Since $\hat{s}_{k,l} = L_d s_{k,l}$ and $(i_{k,l} - 1)L_d + i_d \in [[\hat{\mathcal{I}}_{k,l}]]$, we get $\hat{i} \in \hat{\mathcal{S}}_{k,l}$.

Therefore, for $\hat{i} = (i-1)L_d + i_d$ and $\hat{j} = (j-1)L_d + i_d$, we obtain

$$ (\mathbf{\Pi}_k \otimes \mathbf{I}_d)_{\hat{i}\hat{j}} = \begin{cases} 1 & \text{if } \exists \ell > k : \hat{\mathcal{I}}_{k,\ell} \neq \emptyset, \hat{i} \in \hat{\mathcal{P}}_{k,\ell} \text{ and } \hat{j} \in \hat{\mathcal{S}}_{k,\ell}, \\ -1 & \text{if } \exists \ell < k : \hat{\mathcal{I}}_{\ell,k} \neq \emptyset, \hat{i} \in \hat{\mathcal{P}}_{\ell,k} \text{ and } \hat{j} \in \hat{\mathcal{S}}_{\ell,k}, \\ 0 & \text{otherwise,} \end{cases} = \hat{\mathbf{\Pi}}_k. $$

□

## A.2 Physical interpretation of the additional variables and their elimination

In this section, we provide a physical interpretation for the additionally introduced variables $c$ and $d$. To this goal, we deal with it from a prior-to-mSOS point of view and we exploit the equivalence of (29) with (32) and write the prior AD decomposition of (29) as

$$ \begin{align} \tilde{\gamma}_{\text{AD}}^* &= \min_{\mathbf{x}, \mathbf{u}, \mathbf{d}} \sum_{k=1}^{p} c_k, \nonumber \\ \text{s.t.} \quad & \mathbf{K}_k(\mathbf{x})\mathbf{u}_k - (\mathbf{f}_k(\mathbf{x}) + \mathbf{\Pi}_k \mathbf{d}) = \mathbf{0}, \mathbf{k} \in [p], \nonumber \\ & \bar{w} - \sum_{e=1}^{n_e} \ell_e \rho_e x_e \geq 0, \tag{38} \\ & \mathbf{f}_k(\mathbf{x})^T \mathbf{u}_k = c_k, \nonumber \\ & \mathbf{x} \geq \mathbf{0}, \nonumber \end{align} $$

in which for $k \in [p]$, $\mathbf{u}_k = \mathbf{u}_{\mathcal{I}_k} \in \mathbb{R}^{|\mathcal{I}_k|}$ is a part of the displacement vector $\mathbf{u}$ corresponding to the generalized nodal displacements related to the subdomain $\mathcal{D}_k$. According to [1, Theorem 5], we have $\tilde{\gamma}_{\text{AD}}^* = \gamma_{\text{AD}}^* = \gamma^*$.

From (38), it follows that $c_k$ has the meaning of the potential energy of the external forces (compliance) of the elements in the subset $\mathcal{I}_k$. Clearly, $\sum_{k=1}^p c_k$ provides the overall compliance $\gamma$.
Furthermore, the equilibrium equations given in (38) constitute equilibrium of the substructure formed by elements in the partition $\mathcal{D}_k$. However, due to the sub-structures formed by elements $\mathcal{D}_k$ being connected in reality to other elements, i.e., $\forall k \exists l : (\mathcal{I}_{k,l} \cup \mathcal{I}_{l,k}) \neq \emptyset$, it is needed to introduce so-called interface forces $d_k$ that represent the mechanical interaction between the isolated elements $\mathcal{D}_k$ and the remainder of the structure $[n_e] \setminus \mathcal{D}_k$. Following Newton's Third Law, these forces maintain the equilibrium conditions that existed in the original complete structure. For each interface where the structure is sectioned, the forces and moments acting on the isolated portion are equal and opposite to those acting on the remaining structure at that interface.

**Example 5.** Consider the structure shown in Fig. 10a that contains three structural elements 1–3, four nodes a–d, and we set $\mathcal{D}_1 = 1$, $\mathcal{D}_2 = 2$ and $\mathcal{D}_3 = 3$. Based on the kinematic boundary conditions, there is one degree of freedom (rotation) allowed at the node a, which we denote as $\{1\}$. At the nodes b and c, both translations and rotations are allowed, resulting in 3 degrees of freedom per node. We label these as $\{2, 3, 4\}$ and $\{5, 6, 7\}$, respectively. Finally, the node d prevents translations and rotation, so that there is no degree of freedom. Since element 1 connects nodes a and b, we have $\mathcal{I}_1 = \{1, 2, 3, 4\}$. Analogously, we get $\mathcal{I}_2 = \{2, 3, 4, 5, 6, 7\}$, and $\mathcal{I}_3 = \{5, 6, 7\}$.

Furthermore, we evaluate the intersections as $\mathcal{I}_{1,2} = \{2, 3, 4\}$ and $\mathcal{I}_{2,3} = \{5, 6, 7\}$. Because of $f(\mathbf{x}) = [0 \ 0 \ -q_1 \ 0 \ 0 \ q_2 \ 0]^T \in \mathbb{R}^{n_{\text{dof}} \times 1}$, we need to introduce only one variable for each intersection in $\mathcal{I}_{k,l}$. In particular, we introduce $d_{1,2}^{(1)}$, $d_{1,2}^{(2)}$ and $d_{1,2}^{(3)}$ which denote the horizontal, vertical, and moment internal forces that balance the interaction of the domains $\mathcal{D}_1$ and $\mathcal{D}_2$ at the node b. Analogously, we define $d_{2,3}^{(1)}$, $d_{2,3}^{(2)}$ and $d_{2,3}^{(3)}$ for the horizontal, vertical and moment internal forces balancing interaction between domains $\mathcal{D}_2$ and $\mathcal{D}_3$. This yields the free-body diagram shown in Fig. 10b.

## Additional variables elimination

Next, we consider the variable elimination procedure and the related physical interpretation. To this goal, let $\mathbf{x} \ge \mathbf{0}$ and $\tilde{\mathbf{x}} > \mathbf{0}$. By construction of the stiffness matrix, the null space of the matrix $\mathbf{K}_k(\tilde{\mathbf{x}})$ is constant and $\text{Null}(\mathbf{K}_k(\tilde{\mathbf{x}})) \subseteq \text{Null}(\mathbf{K}_k(\mathbf{x}))$. Thus, for any $\mathbf{x} \in \mathbb{R}^{n_x}$, if $\mathbf{v} \in \text{Null}(\mathbf{K}_k(\mathbf{x}))$, then by (28), we have $\mathbf{K}_0\mathbf{v} + \sum_{e \in \mathcal{D}_k} \mathbf{K}_e^{(1)}x_e\mathbf{v} + \sum_{e \in \mathcal{D}_k} \mathbf{K}_e^{(2)}x_e^2\mathbf{v} + \sum_{e \in \mathcal{D}_k} \mathbf{K}_e^{(3)}x_e^3\mathbf{v} = \mathbf{0}$. Because the monomials 1, $x_k^2$, $x_k^3$ are linearly independent and $\mathbf{K}_0$, $\mathbf{K}_e^{(i)} \succeq \mathbf{0}$ for $i \in \{1, 2, 3\}$, we get $\mathbf{K}_0\mathbf{v} = \mathbf{0}$ and $\mathbf{K}_e^{(i)}\mathbf{v} = \mathbf{0}$ for all $e \in [n_e]$ and $i$. Therefore, the null space of $\mathbf{K}_k(\mathbf{x})$ remains in the intersection of the null spaces of $\mathbf{K}_0$, $\mathbf{K}_e^{(1)}$, $\mathbf{K}_e^{(2)}$ and $\mathbf{K}_e^{(3)}$.

Moreover, in the topology optimization, there exists cheaper alternatives, (see [34, 35]), as the null space has also a physical interpretation of rigid body displacements or rotations. This makes the application of Proposition 4 suitable.

**Example 6.** Consider again the setting of Example 5. For $\mathcal{D}_1$, we have the equilibrium system $\mathbf{K}_1\mathbf{u}_1 = \mathbf{f}_1 + \mathcal{D}_1$, in which $I_1(x_1)$ is a non-negative polynomial of degree at
<figure><img src="image_13.png" /><figcaption>Fig. 10: Physical interpretation of the variables $d_k$: (a) A beam composed of three segments; (b) Free-body diagram showing internal forces and moments at domain interfaces.</figcaption></figure>

most three, non-negative constraints $E_1, \ell_1 \in \mathbb{R}_{>0}$,

$$ K_1(x_1) = \mathcal{E}_{\mathcal{I}_1}^T \begin{bmatrix} \frac{4E_1 I_1(x_1)}{\ell_1} & -\frac{6E_1 I_1(x_1)}{\ell_1^2} & \frac{2E_1 I_1(x_1)}{\ell_1} \\ 0 & \frac{E_1 x_1}{\ell_1} & 0 \\ -\frac{6E_1 I_1(x_1)}{\ell_1^2} & 0 & \frac{12E_1 I_1(x_1)}{\ell_1^3} & -\frac{6E_1 I_1(x_1)}{\ell_1^2} \\ \frac{2E_1 I_1(x_1)}{\ell_1} & 0 & -\frac{6E_1 I_1(x_1)}{\ell_1^2} & \frac{4E_1 I_1(x_1)}{\ell_1} \end{bmatrix} \mathcal{E}_{\mathcal{I}_1}, $$

and $f_1 + D_1 = \mathcal{E}_{\mathcal{I}_1}^T [0 \ d_{1,2}^{(1)} \ d_{1,2}^{(2)} \ d_{1,2}^{(3)}]^T$. For all $x_1 \ge 0$, the stiffness matrix $K_1(x_1)$ has one singular eigenvalue associated with the eigenvector $n_1 = [1 \ 0 \ \ell_1 \ 1]^T$. Hence, $(f_1 + D_1)^T n_1 = 0$ results in the equality

$$ \circ_a: \ d_{1,2}^{(2)}\ell_1 + d_{1,2}^{(3)} = 0, $$

which is the moment static equilibrium of the substructure $D_1$ around the point a, which is the only rigid body mode not prevented by the kinematic boundary conditions. Finally, the range space bases evaluate as $P_1 = \mathcal{E}_{\mathcal{I}_1}^T [0 - \ell_1 \ 1]^T$.

Further, let us consider $D_2$ and the equilibrium system $K_2 u_2 = f_2 + D_2$. Then, for $I_2(x_2)$ being a non-negative polynomial of degree at most three and non-negative
constraints $E_2, \ell_2 \in \mathbb{R}_{>0}$, we have

$$ K_2(x_2) = \mathcal{E}_{\mathcal{I}_2}^T \begin{bmatrix} \frac{E_2 x_2}{\ell_2} & 0 & 0 & -\frac{E_2 x_2}{\ell_2} & 0 & 0 \\ 0 & \frac{12 E_2 I_2(x_2)}{\ell_2^3} & \frac{6 E_2 I_2(x_2)}{\ell_2^2} & 0 & -\frac{12 E_2 I_2(x_2)}{\ell_2^3} & \frac{6 E_2 I_2(x_2)}{\ell_2^2} \\ 0 & \frac{6 E_2 I_2(x_2)}{\ell_2^2} & \frac{4 E_2 I_2(x_2)}{\ell_2} & 0 & -\frac{6 E_2 I_2(x_2)}{\ell_2^3} & \frac{2 E_2 I_2(x_2)}{\ell_2} \\ -\frac{E_2 x_2}{\ell_2} & 0 & 0 & \frac{E_2 x_2}{\ell_2} & 0 & 0 \\ 0 & -\frac{12 E_2 I_2(x_2)}{\ell_2^3} & -\frac{6 E_2 I_2(x_2)}{\ell_2^2} & 0 & \frac{12 E_2 I_2(x_2)}{\ell_2^3} & -\frac{6 E_2 I_2(x_2)}{\ell_2^2} \\ 0 & \frac{6 E_2 I_2(x_2)}{\ell_2^2} & \frac{2 E_2 I_2(x_2)}{\ell_2} & 0 & -\frac{6 E_2 I_2(x_2)}{\ell_2^3} & \frac{4 E_2 I_2(x_2)}{\ell_2} \end{bmatrix} \mathcal{E}_{\mathcal{I}_2} $$

and $f_2 + D_2 = \mathcal{E}_2^T [-d_{1,2}^{(1)} q_1 - d_{1,2}^{(2)} - d_{1,2}^{(3)} d_{2,3}^{(1)} d_{2,3}^{(2)} - q_2 d_{2,3}^{(3)}]^T$, with point loads $q_1, q_2 \in \mathbb{R}$ as in Fig. 10. For $x_2 \ge 0$, the stiffness matrix $K_2(x_2)$ has singularities associated to the three Null space bases $n_1 = [1 \ 0 \ 0 \ 1 \ 0 \ 0]^T$, $n_2 = [0 \ 1 \ 0 \ 0 \ 1 \ 0]^T$ and $n_3 = [0 \ 0 \ 1 \ 0 \ \ell_2 \ 1]^T$. These then correspond to static equilibria for the three rigid body modes not restricted at $D_2$:

$$ \rightarrow: -d_{1,2}^{(1)} + d_{2,3}^{(1)} = 0, $$

$$ \uparrow: -d_{1,2}^{(2)} + d_{2,3}^{(2)} = q_2 - q_1, $$

$$ \circled: -d_{1,2}^{(3)} + d_{2,3}^{(3)} + \ell_2 d_{2,3}^{(2)} = \ell_2 q_2. $$

Hence, the range space bases evaluate as $P_2 = \mathcal{E}_{\mathcal{I}_2}^T \begin{bmatrix} -1 & 0 & 0 \\ 0 & -1 & -\ell_2 \\ 0 & 0 & -1 \end{bmatrix}^T$.

Finally, for $D_3$, $E_3, \ell_3 \in \mathbb{R}_{>0}$ and a non-negative polynomial $I_3(x_3)$ of degree at most 3, we have

$$ K_3 = \mathcal{E}_{\mathcal{I}_3}^T \begin{bmatrix} \frac{E_3 x_3}{\ell_3} & 0 & 0 \\ 0 & \frac{12 E_3 I_3(x_3)}{\ell_3^3} & \frac{6 E_3 I_3(x_3)}{\ell_3^2} \\ 0 & \frac{6 E_3 I_3(x_3)}{\ell_3^2} & \frac{4 E_3 I_3(x_3)}{\ell_3} \end{bmatrix} \mathcal{E}_{\mathcal{I}_3}, f_3 + D_3 = \mathcal{E}_{\mathcal{I}_3}^T \begin{bmatrix} -d_{2,3}^{(1)} \\ -d_{2,3}^{(2)} \\ -d_{2,3}^{(3)} \end{bmatrix}, $$

in which $K_3(x_3)$ is regular due to prevented translations and rotation by the clamped support at the right end the structure, recall Fig. 10. Hence, $P_3 = I_3$.

Now, we combine the Null space equations into a single system, and express its solution as
$$ D = \begin{bmatrix} 0 & 0 & 0 \\ \frac{(q_1 \ell_2^2 + \ell_1 q_1 \ell_2 + q_1 - q_2)}{(2 \ell_1^2 + 2 \ell_1 \ell_2 + \ell_2^2 + 2)} & \frac{-(\ell_1(q_1 - q_2) - (\ell_2 q_1 (\ell_2^2 + 2))/2)}{(2 \ell_1^2 + 2 \ell_1 \ell_2 + \ell_2^2 + 2) - (\ell_2 q_1)/2} & 0 \\ 0 & \frac{q_2 - (2 q_1 \ell_1^2 + \ell_2 q_1 \ell_1 + q_1 + q_2)}{(2 \ell_1^2 + 2 \ell_1 \ell_2 + \ell_2^2 + 2)} & \frac{-(\ell_1(q_1 - q_2) - \ell_2(q_2 + (q_1(2 \ell_1^2 + 2))/2))}{(2 \ell_1^2 + 2 \ell_1 \ell_2 + \ell_2^2 + 2)} \end{bmatrix} + \begin{bmatrix} 1 & 0 & 0 \\ 0 & -\ell_2/\ell_1 & -1/\ell_1 \\ 0 & \ell_2 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} d_R^{(1)} \\ d_R^{(2)} \\ d_R^{(3)} \end{bmatrix}, $$

which allows us to substitute the original variables $D$ as well as to reduce the sizes of matrix inequalities for the domains $D_1$ and $D_2$ to 4 and 4 from the original 5 and 7.

### A.3 Tables

Here, we present a detailed data (Tables 2–5) corresponding to Figures 2–8 presented in Section 6.
<table><caption>**Table 2:** Comparison of four moment-SOS hierarchies for the first-order relaxation of a double-hinged beam problem with varying number of elements ($n_e$). The hierarchies are: standard moment-SOS (mSOS), mSOS with arrow decomposition (mSOS+AD), mSOS using nonmixed-term basis (mSOS+NMT), and mSOS combining nonmixed-term basis with arrow decomposition (mSOS+NMT+AD). For each method and problem size, we report: solution time ($t$) in seconds, computed lower bound (l.b.), number of variables in the relaxation ($n$), and sizes of matrix constraints (where $a \times b$ indicates $a$ matrix constraints of size $b^a$).</caption><thead><tr><th>n<sub>e</sub></th><th>t [s]</th><th>mSOS</th><th>mSOS+AD</th><th>mSOS+NMT</th><th>mSOS+NMT+AD</th></tr></thead><tbody><tr><td rowspan="3">1</td><td>l.b.</td><td>0.01<br>3.98 &times; 10<sup>-2</sup></td><td>0.01<br>3.98 &times; 10<sup>-2</sup></td><td>0.01<br>3.98 &times; 10<sup>-2</sup></td><td>0.01<br>3.98 &times; 10<sup>-2</sup></td></tr><tr><td>n</td><td>5</td><td>5</td><td>5</td><td>5</td></tr><tr><td>size</td><td>3 &times; 1, 2 &times; 3</td><td>3 &times; 1, 2 &times; 3</td><td>3 &times; 1, 2 &times; 3</td><td>3 &times; 1, 2 &times; 3</td></tr><tr><td rowspan="3">2</td><td>l.b.</td><td>0.02<br>1.99 &times; 10<sup>-2</sup></td><td>0.02<br>1.99 &times; 10<sup>-2</sup></td><td>0.02<br>1.99 &times; 10<sup>-2</sup></td><td>0.02<br>1.99 &times; 10<sup>-2</sup></td></tr><tr><td>n</td><td>9</td><td>9</td><td>9</td><td>9</td></tr><tr><td>size</td><td>4 &times; 1, 1 &times; 4, 1 &times; 6</td><td>4 &times; 1, 1 &times; 4, 1 &times; 6</td><td>4 &times; 1, 1 &times; 4, 1 &times; 6</td><td>4 &times; 1, 1 &times; 4, 1 &times; 6</td></tr><tr><td rowspan="3">3</td><td>l.b.</td><td>0.02<br>1.32 &times; 10<sup>-2</sup></td><td>0.02<br>1.32 &times; 10<sup>-2</sup></td><td>0.02<br>1.32 &times; 10<sup>-2</sup></td><td>0.02<br>1.32 &times; 10<sup>-2</sup></td></tr><tr><td>n</td><td>14</td><td>16</td><td>14</td><td>16</td></tr><tr><td>size</td><td>5 &times; 1, 1 &times; 5, 1 &times; 9</td><td>5 &times; 1, 1 &times; 4, 1 &times; 5, 1 &times; 7</td><td>5 &times; 1, 1 &times; 5, 1 &times; 9</td><td>5 &times; 1, 1 &times; 4, 1 &times; 5, 1 &times; 7</td></tr><tr><td rowspan="3">4</td><td>l.b.</td><td>0.02<br>9.89 &times; 10<sup>-2</sup></td><td>0.02<br>9.89 &times; 10<sup>-3</sup></td><td>0.02<br>9.89 &times; 10<sup>-3</sup></td><td>0.02<br>9.89 &times; 10<sup>-3</sup></td></tr><tr><td>n</td><td>20</td><td>23</td><td>20</td><td>23</td></tr><tr><td>size</td><td>6 &times; 1, 1 &times; 6, 1 &times; 12</td><td>6 &times; 1, 2 &times; 4, 1 &times; 6, 1 &times; 7</td><td>6 &times; 1, 1 &times; 6, 1 &times; 12</td><td>6 &times; 1, 2 &times; 4, 1 &times; 6, 1 &times; 7</td></tr><tr><td rowspan="3">5</td><td>l.b.</td><td>0.03<br>7.91 &times; 10<sup>-3</sup></td><td>0.02<br>7.91 &times; 10<sup>-3</sup></td><td>0.03<br>7.91 &times; 10<sup>-3</sup></td><td>0.02<br>7.91 &times; 10<sup>-3</sup></td></tr><tr><td>n</td><td>27</td><td>31</td><td>27</td><td>31</td></tr><tr><td>size</td><td>7 &times; 1, 1 &times; 7, 1 &times; 15</td><td>7 &times; 1, 3 &times; 4, 2 &times; 7</td><td>7 &times; 1, 1 &times; 7, 1 &times; 15</td><td>7 &times; 1, 3 &times; 4, 2 &times; 7</td></tr><tr><td rowspan="3">6</td><td>l.b.</td><td>0.03<br>6.58 &times; 10<sup>-3</sup></td><td>0.02<br>6.58 &times; 10<sup>-3</sup></td><td>0.03<br>6.58 &times; 10<sup>-3</sup></td><td>0.02<br>6.58 &times; 10<sup>-3</sup></td></tr><tr><td>n</td><td>35</td><td>40</td><td>35</td><td>40</td></tr><tr><td>size</td><td>8 &times; 1, 1 &times; 8, 1 &times; 18</td><td>8 &times; 1, 4 &times; 4, 1 &times; 7, 1 &times; 8</td><td>8 &times; 1, 1 &times; 8, 1 &times; 18</td><td>8 &times; 1, 4 &times; 4, 1 &times; 7, 1 &times; 8</td></tr><tr><td rowspan="3">7</td><td>l.b.</td><td>0.04<br>5.64 &times; 10<sup>-3</sup></td><td>0.03<br>5.64 &times; 10<sup>-3</sup></td><td>0.04<br>5.64 &times; 10<sup>-3</sup></td><td>0.03<br>5.64 &times; 10<sup>-3</sup></td></tr><tr><td>n</td><td>44</td><td>50</td><td>44</td><td>50</td></tr><tr><td>size</td><td>9 &times; 1, 1 &times; 9, 1 &times; 21</td><td>9 &times; 1, 5 &times; 4, 1 &times; 7, 1 &times; 9</td><td>9 &times; 1, 1 &times; 9, 1 &times; 21</td><td>9 &times; 1, 5 &times; 4, 1 &times; 7, 1 &times; 9</td></tr><tr><td rowspan="3">8</td><td>l.b.</td><td>0.04<br>4.94 &times; 10<sup>-3</sup></td><td>0.03<br>4.94 &times; 10<sup>-3</sup></td><td>0.04<br>4.94 &times; 10<sup>-3</sup></td><td>0.03<br>4.94 &times; 10<sup>-3</sup></td></tr><tr><td>n</td><td>54</td><td>61</td><td>54</td><td>61</td></tr><tr><td>size</td><td>10 &times; 1, 1 &times; 10, 1 &times; 24</td><td>10 &times; 1, 6 &times; 4, 1 &times; 7, 1 &times; 10</td><td>10 &times; 1, 1 &times; 10, 1 &times; 24</td><td>10 &times; 1, 6 &times; 4, 1 &times; 7, 1 &times; 10</td></tr><tr><td rowspan="3">9</td><td>l.b.</td><td>0.05<br>4.39 &times; 10<sup>-3</sup></td><td>0.09<br>4.39 &times; 10<sup>-3</sup></td><td>0.05<br>4.39 &times; 10<sup>-3</sup></td><td>0.03<br>4.39 &times; 10<sup>-3</sup></td></tr><tr><td>n</td><td>65</td><td>73</td><td>65</td><td>73</td></tr><tr><td>size</td><td>11 &times; 1, 1 &times; 11, 1 &times; 27</td><td>11 &times; 1, 7 &times; 4, 1 &times; 7, 1 &times; 11</td><td>11 &times; 1, 1 &times; 11, 1 &times; 27</td><td>11 &times; 1, 7 &times; 4, 1 &times; 7, 1 &times; 11</td></tr><tr><td rowspan="3">10</td><td>l.b.</td><td>0.12<br>3.95 &times; 10<sup>-3</sup></td><td>0.03<br>3.95 &times; 10<sup>-3</sup></td><td>0.11<br>3.95 &times; 10<sup>-3</sup></td><td>0.03<br>3.95 &times; 10<sup>-3</sup></td></tr><tr><td>n</td><td>77</td><td>86</td><td>77</td><td>86</td></tr><tr><td>size</td><td>12 &times; 1, 1 &times; 12, 1 &times; 30</td><td>12 &times; 1, 8 &times; 4, 1 &times; 7, 1 &times; 12</td><td>12 &times; 1, 1 &times; 12, 1 &times; 30</td><td>12 &times; 1, 8 &times; 4, 1 &times; 7, 1 &times; 12</td></tr><tr><td rowspan="3">11</td><td>l.b.</td><td>0.61<br>3.59 &times; 10<sup>-3</sup></td><td>0.04<br>3.59 &times; 10<sup>-3</sup></td><td>0.59<br>3.58 &times; 10<sup>-3</sup></td><td>0.04<br>3.59 &times; 10<sup>-3</sup></td></tr><tr><td>n</td><td>90</td><td>100</td><td>90</td><td>100</td></tr><tr><td>size</td><td>13 &times; 1, 1 &times; 13, 1 &times; 33</td><td>13 &times; 1, 9 &times; 4, 1 &times; 7, 1 &times; 13</td><td>13 &times; 1, 1 &times; 13, 1 &times; 33</td><td>13 &times; 1, 9 &times; 4, 1 &times; 7, 1 &times; 13</td></tr><tr><td rowspan="3">12</td><td>l.b.</td><td>0.14<br>3.29 &times; 10<sup>-3</sup></td><td>0.04<br>3.29 &times; 10<sup>-3</sup></td><td>0.14<br>3.29 &times; 10<sup>-3</sup></td><td>0.05<br>3.29 &times; 10<sup>-3</sup></td></tr><tr><td>n</td><td>104</td><td>115</td><td>104</td><td>115</td></tr><tr><td>size</td><td>14 &times; 1, 1 &times; 14, 1 &times; 36</td><td>14 &times; 1, 10 &times; 4, 1 &times; 7, 1 &times; 14</td><td>14 &times; 1, 1 &times; 14, 1 &times; 36</td><td>14 &times; 1, 10 &times; 4, 1 &times; 7, 1 &times; 14</td></tr><tr><td rowspan="3">13</td><td>l.b.</td><td>0.13<br>3.04 &times; 10<sup>-3</sup></td><td>0.05<br>3.04 &times; 10<sup>-3</sup></td><td>0.13<br>3.04 &times; 10<sup>-3</sup></td><td>0.07<br>3.04 &times; 10<sup>-3</sup></td></tr><tr><td>n</td><td>119</td><td>131</td><td>119</td><td>131</td></tr><tr><td>size</td><td>15 &times; 1, 1 &times; 15, 1 &times; 39</td><td>15 &times; 1, 11 &times; 4, 1 &times; 7, 1 &times; 15</td><td>15 &times; 1, 1 &times; 15, 1 &times; 39</td><td>15 &times; 1, 11 &times; 4, 1 &times; 7, 1 &times; 15</td></tr><tr><td rowspan="3">14</td><td>l.b.</td><td>0.14<br>2.82 &times; 10<sup>-3</sup></td><td>0.06<br>2.82 &times; 10<sup>-3</sup></td><td>0.13<br>2.82 &times; 10<sup>-3</sup></td><td>0.06<br>2.82 &times; 10<sup>-3</sup></td></tr><tr><td>n</td><td>135</td><td>148</td><td>135</td><td>148</td></tr><tr><td>size</td><td>16 &times; 1, 1 &times; 16, 1 &times; 42</td><td>16 &times; 1, 12 &times; 4, 1 &times; 7, 1 &times; 16</td><td>16 &times; 1, 1 &times; 16, 1 &times; 42</td><td>16 &times; 1, 12 &times; 4, 1 &times; 7, 1 &times; 16</td></tr><tr><td rowspan="3">15</td><td>l.b.</td><td>0.33<br>2.63 &times; 10<sup>-3</sup></td><td>0.07<br>2.63 &times; 10<sup>-3</sup></td><td>0.33<br>2.63 &times; 10<sup>-3</sup></td><td>0.07<br>2.63 &times; 10<sup>-3</sup></td></tr><tr><td>n</td><td>152</td><td>166</td><td>152</td><td>166</td></tr><tr><td>size</td><td>17 &times; 1, 1 &times; 17, 1 &times; 45</td><td>17 &times; 1, 13 &times; 4, 1 &times; 7, 1 &times; 17</td><td>17 &times; 1, 1 &times; 17, 1 &times; 45</td><td>17 &times; 1, 13 &times; 4, 1 &times; 7, 1 &times; 17</td></tr></tbody></table>
<table><caption>**Table 3:** Comparison of four moment-SOS hierarchies for the second-order relaxation of a double-hinged beam problem with varying number of elements ($n_e$). The hierarchies are: standard moment-SOS (mSOS), mSOS with arrow decomposition (mSOS+AD), mSOS using nonmixed-term basis (mSOS+NMT), and mSOS combining nonmixed-term basis with arrow decomposition (mSOS+NMT+AD). For each method and problem size, we report: solution time (t) in seconds, computed lower bound (l.b.), number of variables in the relaxation (n), and sizes of matrix constraints (where $a \times b$ indicates a matrix constraints of size $S^b$). The superscript * indicates solutions with verified global optimality through relative optimality gap, while + denotes numerical issues in the Mosek optimizer.</caption><thead><tr><th>n<sub>e</sub></th><th>mSOS</th><th>mSOS+AD</th><th>mSOS+NMT</th><th>mSOS+NMT+AD</th></tr></thead><tbody><tr><td>1</td><td>0.03<br>4.17 &times; 10<sup>-2</sup><br>14<br>3 &times; 3, 1 &times; 6, 1 &times; 9</td><td>0.02<br>4.17 &times; 10<sup>-2</sup><br>14<br>3 &times; 3, 1 &times; 6, 1 &times; 9</td><td>0.02<br>4.17 &times; 10<sup>-2</sup><br>14<br>3 &times; 3, 1 &times; 5, 1 &times; 9</td><td>0.02<br>4.17 &times; 10<sup>-2</sup><br>14<br>3 &times; 3, 1 &times; 5, 1 &times; 9</td></tr><tr><td>2</td><td>0.05<br>4.00 &times; 10<sup>-2</sup><br>34<br>4 &times; 4, 1 &times; 10, 1 &times; 24</td><td>0.06<br>4.00 &times; 10<sup>-2</sup><br>34<br>4 &times; 4, 1 &times; 10, 1 &times; 24</td><td>0.06<br>4.00 &times; 10<sup>-2</sup><br>34<br>4 &times; 4, 1 &times; 7, 1 &times; 24</td><td>0.07<br>4.00 &times; 10<sup>-2</sup><br>34<br>4 &times; 4, 1 &times; 7, 1 &times; 24</td></tr><tr><td>3</td><td>0.26<br>3.91 &times; 10<sup>-2</sup><br>69<br>5 &times; 5, 1 &times; 15, 1 &times; 45</td><td>0.14<br>3.91 &times; 10<sup>-2</sup><br>99<br>5 &times; 5, 1 &times; 15, 1 &times; 20, 1 &times; 35</td><td>0.44<br>3.91 &times; 10<sup>-2</sup><br>68<br>5 &times; 5, 1 &times; 9, 1 &times; 45</td><td>0.13<br>3.91 &times; 10<sup>-2</sup><br>98<br>5 &times; 5, 1 &times; 9, 1 &times; 20, 1 &times; 35</td></tr><tr><td>4</td><td>0.39<br>3.79 &times; 10<sup>-2</sup><br>125<br>6 &times; 6, 1 &times; 21, 1 &times; 72</td><td>0.29<br>3.79 &times; 10<sup>-2</sup><br>188<br>6 &times; 6, 1 &times; 21, 2 &times; 24, 1 &times; 42</td><td>1.53<br>3.78 &times; 10<sup>-2</sup><br>120<br>6 &times; 6, 1 &times; 11, 1 &times; 72</td><td>0.25<br>3.79 &times; 10<sup>-2</sup><br>183<br>6 &times; 6, 1 &times; 11, 2 &times; 24, 1 &times; 42</td></tr><tr><td>5</td><td>1.91<br>3.63 &times; 10<sup>-2</sup><br>209<br>7 &times; 7, 1 &times; 28, 1 &times; 105</td><td>0.49<br>3.63 &times; 10<sup>-2</sup><br>321<br>7 &times; 7, 4 &times; 28, 1 &times; 49</td><td>5.62<br>3.62 &times; 10<sup>-2</sup><br>194<br>7 &times; 7, 1 &times; 13, 1 &times; 105</td><td>0.41<br>3.62 &times; 10<sup>-2</sup><br>306<br>7 &times; 7, 1 &times; 13, 3 &times; 28, 1 &times; 49</td></tr><tr><td>6</td><td>20.62<br>3.43 &times; 10<sup>-2</sup><br>329<br>8 &times; 8, 1 &times; 36, 1 &times; 144</td><td>0.66<br>3.43 &times; 10<sup>-2</sup><br>509<br>8 &times; 8, 4 &times; 32, 1 &times; 36, 1 &times; 56</td><td>10.98<br>3.42 &times; 10<sup>-2</sup><br>294<br>8 &times; 8, 1 &times; 15, 1 &times; 144</td><td>0.56<br>3.42 &times; 10<sup>-2</sup><br>474<br>8 &times; 8, 1 &times; 15, 4 &times; 32, 1 &times; 56</td></tr><tr><td>7</td><td>13.10<br>3.22 &times; 10<sup>-2</sup><br>494<br>9 &times; 9, 1 &times; 45, 1 &times; 189</td><td>1.17<br>3.22 &times; 10<sup>-2</sup><br>764<br>9 &times; 9, 5 &times; 36, 1 &times; 45, 1 &times; 63</td><td>8.95<br>3.21 &times; 10<sup>-2</sup><br>424<br>9 &times; 9, 1 &times; 17, 1 &times; 189</td><td>0.82<br>3.21 &times; 10<sup>-2</sup><br>694<br>9 &times; 9, 1 &times; 17, 5 &times; 36, 1 &times; 63</td></tr><tr><td>8</td><td>27.34<br>3.01 &times; 10<sup>-2</sup><br>714<br>10 &times; 10, 1 &times; 55, 1 &times; 240</td><td>1.85<br>3.01 &times; 10<sup>-2</sup><br>1099<br>10 &times; 10, 6 &times; 40, 1 &times; 55, 1 &times; 70</td><td>17.50<br>+3.00 &times; 10<sup>-2</sup><br>588<br>10 &times; 10, 1 &times; 19, 1 &times; 240</td><td>1.49<br>3.01 &times; 10<sup>-2</sup><br>973<br>10 &times; 10, 1 &times; 19, 6 &times; 40, 1 &times; 70</td></tr><tr><td>9</td><td>18.27<br>2.81 &times; 10<sup>-2</sup><br>1000<br>11 &times; 11, 1 &times; 66, 1 &times; 297</td><td>5.30<br>2.81 &times; 10<sup>-2</sup><br>1528<br>11 &times; 11, 7 &times; 44, 1 &times; 66, 1 &times; 77</td><td>33.35<br>+2.80 &times; 10<sup>-2</sup><br>790<br>11 &times; 11, 1 &times; 21, 1 &times; 297</td><td>3.34<br>2.81 &times; 10<sup>-2</sup><br>1318<br>11 &times; 11, 1 &times; 21, 7 &times; 44, 1 &times; 77</td></tr><tr><td>10</td><td>127.15<br>2.63 &times; 10<sup>-2</sup><br>1364<br>12 &times; 12, 1 &times; 78, 1 &times; 360</td><td>11.49<br>2.63 &times; 10<sup>-2</sup><br>2066<br>12 &times; 12, 8 &times; 48, 1 &times; 78, 1 &times; 84</td><td>45.10<br>+2.62 &times; 10<sup>-2</sup><br>1034<br>12 &times; 12, 1 &times; 23, 1 &times; 360</td><td>4.86<br>2.63 &times; 10<sup>-2</sup><br>1736<br>12 &times; 12, 1 &times; 23, 8 &times; 48, 1 &times; 84</td></tr><tr><td>11</td><td>93.78<br>2.46 &times; 10<sup>-2</sup><br>1819<br>13 &times; 13, 1 &times; 91, 1 &times; 429</td><td>9.26<br>2.46 &times; 10<sup>-2</sup><br>2729<br>13 &times; 13, 9 &times; 52, 2 &times; 91</td><td>36.06<br>+2.44 &times; 10<sup>-2</sup><br>1324<br>13 &times; 13, 1 &times; 25, 1 &times; 429</td><td>6.19<br>2.46 &times; 10<sup>-2</sup><br>2234<br>13 &times; 13, 1 &times; 25, 9 &times; 52, 1 &times; 91</td></tr><tr><td>12</td><td>145.09<br>2.31 &times; 10<sup>-2</sup><br>2379<br>14 &times; 14, 1 &times; 105, 1 &times; 504</td><td>16.42<br>2.32 &times; 10<sup>-2</sup><br>3534<br>14 &times; 14, 10 &times; 56, 1 &times; 98, 1 &times; 105</td><td>90.36<br>+2.30 &times; 10<sup>-2</sup><br>1664<br>14 &times; 14, 1 &times; 27, 1 &times; 504</td><td>16.19<br>2.32 &times; 10<sup>-2</sup><br>2819<br>14 &times; 14, 1 &times; 27, 10 &times; 56, 1 &times; 98</td></tr><tr><td>13</td><td>161.39<br>+2.18 &times; 10<sup>-2</sup><br>3059<br>15 &times; 15, 1 &times; 120, 1 &times; 585</td><td>66.75<br>2.18 &times; 10<sup>-2</sup><br>4499<br>15 &times; 15, 11 &times; 60, 1 &times; 105, 1 &times; 120</td><td>125.50<br>+2.16 &times; 10<sup>-2</sup><br>2058<br>15 &times; 15, 1 &times; 29, 1 &times; 585</td><td>18.83<br>2.19 &times; 10<sup>-2</sup><br>3498<br>15 &times; 15, 1 &times; 29, 11 &times; 60, 1 &times; 105</td></tr><tr><td>14</td><td>373.55<br>+2.06 &times; 10<sup>-2</sup><br>3875<br>16 &times; 16, 1 &times; 136, 1 &times; 672</td><td>54.08<br>2.06 &times; 10<sup>-2</sup><br>5643<br>16 &times; 16, 12 &times; 64, 1 &times; 112, 1 &times; 136</td><td>140.63<br>+2.03 &times; 10<sup>-2</sup><br>2510<br>16 &times; 16, 1 &times; 31, 1 &times; 672</td><td>27.66<br>2.06 &times; 10<sup>-2</sup><br>4278<br>16 &times; 16, 1 &times; 31, 12 &times; 64, 1 &times; 112</td></tr><tr><td>15</td><td>396.57<br>+1.95 &times; 10<sup>-2</sup><br>4844<br>17 &times; 17, 1 &times; 153, 1 &times; 765</td><td>96.38<br>1.95 &times; 10<sup>-2</sup><br>6986<br>17 &times; 17, 13 &times; 68, 1 &times; 119, 1 &times; 153</td><td>159.30<br>+1.87 &times; 10<sup>-2</sup><br>3024<br>17 &times; 17, 1 &times; 33, 1 &times; 765</td><td>33.31<br>1.95 &times; 10<sup>-2</sup><br>5166<br>17 &times; 17, 1 &times; 33, 13 &times; 68, 1 &times; 119</td></tr></tbody></table>
<table><caption>**Table 4:** Comparison of four moment-SOS hierarchies for the third-order relaxation of a double-hinged beam problem with varying number of elements ($n_e$). The hierarchies are: standard moment-SOS (mSOS), mSOS with arrow decomposition (mSOS+AD), mSOS using nonmixed-term basis (mSOS+NMT), and mSOS combining nonmixed-term basis with arrow decomposition (mSOS+NMT+AD). For each method and problem size, we report: solution time ($t$) in seconds, computed lower bound (l.b.), number of variables in the relaxation ($n$), and sizes of matrix constraints (where $a \times b$ indicates a matrix constraints of size $S^b$). The superscript * indicates solutions with verified global optimality through relative optimality gap, while + denotes numerical issues in the Mosek optimizer, and – indicates solver failure due to time limitations.</caption><thead><tr><th>n<sub>e</sub></th><th>mSOS</th><th>mSOS+AD</th><th>mSOS+NMT</th><th>mSOS+NMT+AD</th></tr></thead><tbody><tr><td>4</td><td>45.76<br>l.b.<br>n<br>size</td><td>4.01<br>*3.86 × 10<sup>-2</sup><br>1154<br>6 × 21, 1 × 56, 1 × 252</td><td>1.58<br>*3.86 × 10<sup>-2</sup><br>240<br>6 × 11, 1 × 16, 1 × 132</td><td>0.41<br>*3.86 × 10<sup>-2</sup><br>438<br>6 × 11, 1 × 16, 2 × 44, 1 × 77</td></tr><tr><td>5</td><td>173.21<br>l.b.<br>n<br>size</td><td>7.85<br>*3.84 × 10<sup>-2</sup><br>2547<br>7 × 28, 1 × 84, 1 × 420</td><td>24.86<br>*3.84 × 10<sup>-2</sup><br>391<br>7 × 13, 1 × 19, 1 × 195</td><td>0.94<br>*3.84 × 10<sup>-2</sup><br>755<br>7 × 13, 1 × 19, 3 × 52, 1 × 91</td></tr><tr><td>6</td><td>237.84<br>l.b.<br>n<br>size</td><td>27.08<br>*3.82 × 10<sup>-2</sup><br>5045<br>8 × 36, 1 × 120, 1 × 648</td><td>49.18<br>*3.82 × 10<sup>-2</sup><br>595<br>8 × 15, 1 × 22, 1 × 270</td><td>1.73<br>*3.82 × 10<sup>-2</sup><br>1195<br>8 × 15, 1 × 22, 4 × 60, 1 × 105</td></tr><tr><td>7</td><td>456.53<br>l.b.<br>n<br>size</td><td>85.93<br>*3.81 × 10<sup>-2</sup><br>9212<br>9 × 45, 1 × 165, 1 × 945</td><td>129.79<br>*3.81 × 10<sup>-2</sup><br>860<br>9 × 17, 1 × 25, 1 × 357</td><td>4.67<br>*3.81 × 10<sup>-2</sup><br>1778<br>9 × 17, 1 × 25, 5 × 68, 1 × 119</td></tr><tr><td>8</td><td>2566.01<br>l.b.<br>n<br>size</td><td>350.88<br>*3.80 × 10<sup>-2</sup><br>15784<br>10 × 55, 7 × 220, 1 × 385</td><td>49.97<br>3.79 × 19<sup>-2</sup><br>1194<br>10 × 19, 1 × 28, 1 × 456</td><td>20.99<br>3.80 × 10<sup>-2</sup><br>2524<br>10 × 19, 1 × 28, 6 × 76, 1 × 133</td></tr><tr><td>9</td><td>3816.29<br>l.b.<br>n<br>size</td><td>9275.24<br>*3.79 × 10<sup>-2</sup><br>25695<br>11 × 66, 1 × 286, 1 × 1782</td><td>68.91<br>3.77 × 10<sup>-2</sup><br>1605<br>11 × 21, 1 × 31, 1 × 567</td><td>89.30<br>3.78 × 10<sup>-2</sup><br>3453<br>11 × 21, 1 × 31, 7 × 84, 1 × 147</td></tr><tr><td>10</td><td>9166.91<br>l.b.<br>n<br>size</td><td>—</td><td>109.95<br>3.74 × 10<sup>-2</sup><br>2101<br>12 × 23, 1 × 34, 1 × 690</td><td>164.84<br>3.76 × 10<sup>-2</sup><br>4585<br>12 × 23, 1 × 34, 8 × 92, 1 × 161</td></tr><tr><td>11</td><td>—</td><td>—</td><td>167.05<br>3.72 × 10<sup>-2</sup><br>2690<br>13 × 25, 1 × 37, 1 × 825</td><td>200.88<br>3.74 × 10<sup>-2</sup><br>5940<br>13 × 25, 1 × 37, 9 × 100, 1 × 175</td></tr><tr><td>12</td><td>—</td><td>—</td><td>402.48<br>+3.68 × 10<sup>-2</sup><br>3380<br>14 × 27, 1 × 40, 1 × 972</td><td>225.97<br>3.72 × 10<sup>-2</sup><br>7538<br>14 × 27, 1 × 40, 10 × 108, 1 × 189</td></tr><tr><td>13</td><td>—</td><td>—</td><td>303.97<br>+3.61 × 10<sup>-2</sup><br>4179<br>15 × 29, 1 × 43, 1 × 1131</td><td>251.30<br>3.69 × 10<sup>-2</sup><br>9399<br>15 × 29, 1 × 43, 11 × 116, 1 × 203</td></tr><tr><td>14</td><td>—</td><td>—</td><td>578.86<br>+3.56 × 10<sup>-2</sup><br>5095<br>16 × 31, 1 × 46, 1 × 1302</td><td>328.50<br>3.66 × 10<sup>-2</sup><br>11543<br>16 × 31, 1 × 46, 12 × 124, 1 × 217</td></tr><tr><td>15</td><td>—</td><td>—</td><td>719.89<br>+3.46 × 10<sup>-2</sup><br>6136<br>17 × 33, 1 × 49, 1 × 1485</td><td>532.08<br>3.61 × 10<sup>-2</sup><br>13990<br>17 × 33, 1 × 49, 13 × 132, 1 × 231</td></tr></tbody></table>
<table><caption>**Table 5:** Comparison of four moment-SOS hierarchies for the fourth-order relaxation of a double-hinged beam problem with varying number of elements ($n_e$).</caption><thead><tr><th>n<sub>e</sub></th><th>mSOS</th><th>mSOS+AD</th><th>mSOS+NMT</th><th>mSOS+NMT+AD</th></tr></thead><tbody><tr><td>8 t [s]</td><td>200931.39</td><td></td><td>88.55</td><td>36.43</td></tr><tr><td>l.b.</td><td>3.80 × 10<sup>-2</sup></td><td>—</td><td>+3.80 × 10<sup>-2</sup></td><td>*3.80 × 10<sup>-2</sup></td></tr><tr><td>n</td><td>24309</td><td></td><td>3192</td><td>6034</td></tr><tr><td>size</td><td>10 × 220, 1 × 715, 1 × 5280</td><td></td><td>10 × 28, 1 × 37, 1 × 672</td><td>10 × 28, 1 × 37, 6 × 112, 1 × 196</td></tr><tr><td>9 t [s]</td><td></td><td></td><td>142.16</td><td>901.23</td></tr><tr><td>l.b.</td><td>—</td><td>—</td><td>+3.79 × 10<sup>-2</sup></td><td>*3.79 × 10<sup>-2</sup></td></tr><tr><td>n</td><td></td><td></td><td>4370</td><td>8338</td></tr><tr><td>size</td><td></td><td></td><td>11 × 31, 1 × 41, 1 × 837</td><td>11 × 31, 1 × 41, 7 × 124, 1 × 217</td></tr><tr><td>10 t [s]</td><td></td><td></td><td>685.56</td><td>574.21</td></tr><tr><td>l.b.</td><td>—</td><td>—</td><td>3.79 × 10<sup>-2</sup></td><td>*3.79 × 10<sup>-2</sup></td></tr><tr><td>n</td><td></td><td></td><td>5808</td><td>11163</td></tr><tr><td>size</td><td></td><td></td><td>12 × 34, 1 × 45, 1 × 1020</td><td>12 × 34, 1 × 45, 8 × 136, 1 × 238</td></tr><tr><td>11 t [s]</td><td></td><td></td><td>936.62</td><td>493.89</td></tr><tr><td>l.b.</td><td>—</td><td>—</td><td>3.78 × 10<sup>-2</sup></td><td>3.79 × 10<sup>-2</sup></td></tr><tr><td>n</td><td></td><td></td><td>7532</td><td>14562</td></tr><tr><td>size</td><td></td><td></td><td>13 × 37, 1 × 49, 1 × 1221</td><td>13 × 37, 1 × 49, 9 × 148, 1 × 259</td></tr><tr><td>12 t [s]</td><td></td><td></td><td>1897.92</td><td>1004.73</td></tr><tr><td>l.b.</td><td>—</td><td>—</td><td>3.77 × 10<sup>-2</sup></td><td>3.78 × 10<sup>-2</sup></td></tr><tr><td>n</td><td></td><td></td><td>9568</td><td>18588</td></tr><tr><td>size</td><td></td><td></td><td>14 × 40, 1 × 53, 1 × 1440</td><td>14 × 40, 1 × 53, 10 × 160, 1 × 280</td></tr><tr><td>13 t [s]</td><td></td><td></td><td>1377.81</td><td>1869.33</td></tr><tr><td>l.b.</td><td>—</td><td>—</td><td>3.76 × 10<sup>-2</sup></td><td>3.78 × 10<sup>-2</sup></td></tr><tr><td>n</td><td></td><td></td><td>11942</td><td>23294</td></tr><tr><td>size</td><td></td><td></td><td>15 × 43, 1 × 57, 1 × 1677</td><td>15 × 43, 1 × 57, 11 × 172, 1 × 301</td></tr><tr><td>14 t [s]</td><td></td><td></td><td>2785.38</td><td>4305.19</td></tr><tr><td>l.b.</td><td>—</td><td>—</td><td>3.76 × 10<sup>-2</sup></td><td>3.77 × 10<sup>-2</sup></td></tr><tr><td>n</td><td></td><td></td><td>14680</td><td>28733</td></tr><tr><td>size</td><td></td><td></td><td>16 × 46, 1 × 61, 1 × 1932</td><td>16 × 46, 1 × 61, 12 × 184, 1 × 322</td></tr><tr><td>15 t [s]</td><td></td><td></td><td>6667.30</td><td>6879.09</td></tr><tr><td>l.b.</td><td>—</td><td>—</td><td>3.74 × 10<sup>-2</sup></td><td>3.76 × 10<sup>-2</sup></td></tr><tr><td>n</td><td></td><td></td><td>17808</td><td>34958</td></tr><tr><td>size</td><td></td><td></td><td>17 × 49, 1 × 65, 1 × 2205</td><td>17 × 49, 1 × 65, 13 × 196, 1 × 343</td></tr></tbody></table>

The hierarchies are: standard moment-SOS (mSOS), mSOS with arrow decomposition (mSOS+AD), mSOS using nonmixed-term basis (mSOS+NMT), and mSOS combining nonmixed-term basis with arrow decomposition (mSOS+NMT+AD). For each method and problem size, we report: solution time (t) in seconds, computed lower bound (l.b.), number of variables in the relaxation (n), and sizes of matrix constraints (where $a \times b$ indicates a matrix constraints of size $S^b$). The superscript * indicates solutions with verified global optimality through relative optimality gap, while + denotes numerical issues in the Mosek optimizer, and — indicates solver failure due to time limitations.

## Acknowledgements

Marouan Handa, Marek Tyburec and Michal Kočvara acknowledge the financial support of the Czech Science Foundation project GA22-15524S, and Marek Tyburec and Michal Kočvara also benefited from the support of the project ROBOPROX (reg. no. CZ.02.01.01/00/22.008/0004590) that was co-funded by the European Union. In addition, Marek Tyburec and Giovanni Fantuzzi acknowledge the support of the mobility project 8J24DE005 awarded jointly by Ministry of Education,
Youth and Sport of the Czech Republic and German Academic Exchange Service. Victor Magron benefited from the HORIZON-MSCA-2023-DN-JD of the European Commission under the Grant Agreement No 101120296 (TENORS), the ANITI AI Cluster program under the Grant agreement n° ANR-23-IACL-0002, as well as the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme.

**Availability of data and materials** Source codes and input files to reproduce the computations are available at https://gitlab.com/tyburec/pof-dyna.

## Declarations

**Ethics approval and consent to participate** This work does not contain any studies with human participants or animals performed by any of the authors.

**Consent for publication** Not applicable.

**Competing interests** The authors declare that they have no competing interests.

## References

[1] Kočvara, M.: Decomposition of arrow type positive semidefinite matrices with application to topology optimization. Mathematical Programming **190**(1-2), 105-134 (2020) https://doi.org/10.1007/s10107-020-01526-w

[2] Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana University Mathematics Journal **42**(3), 969-984 (1993) https://doi.org/10.1512/iumj.1993.42.42045

[3] Lasserre, J.-B.: Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization **11**(3), 796-817 (2001) https://doi.org/10.1137/S1052623400366802

[4] Nie, J.: Optimality conditions and finite convergence of lasserre's hierarchy. Mathematical programming **146**, 97-121 (2014)

[5] Lasserre, J.-B.: Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM Journal on Optimization **17**(3), 822-843 (2006) https://doi.org/10.1137/05064504X

[6] Wang, J., Magron, V., Lasserre, J.-B.: TSSOS: A moment-SOS hierarchy that exploits term sparsity. SIAM Journal on Optimization **31**(1), 30-58 (2021) https://doi.org/10.1137/19m1307871

[7] Wang, J., Magron, V., Lasserre, J.-B.: Chordal-tssos: A moment-sos hierarchy that exploits term sparsity with chordal extension. SIAM Journal on Optimization
31(1), 114–141 (2021) https://doi.org/10.1137/20M1323564

[8] Wang, J., Magron, V., Lasserre, J.B., Mai, N.H.A.: CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization. ACM Transactions on Mathematical Software **48**(4), 1–26 (2022) https://doi.org/10.1145/3569709

[9] Korda, M., Laurent, M., Magron, V., Steenkamp, A.: Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks. Mathematical Programming **205**(1–2), 703–744 (2023) https://doi.org/10.1007/s10107-023-01993-x

[10] Riener, C., Theobald, T., Andrén, L.J., Lasserre, J.-B.: Exploiting symmetries in SDP-relaxations for polynomial optimization. Mathematics of Operations Research **38**(1), 122–141 (2013) https://doi.org/10.1287/moor.1120.0558

[11] Magron, V., Wang, J.: Sparse Polynomial Optimization: Theory and Practice. Series on Optimization and Its Applications, vol. 5. World Scientific (Europe), London (2023). https://doi.org/10.1142/q0382

[12] Korda, M., Magron, V., Ríos-Zertuche, R.: Convergence rates for sums-of-squares hierarchies with correlative sparsity. Mathematical Programming **209**(1–2), 435–473 (2024) https://doi.org/10.1007/s10107-024-02071-6

[13] Henrion, D., Lofberg, J., Kocvara, M., Stingl, M.: Solving polynomial static output feedback problems with penbmi. In: Proceedings of the 44th IEEE Conference on Decision and Control, pp. 7581–7586 (2005). https://doi.org/10.1109/cdc.2005.1583385. IEEE

[14] Tyburec, M., Zeman, J., Kružík, M., Henrion, D.: Global optimality in minimum compliance topology optimization of frames and shells by moment-sum-of-squares hierarchy. Structural and Multidisciplinary Optimization **64**(4), 1963–1981 (2021) https://doi.org/10.1007/s00158-021-02957-5

[15] Popovych, Z., Jacobs, K., Korpas, G., Marecek, J., Bondar, D.I.: Quantum open system identification via global optimization: Optimally accurate Markovian models of open systems from time-series data (2024). https://doi.org/10.48550/arXiv.2203.17164

[16] Henrion, D., Lasserre, J.-B.: Convergent relaxations of polynomial matrix inequalities and static output feedback. IEEE Transactions on Automatic Control **51**(2), 192–202 (2006) https://doi.org/10.1109/TAC.2005.863494

[17] Scherer, C.W., Hol, C.W.J.: Matrix sum-of-squares relaxations for robust semi-definite programs. Mathematical Programming **107**(1–2), 189–211 (2005) https://doi.org/10.1007/s10107-005-0684-2

[18] Miller, J., Wang, J., Guo, F.: Sparse polynomial matrix optimization. arXiv
preprint arXiv:2411.15479 (2024)

[19] Handa, M., Tyburec, M., Kočvara, M.: Term-sparse polynomial optimization for the design of frame structures. Optimization and Engineering, 1–44 (2025) https://doi.org/10.1007/s11081-025-10000-5

[20] Zheng, Y., Fantuzzi, G.: Sum-of-squares chordal decomposition of polynomial matrix inequalities. Mathematical Programming **197**(1), 71–108 (2021) https://doi.org/10.1007/s10107-021-01728-w

[21] Zheng, Y., Fantuzzi, G., Papachristodoulou, A.: Decomposition and completion of sum-of-squares matrices. In: 2018 IEEE Conference on Decision and Control (CDC), pp. 4026–4031. IEEE, USA (2018). https://doi.org/10.1109/CDC.2018.8619144

[22] Gallier, J.: Geometric Methods and Applications: For Computer Science and Engineering. Texts in Applied Mathematics. Springer, USA (2011). https://doi.org/10.1007/978-1-4419-9961-0

[23] Lasserre, J.-B.: An Introduction to Polynomial and Semi-Algebraic Optimization. Cambridge University Press, Cambridge, UK (2015). https://doi.org/10.1017/cbo9781107447226

[24] Curto, R.E., Fialkow, L.A.: Solution of the truncated complex moment problem for flat data. Memoirs of the American Mathematical Society **119**(568), 1–52 (1996) https://doi.org/10.1090/memo/0568

[25] Henrion, D., Lasserre, J.-B.: Detecting global optimality and extracting solutions in GloptiPoly, pp. 293–310. Springer, Berlin, Germany (2005). https://doi.org/10.1007/10997703_15

[26] Henrion, D., Korda, M., Kružík, M., Rios-Zertuche, R.: Occupation measure relaxations in variational problems: the role of convexity (2023). https://doi.org/10.1137/23M1557088

[27] Tyburec, M., Kočvara, M., Kružík, M.: Global weight optimization of frame structures with polynomial programming. Structural and Multidisciplinary Optimization **66**(12), 257 (2023) https://doi.org/10.1007/s00158-023-03715-5

[28] Tyburec, M., Kočvara, M., Handa, M., Zeman, J.: Global weight optimization of frame structures under free-vibration eigenvalue constraints (2024)

[29] Agler, J., Helton, W., McCullough, S., Rodman, L.: Positive semidefinite matrices with a given sparsity pattern. Linear algebra and its applications **107**, 101–149 (1988) https://doi.org/10.1016/0024-3795(88)90240-6

[30] Vandenberghe, L., Andersen, M.S.: Chordal graphs and semidefinite optimization.
Foundations and Trends in Optimization 1(4), 241-433 (2015) https://doi.org/10.1561/2400000006

[31] Fukuda, M., Kojima, M., Murota, K., Nakata, K.: Exploiting sparsity in semidefinite programming via matrix completion: General framework. SIAM Journal on Optimization 11(3), 647-674 (2001) https://doi.org/10.1137/S1052623400366218

[32] De Klerk, E.: Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Applied Optimization, vol. 65. Kluwer Academic Publishers, Dordrecht, The Netherlands (2006). https://doi.org/10.1007/B105286

[33] Murota, K., Kanno, Y., Kojima, M., Kojima, S.: A numerical algorithm for block-diagonal decomposition of matrix * -algebras with application to semidefinite programming. Japan Journal of Industrial and Applied Mathematics 27(1), 125-160 (2010) https://doi.org/10.1007/s13160-010-0006-9

[34] Xue, L., Jiao, D.: Method for analytically finding the nullspace of stiffness matrix for both zeroth-order and higher order curl-conforming vector bases in unstructured meshes. IEEE Transactions on Microwave Theory and Techniques 68(2), 456-468 (2020) https://doi.org/10.1109/tmtt.2019.2955082

[35] Shklarski, G., Toledo, S.: Computing the null space of finite element problems. Computer Methods in Applied Mechanics and Engineering 198(37-40), 3084-3095 (2009) https://doi.org/10.1016/j.cma.2009.05.012