11institutetext: Department of Mathematics, University of Padova, Padova,
Italy 22institutetext: Department of General Psychology, University of Padova,
Padova, Italy

# Assessing the Emergent Symbolic Reasoning Abilities of Llama Large Language
Models

Flavio Petruzzellis 11 Alberto Testolin 1122 Alessandro Sperduti 11

###### Abstract

Large Language Models (LLMs) achieve impressive performance in a wide range of
tasks, even if they are often trained with the only objective of chatting
fluently with users. Among other skills, LLMs show emergent abilities in
mathematical reasoning benchmarks, which can be elicited with appropriate
prompting methods. In this work, we systematically investigate the
capabilities and limitations of popular open-source LLMs on different symbolic
reasoning tasks. We evaluate three models of the Llama 2 family on two
datasets that require solving mathematical formulas of varying degrees of
difficulty. We test a generalist LLM (Llama 2 Chat) as well as two fine-tuned
versions of Llama 2 (MAmmoTH and MetaMath) specifically designed to tackle
mathematical problems. We observe that both increasing the scale of the model
and fine-tuning it on relevant tasks lead to significant performance gains.
Furthermore, using fine-grained evaluation measures, we find that such
performance gains are mostly observed with mathematical formulas of low
complexity, which nevertheless often remain challenging even for the largest
fine-tuned models.

###### Keywords:

LLMs open source mathematical reasoning formulas ListOps arithmetic

##  1 Introduction

Large language models (LLMs) featuring billions of parameters can exhibit
sophisticated cognitive skills as a by-product of their design and training
process rather than being explicitly trained to learn such skills. For
example, after being trained on large unlabeled corpora of text with the
objective of predicting the next word in a sentence, without additional fine-
tuning, LLMs can be “prompted” to perform a remarkable variety of tasks,
including two-digit arithmetic, question answering, text summarization, and
language translation [2]. Mathematical reasoning is still considered a
challenge for most LLMs [16], but it can be partially elicited in large models
using prompting techniques such as chain-of-thought prompting [21]. However,
whether symbolic reasoning can be considered an emerging ability is still a
matter of intense debate [15, 20].

In this work, we study the symbolic reasoning abilities of various large
language models, focusing on open-source models from the Llama 2 family [17].
We adopt a symbolic reasoning benchmark consisting of synthetic datasets of
mathematical formulas characterized by the possibility of manipulating problem
difficulty at a fine-grained level. Although such problems may appear, and
indeed are, distant from typical applications of LLMs, they can be effectively
used to systematically study the reasoning skills and the limitations of these
models.

We tested Llama 2 models of different sizes, as well as MetaMath [22] and
MAmmoTH [23], two versions of the base Llama 2 model fine-tuned to solve
mathematical problems. In our experiments, we observe that Llama 2 models
become more capable of solving symbolic reasoning problems as their size grows
and that fine-tuning on domain-specific problems can further improve their
performance. At the same time, by carefully analyzing how performance
improvements are related to problem difficulty, we find that the emergence of
symbolic reasoning is mainly observed when models (especially fine-tuned ones)
are probed with relatively simple formulas.

##  2 Related works

The concept of emergence [1] has been successfully used to characterize the
dynamics of neural networks [5] and describe cognitive phenomena in terms of
self-organizing principles [8, 24]. In recent years, it has attracted the
interest of the AI community following the observation that unexpected
cognitive abilities could emerge by simply increasing the size of deep
learning models [20].

Indeed, transformer-based models from the GPT family were first shown to
exhibit remarkable abilities to perform new tasks from textual instructions or
from a few examples, while only being trained to autoregressively predict the
next word in a sentence [2]. Since then, several works have shown that LLMs
can carry out many new tasks that were not explicitly included in their
training data, including solving arithmetic operations [2] and performing
commonsense reasoning [20]. The ability of these models to reason about novel
problems “zero-shot”, that is, without any direct training, has been directly
compared to the human ability to reason by analogy [19].

Reasoning abilities are generally tested in LLMs using commonsense reasoning
tasks, math word problems and symbolic reasoning benchmarks [7, 18, 21]. The
latter is a class of synthetically generated problems whose difficulty can be
systematically manipulated by deriving complex problems from the composition
of simple ones. One example is the “last letter concatenation” task [21], in
which the model is asked to output the string of characters obtained by
concatenating the last character of the words in a list (which can be
arbitrarily long). Another one is the “coin flip” problem [21], a version of
the parity problem in which the model should track the state of a coin after a
variable number of flips.

A significant boost in performance on these benchmarks has been obtained using
chain-of-thought prompting [21] and its variants [7, 18]. These prompting
methods let the model produce a sequence of reasoning steps through which it
can exploit the knowledge contained in the prompt to gradually derive the
final answer.

##  3 Methodology

In this work, we focused on a class of challenging reasoning problems in which
the model is tasked to solve symbolic mathematical formulas. As in other
symbolic reasoning benchmarks used to test Large Language Models, the problems
we examined do not require verbal reasoning to be solved. Instead, they
require the ability to discover and systematically apply an algorithmic
reasoning procedure that should enable generalization to problems of any level
of difficulty.

We considered symbolic formulas that can be nested, which means that each
operand in a formula can in turn be another formula. This implies that, in
general, several reasoning steps might be required to solve a given formula.
Indeed, similarly to other symbolic reasoning tasks, any formula can be solved
by the iterative application of a simple rewriting rule. For example, the
arithmetic expression (12+(3-(4+5))) can be solved by first identifying a
solvable sub-expression, i.e. (4+5), and then substituting the result obtained
by solving that sub-expression, namely 9, into the original expression,
obtaining a simpler expression, i.e. (12+(3-9)), which can be further
simplified by iteratively applying the same procedure. We note that, given
this problem structure, chain-of-thought prompting could in principle allow
LLMs to solve these tasks by decomposing each formula and iteratively solving
its simplest components.

Since the complexity of formulas can be characterized in terms of two
parameters, that is, the nesting level and the number of operands involved,
the reasoning abilities of LLMs can be analyzed in a finer-grained way
compared to other reasoning benchmarks. This allowed us to compare the
performance of models of different sizes on problems of varying levels of
difficulty and thus investigate the dynamics of emergence of symbolic
reasoning abilities.

###  3.1 Symbolic formulas

We considered two types of formulas: operations on lists of single-digit
integers derived from the ListOps dataset [10] and arithmetic expressions
[13].

The ListOps dataset was introduced to evaluate the capacity of neural networks
to build parse trees of nested formulas. The original dataset included
formulas composed of operations on lists of integers, including minimum,
maximum, median, and sum modulo $10$ of a list of integers. To reduce the
complexity of the problem, we only used minimum, maximum, and sum modulo $10$.
We also built data splits of ListOps formulas whose level of difficulty could
be precisely characterized. In particular, we made it possible to specify the
number of arguments that appear in formulas at any level, and we fixed the
number of nesting points at each level of a formula to two, as in the case of
arithmetic formulas (see below). We evaluated models on ListOps formulas that
had two to four operands and one to four nesting levels. Furthermore, we
slightly modified the original format of the ListOps formulas by using a more
explicit functional notation since it has been observed that the notation used
to represent symbolic formulas can strongly influence the performance of
transformers on arithmetic tasks [11]. For example, the formula [MAX 3 9 1]
was rewritten in the new format as MAX(3, 9, 1), since this notation is more
likely to be observed in other mathematical datasets used for training and
fine-tuning of the LLMs considered here.

For the arithmetic task, we generated arithmetic expressions with sum,
subtraction, and multiplication operations between two integers sampled in the
interval $[-99,99]$. We considered formulas with one to four nesting levels.
For each nesting level, a formula was nested in two points: that is, exactly
two operands on that level could be other formulas. In this work, we were more
interested in testing the capacity of Large Language Models to systematically
execute a sequence of operations, rather than their mathematical competence in
arithmetic with multi-digit numbers [3]. Therefore, when computing the final
values of formulas we used the modulo $100$ of the intermediate results, as
done in previous work on systematic generalization in transformers [4].

###  3.2 Models

We evaluated the symbolic reasoning abilities of three models: Llama 2 Chat
[17], and two fine-tuned versions, MAmmoTH [23] and MetaMath [22]. For all of
them, we considered three model sizes with 7B, 13B, and 70B parameters.

The Llama 2 Chat model is a large language model optimized for dialogue use
cases, trained on a mix of publicly available data. It generally performs
better than existing open-source models, approaching some of the most powerful
closed-source models on a series of safety benchmarks, and it achieves high
performance on a variety of tasks ranging from common sense reasoning to world
knowledge, reading comprehension, and mathematical problem solving [17].

We also chose to test two recently proposed fine-tuned versions of Llama 2,
MetaMath and MAmmoTH, that were designed to improve the mathematical reasoning
abilities of the base model using different fine-tuning strategies. MetaMath
has been fine-tuned on MetaMathQA, a companion dataset created by
bootstrapping samples in the GSM8K and MATH datasets by rephrasing both
questions and answers with the aim of increasing variety in the training
samples [22]. MAmmoTH was created with the aim of generalizing to many
different mathematical and reasoning domains, hence it has been fine-tuned on
eight different popular benchmarks and evaluated on both in-domain and out-of-
domain problems from different datasets [23].

###  3.3 Prompting Strategies

In order to elicit the emergence of reasoning abilities in Llama 2 Chat, we
have initially tested zero-shot chain-of-thought prompting, a recently
proposed prompting method that was shown to achieve similar performance as
chain-of-thought prompting without the need to craft exemplars [7, 14].
However, we observed that Llama 2 Chat already produced reasoning steps in the
output using zero-shot prompting, presumably as the result of fine-tuning with
reinforcement learning through human feedback [12], and that zero-shot chain-
of-thought prompting did not further improve the model’s performance.
Therefore, we opted for a simpler zero-shot prompting strategy, in which we
briefly describe the task and then directly ask the model to solve it. In the
case of the ListOps dataset, we also briefly describe the semantics of the
operators that appear in the expression. For example, a Llama 2 prompt to
solve a ListOps formula could be the following: MIN, MAX and SM are operators
on lists of single-digit integers which have the semantics of minimum, maximum
and sum modulo 10, respectively. Solve the following expression involving
these operators: MAX(3, 9, 1). Give the final answer stating ‘The final answer
is: <NUMBER>’.

In the case of MAmmoTH and MetaMath, we instead used the official prompting
strategy used by the authors of the model during fine-tuning. The prompt
formats for the two models are similar: they both include an initial sentence
introducing a generic task to the model followed by task-dependent
instructions and a request to produce a response. In our case, we used the
Llama 2 zero-shot prompt as a description of the task to be solved and we
inserted it in the official prompt format. The MetaMath prompt contained an
explicit request to solve the problem step-by-step, while this was not
required with MAmmoTH models since they have been fine-tuned with reasoning
problems solved via chain-of-thought prompting, and thus produce a sequence of
reasoning steps by default. For example, a MetaMath prompt to solve an
arithmetic formula could be the following: Below is an instruction that
describes a task. Write a response that appropriately completes the request.
Instruction: Solve the following arithmetic expression: ((86+51)+(-74-35)).
Take the modulo 100 of intermediate values, i.e. keep the last two digits of
the number with the sign. Give the final answer stating ‘The final answer is:
<NUMBER>’. Response: Let’s think step by step.

To extract the final answer from the model response we used regular
expressions to match integers and take the last one appearing in the text. We
measured the performance of all models using sequence accuracy, which means
that an output was considered correct only if it exactly matched the target.

##  4 Experiments and results

In this section, we present the results of our evaluations of the three
models. We first focused on the impact of model size on the performance, and
then study how performance is modulated by different levels of problem
difficulty. Finally, we take a closer look at the errors committed by the
models on the simplest examples, to better characterize their capacities and
limitations.

###  4.1 Model size improves global accuracy

Fig. 1 shows the performance of the three models considered on ListOps and
Arithmetic formulas, averaged across formulas of any nesting level and with
any number of operands. From this coarse-grained analysis, we can already
observe that accuracy always increases with model size. In particular, models
with 13B parameters seem to develop significantly better symbolic reasoning
abilities than their smaller 7B versions, and accuracy improves further in the
largest models.

Figure 1: Average accuracy on the ListOps and Arithmetic tasks obtained by
Llama 2, MAmmoTH, and MetaMath models of increasing size. Larger models
(especially if fine-tuned on math tasks) achieve better performance than
smaller ones.

From the aggregate performance metrics, it is also clear that solving ListOps
formulas is much easier than solving arithmetic ones, even for models that
have been specifically tuned on mathematical reasoning datasets (note the
different scale of the $y$-axes). This phenomenon could be due to the fact
that arithmetic formulas involve complex operations like multiplication
between two-digit integers, and calculation of the modulo 100 of intermediate
results.

It is also evident that fine-tuning Llama2 on mathematical problems improves
its capacity to solve the kind of math-based symbolic reasoning problems used
in our experiments. MetaMath models (especially the medium and large versions)
outperform MAmmoTH models on both tasks, probably because they have been fine-
tuned only on mathematical problems that are more similar to the ones we
consider here. Furthermore, in the case of ListOps, we find that fine-tuning
is especially effective in boosting the performance of 70B models, leading to
gains of 9% (MAmmoTH) and 17% (MetaMath) compared to the 70B Llama 2 model.
This could indicate that in the case of tasks consisting of a composition of
relatively simple elementary operations, greater performance improvements can
be achieved by fine-tuning large models.

Figure 2: Accuracy of Llama 2, MAmmoTH and MetaMath models on ListOps (top)
and arithmetic (bottom) formulas of varying levels of difficulty as a function
of model size. N$k$ indicates formulas with nesting level $k$.

###  4.2 Accuracy improves more on simple formulas

We now aim to better understand where the performance gain obtained by larger
models is concentrated. In Fig. 2, we report a fine-grained measure of the
accuracy of the three models on groups of ListOps and arithmetic formulas of
increasing nesting levels. As expected, all models are generally more accurate
when solving formulas in the easiest splits of both tasks (i.e., formulas with
only one or two nested expressions). This indicates that increasing the
nesting level of a formula indeed makes the problem more difficult for all the
models.

We further notice that as model size grows, accuracy generally increases more
on formulas with nesting levels 1 and 2, both for Arithmetic and ListOps. For
ListOps we observe a slight improvement in accuracy with model size also for
the most complicated formulas, while for the most challenging arithmetic
problems the improvement is almost null. It is also interesting to notice that
the largest version of MetaMath (70B) is slightly less accurate than the
intermediate version (13B) in arithmetic problems with a single nesting,
suggesting that scaling-up model size might be detrimental in some cases [9].

These results suggest that the emergent symbolic reasoning abilities observed
in the largest models do not yet allow for compositional generalization [6],
being mostly effective on relatively simple formulas. This holds even for
fine-tuned models, since their accuracy on the most challenging problems (four
nested formulas) is comparable to that achieved by the base Llama 2 models.

Figure 3: Type of errors made by the models on ListOps formulas with a single
nesting level. Absolute number of errors is on the $y$-axes and operator used
in the formula is on the $x$-axis.

Figure 4: Type of errors made by the models on arithmetic formulas with
nesting level 1, grouped by operator (+,-,$\ast$) and sign of the result (y).
Incidence of errors is measured by group.

###  4.3 Analysis of errors on simple formulas

In order to solve the symbolic reasoning problems considered in our
experiments, the models should be able to solve both atomic operations, such
as summing two numbers or finding the maximum in a list, and apply the correct
sequence of solution steps in nested formulas. Since we generally observed
that performance mostly improved on simpler problems, in the following
analysis we focus on studying the capacity of the models to solve the simplest
arithmetic and ListOps formulas. To this aim, we isolated and analyzed the
errors on data splits with a single nesting level.

In Fig. 4, we show the number of errors committed by the models on ListOps
formulas with a single nesting. We observe that for Llama 2, the scale of the
model allows to significantly improve its ability to solve min and max
operations (almost to perfection), while the sum modulo 10 becomes the most
difficult operation in the largest model, with a surprising deterioration in
performance compared to smaller-scale models. The trend is different for fine-
tuned models, which have presumably observed the sum modulo 10 operation more
frequently during training and can thus solve it better than the base model,
with the largest model versions reaching almost perfect accuracy on all atomic
operations.

In Fig. 4, we show the mistakes made by the models on arithmetic formulas with
a single nesting level. We group input samples based on the type of operation
appearing in the formulas and on the sign of the result, as we hypothesize
that operations involving negative operands could be more difficult than those
on positive ones. We then measure the incidence of errors in each group, i.e.
the fraction of formulas in each group that the model does not solve
correctly. We observe that both fine-tuning and reasoning abilities emerging
with scale mainly improve the models’ accuracy on formulas that have a
positive result. By looking at the reasoning steps produced by the models, we
noticed that the vast majority of these errors are due to an incorrect
calculation of the modulo operation, which indeed proves to be more difficult
for all models when it involves negative operands.

##  5 Conclusions

Despite the widespread deployment of foundation models, we currently lack a
clear understanding of how they work, when they fail, and what are the
capabilities and limitations of their seemingly emergent cognitive skills
[15].

In this work, we studied the emergent symbolic reasoning abilities of open-
source LLMs of the Llama family on mathematical formulas whose level of
difficulty can be precisely manipulated. We considered Llama 2 Chat and two
variants of the model fine-tuned for mathematical reasoning, comparing the
performance of small, medium, and large versions of each model.

We found that larger models are generally more capable of solving mathematical
formulas compared to smaller ones, suggesting the emergence of symbolic
reasoning abilities. However, a finer-grained analysis revealed that accuracy
mostly increased on formulas of low complexity, involving only a few nesting
levels. Furthermore, by analyzing the models’ failures on such simple
formulas, we found that common expressions like the modulo operation can still
represent a challenge even for the largest and fine-tuned language models.

Overall, our results suggest that large language models still struggle in
tasks requiring symbolic reasoning, and further research is needed to design
neural architectures better suited for this type of tasks. While our findings
are limited to models in the Llama family, we believe that the proposed
evaluation approach, based on symbolic reasoning benchmarks in which the
difficulty of samples can be precisely characterized, can help to build a more
sound understanding of the potential and limitations of this technology.

## References

  * [1] Anderson, P.W.: More is different: Broken symmetry and the nature of the hierarchical structure of science. Science 177(4047), 393–396 (1972)
  * [2] Brown, T., et al.: Language models are few-shot learners. Advances in neural information processing systems 33, 1877–1901 (2020)
  * [3] Cognolato, S., Testolin, A.: Transformers discover an elementary calculation system exploiting local attention and grid-like problem representation. In: 2022 International Joint Conference on Neural Networks (IJCNN). pp. 1–8. IEEE (2022)
  * [4] Csordás, R., Irie, K., Schmidhuber, J.: The neural data router: Adaptive control flow in transformers improves systematic generalization. In: The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net (2022), https://openreview.net/forum?id=KBQP4A_J1K
  * [5] Hopfield, J.J.: Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences 79(8), 2554–2558 (1982)
  * [6] Hupkes, D., Dankers, V., Mul, M., Bruni, E.: Compositionality decomposed: How do neural networks generalise? J. Artif. Intell. Res. 67, 757–795 (2020). https://doi.org/10.1613/JAIR.1.11674, https://doi.org/10.1613/jair.1.11674
  * [7] Kojima, T., Gu, S.S., Reid, M., Matsuo, Y., Iwasawa, Y.: Large language models are zero-shot reasoners. In: Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., Oh, A. (eds.) Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022 (2022), http://papers.nips.cc/paper_files/paper/2022/hash/8bb0d291acd4acf06ef112099c16f326-Abstract-Conference.html
  * [8] McClelland, J.L.: Emergence in cognitive science. Topics in cognitive science 2(4), 751–770 (2010)
  * [9] McKenzie, I.R., et al.: Inverse scaling: When bigger isn’t better. CoRR abs/2306.09479 (2023). https://doi.org/10.48550/ARXIV.2306.09479, https://doi.org/10.48550/arXiv.2306.09479
  * [10] Nangia, N., Bowman, S.R.: Listops: A diagnostic dataset for latent tree learning. In: Cordeiro, S.R., Oraby, S., Pavalanathan, U., Rim, K. (eds.) Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics, NAACL-HLT 2018, New Orleans, Louisiana, USA, June 2-4, 2018, Student Research Workshop. pp. 92–99. Association for Computational Linguistics (2018). https://doi.org/10.18653/V1/N18-4013, https://doi.org/10.18653/v1/n18-4013
  * [11] Nogueira, R.F., Jiang, Z., Lin, J.: Investigating the limitations of the transformers with simple arithmetic tasks. CoRR abs/2102.13019 (2021), https://arxiv.org/abs/2102.13019
  * [12] Ouyang, L., et al.: Training language models to follow instructions with human feedback. In: Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., Oh, A. (eds.) Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022 (2022), https://papers.nips.cc/paper_files/paper/2022/hash/b1efde53be364a73914
f58805a001731-Abstract-Conference.html

  * [13] Petruzzellis, F., Testolin, A., Sperduti, A.: A hybrid system for systematic generalization in simple arithmetic problems. In: Proceedings of the 17th International Workshop on Neural-Symbolic Learning and Reasoning (2023)
  * [14] Petruzzellis, F., Testolin, A., Sperduti, A.: Benchmarking GPT-4 on algorithmic problems: A systematic evaluation of prompting strategies. In: Calzolari, N., Kan, M.Y., Hoste, V., Lenci, A., Sakti, S., Xue, N. (eds.) Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024). pp. 2161–2177. ELRA and ICCL, Torino, Italia (May 2024), https://aclanthology.org/2024.lrec-main.195
  * [15] Schaeffer, R., Miranda, B., Koyejo, S.: Are emergent abilities of large language models a mirage? arXiv preprint arXiv:2304.15004 (2023)
  * [16] Testolin, A.: Can neural networks do arithmetic? a survey on the elementary numerical skills of state-of-the-art deep learning models. Applied Sciences 14(2), 744 (2024)
  * [17] Touvron, H., et al.: Llama 2: Open foundation and fine-tuned chat models. CoRR abs/2307.09288 (2023). https://doi.org/10.48550/ARXIV.2307.09288, https://doi.org/10.48550/arXiv.2307.09288
  * [18] Wang, X., Wei, J., Schuurmans, D., Le, Q.V., Chi, E.H., Narang, S., Chowdhery, A., Zhou, D.: Self-consistency improves chain of thought reasoning in language models. In: The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net (2023), https://openreview.net/pdf?id=1PL1NIMMrw
  * [19] Webb, T., Holyoak, K.J., Lu, H.: Emergent analogical reasoning in large language models. Nature Human Behaviour 7(9), 1526–1541 (2023)
  * [20] Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., et al.: Emergent abilities of large language models. arXiv preprint arXiv:2206.07682 (2022)
  * [21] Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E.H., Le, Q.V., Zhou, D.: Chain-of-thought prompting elicits reasoning in large language models. In: Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., Oh, A. (eds.) Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022 (2022)
  * [22] Yu, L., Jiang, W., Shi, H., Yu, J., Liu, Z., Zhang, Y., Kwok, J.T., Li, Z., Weller, A., Liu, W.: Metamath: Bootstrap your own mathematical questions for large language models. CoRR abs/2309.12284 (2023). https://doi.org/10.48550/ARXIV.2309.12284, https://doi.org/10.48550/arXiv.2309.12284
  * [23] Yue, X., Qu, X., Zhang, G., Fu, Y., Huang, W., Sun, H., Su, Y., Chen, W.: Mammoth: Building math generalist models through hybrid instruction tuning. CoRR abs/2309.05653 (2023). https://doi.org/10.48550/ARXIV.2309.05653, https://doi.org/10.48550/arXiv.2309.05653
  * [24] Zorzi, M., Testolin, A.: An emergentist perspective on the origin of number sense. Philosophical Transactions of the Royal Society B: Biological Sciences 373(1740), 20170043 (2018)


# On Infinite-horizon System Level Synthesis Problems

Olle Kjellqvist∗ and Jing Yu∗ * The authors contributed equally to this
work.OK is with the Department of Automatic Control, Lund University, Lund,
Sweden<EMAIL_ADDRESS>and has received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme under grant agreement No 834142
(ScalableControl).JY is with the Department of Computing and Mathematical
Sciences, California Institute of Technology, Pasadena, CA, USA,
<EMAIL_ADDRESS>
###### Abstract

System level synthesis is a promising approach that formulates structured
optimal controller synthesis problems as convex problems. This work solves the
distributed linear-quadratic regulator problem under communication constraints
directly in infinite-dimensional space, without the finite-impulse response
relaxation common in related work. Our method can also be used to construct
optimal distributed Kalman filters with limited information exchange. We
combine the distributed Kalman filter with state-feedback control to perform
localized LQG control with communication constraints. We provide agent-level
implementation details for the resulting output-feedback state-space
controller.

##  I INTRODUCTION

In recent years, control design for networked dynamical systems has seen
tremendous interest and progress. An important problems is to impose
structures on the controllers, such as sparsity for distributed or localized
control [1, 2], and communication delay constraints [2, 3]. Such control
design problems are challenging due to the non-convex nature of the problem
[4].

Lately, researchers have focused on novel controller parameterization that
admits convex formulation [5, 6, 7], with System Level Synthesis (SLS)
emerging as a promising and unified framework for structured controller
synthesis [8]. A vital feature of the SLS framework is that both the synthesis
and the implementation of the structured controller can be done locally, thus
scaling favorably with the number of subsystems in a network.

All current SLS-based control methods require both the parameterization and
implementation to have finite impulse responses (FIR), with the exception of
[9, 10]. This is because optimal controller synthesis, despite the choice of
convex reparameterization, is an infinite-dimensional non-convex optimization
problem over dynamical systems. The current method of choice to relax the
problem into a tractable finite-dimensional optimization problem is to
restrict the optimization variable to having a finite impulse response. Such
relaxation technique is required for many parameterizations other than SLS
[11]. Although previous work almost exclusively uses FIR approximations, we
emphasize that FIR is not a requirement for SLS, but rather a convenient way
to use off-the-shelf optimization software. Therefore, lifting the FIR
constraint will render SLS applicable to detectable and stabilizable systems.

An exception is [9], where the authors showed that a class of the infinite-
horizon state-feedback SLS problem has natural connections to the Riccati
solution for linear quadratic regulator (LQR) problems. The resulting SLS
controller has a state-space form that significantly reduces the required
memory compared to the FIR SLS controllers.

It is a natural next step to investigate the correspondence between infinite-
horizon output-feedback SLS and the linear quadratic Gaussian (LQG) control
[12, 13].

Contribution. This paper generalizes a previous result on infinite-horizon
state-feedback SLS problem, and investigates a class of infinite-horizon
output-feedback SLS problems. In particular, we study an output-feedback SLS
problem that corresponds to a class of LQG problems with structural
constraints expressable as convex sparsity constraints under the SLS
parameterization. Our contribution is three-fold. (1) We generalize the result
on the infinite-horizon state-feedback SLS solution [9] to scenarios where
communication delay constraints among subsystems in a network can be
incorporated into controller synthesis and implementation. (2) We provide a
suboptimal solution to a class of infinite-horizon output-feedback SLS
problems. Our solution leverages an analogous separation principle for SLS
parameterization, where the proposed generalized infinite-horizon state-
feedback SLS solution is used. A key advantage of our approach is the ability
to compute the parameters of each subsystem locally in one swoop using local
information without iterations or communications among subsystems, which were
required by previous methods. (3) We demonstrate an internally stabilizing
output-feedback controller that is distributed and localized based on the
proposed suboptimal solution. The proposed state-space controller has a fixed,
low memory requirement, unlike existing FIR-based SLS controllers where the
length of the memory grows linearly with the FIR horizon.

Paper Structure. We introduce the infinite-horizon SLS problems and related
concepts in Section II. Section III proposes a generalized approach that
solves the infinite-horizon state-feedback SLS problems with communication
delay and localization constraints. In Section IV, we construct a suboptimal
solution to the infinite-horizon output-feedback SLS problem using the
proposed optimal state-feedback solution. In Section V, we show the
implementation of the state-space controller associated with the constructed
suboptimal solution. Section VI demonstrates numerical simulation that
corroborates with the theoretical results.

Notation. Bold font $\mathbf{x}$ and $\mathbf{G}$ denote signals
$\mathbf{x}=\\{x(t)\\}_{t=0}^{\infty}$ with $x(t)\in\mathbb{R}^{n}$, and
proper transfer matrices $\mathbf{G}(z)=\sum_{i=0}^{\infty}z^{-i}G[i]$ with
convolution kernels $G[i]\in\mathbb{R}^{m\times n}$. The $j^{\text{th}}$
standard basis vector is denoted as $e_{j}$. For a matrix $A$, $A(i,j)$ refers
to the $(i,j)^{\text{th}}$ element, $A(i,:)$ to the $i^{\text{th}}$ row and
$A(:,j)$ to the $j^{\text{th}}$ column. Non-negative integers are denoted as
$\mathbb{N}_{+}$. We write $A\succ B$ ($A\succeq B$) to mean that $A-B$ is a
positive (semi)definite matrix. We use $\mathbb{R}\mathcal{H}_{\infty}$ for
the space of all proper and real rational stable transfer matrices and denote
$F\in\frac{1}{z}\mathbb{R}\mathcal{H}_{\infty}$ if and only if
$zF\in\mathbb{R}\mathcal{H}_{\infty}$.

##  II Preliminaries

We consider the following dynamical system

$\displaystyle x(t+1)$ $\displaystyle=Ax(t)+Bu(t)+w(t)$ (1) $\displaystyle
y(t)$ $\displaystyle=Cx(t)+v(t),$

where $w(t)\sim\mathcal{N}(0,W)$, and $v(t)\sim\mathcal{N}(0,V)$ are
respectively state and measurement noise independently and identically drawn
at each time from the zero-mean Gaussian distributions. Here $W$ and $V$ are
positive definite matrices. The general control design objective is to
synthesize a linear controller $\mathbf{K}$ such that control action computed
as $\mathbf{u}=\mathbf{Ky}$ stabilizes the closed-loop system while optimizing
over a quadratic cost
$J(\mathbf{x},\mathbf{u}):=\lim_{T\rightarrow\infty}\mathbb{E}\sum_{t=0}^{T}x(t)^{{\mkern-1.5mu\mathsf{T}}}Rx(t)+u(t)^{\mkern-1.5mu\mathsf{T}}Qu(t)$,
with $Q$, $R\succ 0$ . This is known as the linear quadratic Gaussian (LQG)
problem, where the optimal controller is given by the combination of a state-
feedback controller and a state observer[12].

In this paper, we investigate a _distributed_ variant of the LQG problem,
where (1) is constructed from a network of heterogeneous subsystems with
dynamical coupling. In particular, we aim to design a stabilizing output-
feedback controller that respects _communication delays_ and _localization
constraints_. For detalied discussions of such constraints, we refer
interested readers to [9, 14].

###  II-A System Level Synthesis

The SLS theory approaches the constrained output-feedback control design
problem described above by characterizing all achievable closed-loop mappings
(CLMs) from $\mathbf{w},\mathbf{v}$ to $\mathbf{x}$, $\mathbf{u}$ under an
internally stabilizing controller $\mathbf{K}$. Then, using any achievable
CLMs, SLS provides an implementation of the controller $\mathbf{K}$ that
realizes the prescribed CLMs. This is made precise in the following result.

######  Theorem 1 ([8]).

Strictly proper linear CLMs $\mathbf{\Phi}_{xx}$, $\mathbf{\Phi}_{xy}$,
$\mathbf{\Phi}_{ux}$,
$\mathbf{\Phi}_{uy}\in\frac{1}{z}\mathbb{R}\mathcal{H}_{\infty}$ can be
achieved by a linear internally stabilizing controller $\mathbf{K}$ if and
only if

$\displaystyle\begin{bmatrix}zI-A&-B\end{bmatrix}\begin{bmatrix}\mathbf{\Phi}_{xx}&\mathbf{\Phi}_{xy}\\\
\mathbf{\Phi}_{ux}&\mathbf{\Phi}_{uy}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}I&0\end{bmatrix}$ (2a)
$\displaystyle\begin{bmatrix}\mathbf{\Phi}_{xx}&\mathbf{\Phi}_{xy}\\\
\mathbf{\Phi}_{ux}&\mathbf{\Phi}_{uy}\end{bmatrix}\begin{bmatrix}zI-A\\\
-C\end{bmatrix}$ $\displaystyle=\begin{bmatrix}I\\\ 0\end{bmatrix},$ (2b)

where $\mathbf{\Phi}_{xx}$, $\mathbf{\Phi}_{xy}$, $\mathbf{\Phi}_{ux}$,
$\mathbf{\Phi}_{uy}$ maps $\mathbf{w},\mathbf{v}$ to $\mathbf{x}$,
$\mathbf{u}$ under a controller $\mathbf{K}$,
i.e.,$\begin{bmatrix}\mathbf{x}\\\
\mathbf{u}\end{bmatrix}=\begin{bmatrix}\mathbf{\Phi}_{xx}&\mathbf{\Phi}_{xy}\\\
\mathbf{\Phi}_{ux}&\mathbf{\Phi}_{uy}\end{bmatrix}\begin{bmatrix}\mathbf{w}\\\
\mathbf{v}\end{bmatrix}$. In particular, $\mathbf{K}$ can be implemented as
the following, which is illustrated in Figure 1:

$\displaystyle z\boldsymbol{\beta}$
$\displaystyle=\widehat{\mathbf{\Phi}}_{xx}\boldsymbol{\beta}+\widehat{\mathbf{\Phi}}_{xy}\mathbf{y}$
(3) $\displaystyle\mathbf{u}$
$\displaystyle=\widehat{\mathbf{\Phi}}_{ux}\boldsymbol{\beta}+\mathbf{\Phi}_{uy}\mathbf{y},$

where $\widehat{\mathbf{\Phi}}_{xx}=z(I-z\mathbf{\Phi}_{xx})$,
$\widehat{\mathbf{\Phi}}_{ux}=z\mathbf{\Phi}_{ux}$,
$\widehat{\mathbf{\Phi}}_{xy}=-z\mathbf{\Phi}_{xy}$, and $\beta$ is the
controller internal state.

Further, it was shown in [5] that (2) is equivalent to stabilizability and
detectability of (1). Therefore, (3) parameterizes all internally stabilizing
linear controller $\mathbf{K}$ for (1).

A special case of Theorem 1 is when the controller is _state-feedback_ , i.e.,
$\mathbf{u}=\mathbf{K}\mathbf{x}$. In this scenario, the SLS CLMs reduce to
only $\mathbf{\Phi}_{xw}:\mathbf{w}\rightarrow\mathbf{x}$ and
$\mathbf{\Phi}_{uw}:\mathbf{w}\rightarrow\mathbf{u}$ with the following
variation of Theorem 1.

######  Theorem 2 ([5]).

For the dynamics (1) with $C=I$ and $v(t)\equiv 0$, CLMs $\mathbf{\Phi}_{xw}$
and $\mathbf{\Phi}_{uw}$ can be achieved by a linear internally stabilizing
controller $\mathbf{K}$ if and only if

$\displaystyle\begin{bmatrix}zI-A&-B\end{bmatrix}\begin{bmatrix}\mathbf{\Phi}_{xw}\\\
\mathbf{\Phi}_{uw}\end{bmatrix}$
$\displaystyle=I,\quad\mathbf{\Phi}_{xw},\,\mathbf{\Phi}_{uw}\in\frac{1}{z}\mathbb{R}\mathcal{H}_{\infty}.$
(4)

$\frac{1}{z}$$A$$C$$B$$+$$\frac{1}{z}$$\widehat{\mathbf{\Phi}}_{xx}$$\widehat{\mathbf{\Phi}}_{xy}$$\widehat{\mathbf{\Phi}}_{ux}$$\mathbf{\Phi}_{uy}$$+$$+$$+$$\boldsymbol{\delta}_{u}$$\boldsymbol{\delta}_{x}$$\boldsymbol{\delta}_{y}$$\boldsymbol{\delta}_{\beta}$$\mathbf{u}$$\mathbf{x}$$\boldsymbol{\beta}$$\mathbf{y}$

Figure 1: Output-feedback controller architecture. Here,
$\widehat{\mathbf{\Phi}}_{xx}=z(I-z\mathbf{\Phi}_{xx})$,
$\widehat{\mathbf{\Phi}}_{ux}=z\mathbf{\Phi}_{ux}$ and
$\widehat{\mathbf{\Phi}}_{xy}=-z\mathbf{\Phi}_{xy}$. The controller is
internally stable; the closed-loop maps from perturbations
$(\boldsymbol{\delta}_{x},\boldsymbol{\delta}_{y},\boldsymbol{\delta}_{u},\boldsymbol{\delta}_{\beta})$
to internal signals $(\mathbf{x},\mathbf{y},\mathbf{u},\boldsymbol{\beta})$
are stable.

###  II-B System-level Constraints (SLCs)

In this paper, we consider a networked system (1) composed of $N$ subsystems,
where each subsystem $i$ has the following dynamics

$\displaystyle x_{i}(t+1)$
$\displaystyle=\sum_{j\in\mathcal{N}_{\text{in}}^{1}(i)}\left(A_{ij}x_{j}(t)+B_{ij}u_{j}(t)\right)+w_{i}(t)$
(5) $\displaystyle y_{i}(t)$ $\displaystyle=C_{i}x_{i}(t)+v_{i}(t)$ (6)

where we denote $j\in\mathcal{N}_{\text{in}}^{k}(i)$ if the states and control
actions of subsystem $j$ affect those of subsystem $i$ in $k$ time steps
through the open-loop network dynamics. Analogously, we write
$i\in\mathcal{N}_{\text{out}}^{k}(j)$ when the states of subsystem $i$ are
affected by subsystem $j$ via dynamics in $k$ time steps.

For such systems, it is common to impose structural constraints such as
localization requirement and communication delay for control design. A large
class of such structural constraints can be characterized as convex
constraints on CLMs. This is called the system-level constraints (SLCs) [5].
Examples of SLCs include sparsity constraints on the Youla parameter, QI
subspace constraints on controller $\mathbf{K}$, and FIR constraints on the
closed-loop responses to noises.

In this paper, we consider the family of SLCs that can be formulated as
sparsity constraints on the CLMs. This family includes disturbance
localization and communication delay constraints considered in [9]. We denote
any such sparsity constraints as $\mathcal{S}:=\\{S[k]\\}_{k=1}^{\infty}$
where each $S[k]\in\\{0,1\\}^{n\times n}$ are binary matrices specifying the
sparsity of the kernels of CLMs. Specifically, we consider the localization
SLCs, which specifies how disturbances at each subsystem must be localized to
a neighborhood.

######  Definition 1 (Localization SLCs).

An SLC $\mathcal{S}:=\\{S[k]\\}_{k=1}^{\infty}$ is called the localization SLC
if $S[k]$ for all $k$ are the same binary matrices.

In addition to disturbance localization which assumes instantaneous
information exchange within a localization neighborhood, one may wish to
incorporate communication delay SLCs111Such delayed localization pattern
corresponds to scenarios when communication delays allow disturbances to
propagate through dynamics, before subsystems are able to completely attenuate
and localize them. For ease of exposition, here we consider a communication
delay pattern among subsystems that matches the dynamics. The results in this
paper can be generalized to broader classes of communication patterns.. Let
$\text{Sp}(\cdot)$ denote the support of a matrix.

######  Definition 2 (d-Delayed localization SLCs).

For a fixed integer $d\geq 1$ and sparsity pattern of the dynamics
$\mathbb{A}:=\text{Sp}\left(A\right)$, a delayed localization SLC is such that
$S[k]=\text{Sp}\left(\mathbb{A}^{k}\right)$ for $k\leq d$ and
$S[k]=\text{Sp}\left(\mathbb{A}^{d}\right)$ for all $k\geq d$.

This is sometimes called the $(A,d)$-sparsity [2] and generalizes the
localization SLCs. We say $\mathbf{\Phi}_{xx}\in\mathcal{S}$ if $\Phi_{xx}[k]$
has the same sparsity pattern as $S[k]$ for all $k\in\mathbb{N}_{+}$. For the
rest of paper, we consider d-delayed localization SLCs for structured
controller synthesis. We assume that any given SLCs are feasible for the
underlying system.

###  II-C The State-feedback and Output-feedback SLS Problem

Given d-delayed localization SLCs $\mathcal{S}_{x}$ and $\mathcal{S}_{u}$
specifying the state and input closed-loop sparsity respectively, we now state
the output-feedback (OF) SLS problem [5].

$\displaystyle\underset{\mathbf{\Phi}\in\frac{1}{z}\mathbb{R}\mathcal{H}_{\infty}}{\text{min}}$
$\displaystyle\left\|\begin{bmatrix}Q^{1/2}&0\\\
0&R^{1/2}\end{bmatrix}\begin{bmatrix}\mathbf{\Phi}_{xx}&\mathbf{\Phi}_{xy}\\\
\mathbf{\Phi}_{ux}&\mathbf{\Phi}_{uy}\end{bmatrix}\begin{bmatrix}W^{1/2}&0\\\
0&V^{1/2}\end{bmatrix}\right\|_{\mathcal{H}_{2}}$ s.t.
$\displaystyle\text{Constraints \eqref{eq:output-feasibility}},\quad$
$\displaystyle\Phi_{xx}[k]\,,\Phi_{xy}[k]\in S_{x}[k]\text{ for
}k\in\mathbb{N}_{+}$ (OF-SLS) $\displaystyle\Phi_{ux}[k]\,,\Phi_{uy}[k]\in
S_{u}[k]\text{ for }k\in\mathbb{N}_{+}\,.$

where we used $\mathbf{\Phi}$ to collectively refer to the tuple
$\left(\mathbf{\Phi}_{xx},\mathbf{\Phi}_{ux},\mathbf{\Phi}_{xy},\mathbf{\Phi}_{uy}\right)$
to reduce notation. Control problem (OF-SLS) is similar to the classical LQG
problem but differs in the additional constraints on the system responses that
corresponds to disturbance localization and information delay.

As a special case, the state-feedback (SF) SLS problem is

$\displaystyle\underset{\mathbf{\Phi}_{xw},\mathbf{\Phi}_{uw}}{\text{min}}$
$\displaystyle\left\|\begin{bmatrix}Q^{1/2}&0\\\
0&R^{1/2}\end{bmatrix}\begin{bmatrix}\mathbf{\Phi}_{xw}\\\
\mathbf{\Phi}_{uw}\end{bmatrix}\right\|_{\mathcal{H}_{2}}$ s.t.
$\displaystyle\text{Constraints }\eqref{eq:sf-feasibility}$ (SF-SLS)
$\displaystyle\Phi_{xw}[k]\in S_{x}[k],\,\,\,\Phi_{uw}[k]\in S_{u}[k]\text{
for }k\in\mathbb{N}_{+}\,.$

##  III Optimal solution to State-feedback SLS

In this section, we derive the optimal solution to (SF-SLS). This generalizes
[9] to account for the _delayed_ localization constraints. This solution
allows the subsequent output-feedback controller synthesis.

Because (SF-SLS) is column-wise separable [14], we will synthesize the closed-
loop maps one column at a time so that each subsystem can synthesize the
columns corresponds to its local states, in a parallel fashion. Such parallel
synthesis scales favorably with the number of subsystems in the network. From
here on, everything will be seen by the $i$th subsystem222To reduce notation,
we assume each subsystem has scalar dynamics. One can alleviate this
assumption by running the algorithm for multiple columns per subsystem.. Let
$\boldsymbol{\varphi_{x}}:=\mathbf{\Phi}_{xw}(:,i)$ and
$\boldsymbol{\varphi_{u}}:=\mathbf{\Phi}_{uw}(:,i)$ with kernels
$\varphi_{x}[k]$ and $\varphi_{u}[k]$ for $k\in\mathbb{N}_{+}$, respectively
corresponding to the $i$th column of $\mathbf{\Phi}_{xw}$ and
$\mathbf{\Phi}_{uw}$. Furthermore we use $s_{x}[k]$ and $s_{u}[k]$ denote the
$i{\text{th}}$ column of $S_{x}[k]$ and $S_{u}[k]$ respectively. Each
corresponding column problem to be solved locally by subsystem $i$ becomes

$\displaystyle\underset{\boldsymbol{\varphi_{x}},\boldsymbol{\varphi_{u}}}{\text{min}}\quad$
$\displaystyle\sum_{k=1}^{\infty}\varphi_{x}[k]^{\mkern-1.5mu\mathsf{T}}Q\varphi_{x}[k]+\varphi_{u}[k]^{\mkern-1.5mu\mathsf{T}}R\varphi_{u}[k]$
s.t. $\displaystyle\varphi_{x}[k+1]=A\varphi_{x}[k]+B\varphi_{u}[k]$ (7a)
$\displaystyle\varphi_{x}[0]=0,\quad\varphi_{x}[1]=e_{i}$
$\displaystyle\varphi_{x}[k]\in s_{x}[k],\ \varphi_{u}[k]\in s_{u}[k].$ (7b)

This new problem is a constrained linear quadratic optimal control problem,
and would be a standard infinite-horizon LQR problem if not for the sparsity
constraints (7b). We will show how to transform this problem to a finite-
horizon LQR problem with time-varying dynamics.

###  III-A Derivation of the Optimal Solution

Let $n_{x}[k]$ be the number of nonzero elements in the $n$-dimensional vector
$s_{x}[k]$ and $n_{u}[k]$ be the number of nonzero elements in $s_{u}[k]$.
Then there exists a surjective matrix
$M_{x}[k]\in\mathbb{R}^{(n-n_{x}[k])\times n}$ and an injective matrix
$M_{u}[k]\in\mathbb{R}^{m\times n_{u}[k]}$ such that (7b) is equivalent to

$M_{x}[k]\varphi_{x}[k]=0,\quad\varphi_{u}[k]=M_{u}[k]q[k],$ (8)

where $q[k]\in\mathbb{R}^{n_{u}[k]}$ becomes the new variable. In particular,
one can construct $M_{x}[k]$ by horizontally stacking standard basis vectors
with nonzero positions corresponding to the positions that are zero in
$\varphi_{x}[k]$. On the other hand, $M_{u}[k]$ can be obtained similarly but
with basis vectors corresponding to the nonzero positions in $\varphi_{u}[k]$.
Since $\varphi_{x}[k+1]$ is uniquely determined by $\varphi_{x}[k]$ and
$\varphi_{u}[k]$, substitution of (8) into (7a) yields

$M_{x}[k+1]A\varphi_{x}[k]+\underbrace{M_{x}[k+1]BM_{u}[k]}_{F[k]}q[k]=0.$ (9)

The solutions to (9) can be expressed as

$q[k]=F[k]^{\dagger}M_{x}[k+1]A\varphi_{x}[k]+N_{F}[k]r[k],$ (10)

where $N_{F}[k]\in\mathbb{R}^{n_{u}[k]\times n_{r}[k]}$ is a bijection onto
the nullspace of $F[k]$. The vector $r[k]\in\mathbb{R}^{n_{r}[k]}$ is now our
new unconstrained optimization variable. Substituting
$\varphi_{u}[k]=M_{u}[k]q[k]$ and (10) into the optimal control problem we get
the equivalent time-varying LQR problem

$\displaystyle\underset{r[k]\in\mathbb{R}^{n_{r}[k]}}{\text{min}}\quad$
$\displaystyle\sum_{k=1}^{\infty}\Big{(}\varphi_{x}[k]^{\mkern-1.5mu\mathsf{T}}\tilde{Q}[k]\varphi_{x}[k]+$
$\displaystyle\quad
2r[k]^{\mkern-1.5mu\mathsf{T}}\tilde{Z}\varphi_{x}[k]+r[k]^{\mkern-1.5mu\mathsf{T}}\tilde{R}[k]r[k]\Big{)}$
s.t. $\displaystyle\varphi_{x}[k+1]=\tilde{A}\varphi_{x}[k]+\tilde{B}[k]r[k]$
(11) $\displaystyle\varphi_{x}[0]=0,\quad\varphi_{x}[1]=e_{i},$

where

$\displaystyle\kappa[k]$ $\displaystyle=M_{u}[k]F[k]^{\dagger}M_{x}[k+1]A$
$\displaystyle\tilde{Z}[k]$
$\displaystyle=N_{F}[k]^{\mkern-1.5mu\mathsf{T}}M_{u}[k]^{\mkern-1.5mu\mathsf{T}}R\kappa[k],\quad\tilde{Q}[k]=Q+\kappa[k]^{\mkern-1.5mu\mathsf{T}}R\kappa[k]$
$\displaystyle\tilde{R}[k]$
$\displaystyle=(M_{u}[k]N_{F}[k])^{\mkern-1.5mu\mathsf{T}}R[k]M_{u}[k]N_{F}[k]$
(12) $\displaystyle\tilde{A}[k]$
$\displaystyle=A-B\kappa[k],\quad\tilde{B}[k]=BM_{u}[k]N_{F}[k].$

Finally we note that for $k\geq d+1$, the localization patterns are constant,
implying that the dynamics matrices of the transformed problem are static for
$k\geq d+1$. Standard dynamic programming arguments allow us to first solve
the Riccati equation for the time-invariant problem for $k\geq d+1$ to get the
positive definite solution $\tilde{X}_{\star}$ and the feedback gain
$\tilde{K}_{\star}$, and then to solve a finite-horizon time-varying problem
by replacing the cost function of each column problem (11) with equivalent
cost function

$\displaystyle J$
$\displaystyle=\sum_{k=1}^{d}\Big{(}\varphi_{x}[k]^{\mkern-1.5mu\mathsf{T}}\tilde{Q}[k]\varphi_{x}[k]+2r[k]^{\mkern-1.5mu\mathsf{T}}\tilde{Z}\varphi_{x}[k]+r[k]^{\mkern-1.5mu\mathsf{T}}\tilde{R}[k]r[k]\Big{)}$
$\displaystyle+\varphi_{x}[d+1]^{\mkern-1.5mu\mathsf{T}}\tilde{X}_{\star}\varphi_{x}[d+1].$
(13)

To obtain $\tilde{X}_{\star}$ and $\tilde{K}_{\star}$, we invoke the results
in [9] for the time-invariant problem for with staic localization pattern.
Finally, the solution to the time-varying finite-horizon problem (11) with
cost (13) is given by the Riccati iteration with
$\tilde{X}[d+1]=\tilde{X}_{\star}$, and for $k=1,\dots,d$,

$\displaystyle\tilde{X}[k]$
$\displaystyle=\tilde{Q}[k]+\tilde{A}[k]^{\mkern-1.5mu\mathsf{T}}\tilde{X}[k+1]\tilde{A}[k]-$
$\displaystyle\left(\tilde{A}[k]^{\mkern-1.5mu\mathsf{T}}\tilde{X}[k+1]\tilde{B}[k]+\tilde{Z}[k]\right)$
$\displaystyle\cdot\left(\tilde{R}[k]+\tilde{B}[k]^{\mkern-1.5mu\mathsf{T}}\tilde{X}[k+1]B[k]\right)^{-1}\left(\tilde{B}[k]^{\mkern-1.5mu\mathsf{T}}\tilde{X}[k+1]\tilde{A}[k]\right)$
$\displaystyle\tilde{K}[k]$
$\displaystyle=\left(\tilde{R}[k]+\tilde{B}[k]\tilde{X}[k+1]\tilde{B}[k]\right)^{-1}$
$\displaystyle\quad\cdot\left(\tilde{B}[k]^{\mkern-1.5mu\mathsf{T}}\tilde{X}[k+1]\tilde{A}[k]+\tilde{Z}[k]^{\mkern-1.5mu\mathsf{T}}\right).$
(14)

Substituting $r[k]=\tilde{K}[k]\varphi_{x}[k]$ into (10) and further into (9),
one can obtain the solution to the original problem (7). We formally state the
optimality of the proposed solution.

######  Theorem 3.

Fix delayed localization SLCs $\mathcal{S}_{x}$ and $\mathcal{S}_{u}$. The
optimal solution to the infinite-horizon state-feedback SLS problem in (SF-
SLS) is given, in a column-wise fashion, by

$\displaystyle\mathbf{\Phi}_{xw}^{\star}(:,i)=\left[\begin{array}[]{c|
c}A_{\text{SF}}^{i}&B_{\text{SF}}^{i}\\\ \hline\cr
C_{\text{SF}}^{i}&0\end{array}\right],\,\,\mathbf{\Phi}_{uw}^{\star}(:,i)=\left[\begin{array}[]{c|
c}A_{\text{SF}}^{i}&B_{\text{SF}}^{i}\\\ \hline\cr
K_{\text{SF}}^{i}&0\end{array}\right]\,,$ (19)

where

$\displaystyle A_{\text{SF}}^{i}$ $\displaystyle=\begin{bmatrix}0&\dots&&&0\\\
\tilde{A}_{\text{CL},i}[1]&0&\dots&&0\\\
0&\tilde{A}_{\text{CL},i}[2]&0&\dots&0\\\ 0&0&\ddots&&\vdots\\\
&&&\tilde{A}_{\text{CL},i}[d]&\tilde{A}_{\text{CL},\star,i}\end{bmatrix}$
$\displaystyle B_{\text{SF}}^{i}$
$\displaystyle=\begin{bmatrix}e_{i}^{\mkern-1.5mu\mathsf{T}}&0\dots
0\end{bmatrix}^{\mkern-1.5mu\mathsf{T}}\quad
C_{\text{SF}}^{i}=\begin{bmatrix}I&I\dots&I\end{bmatrix}$ $\displaystyle
K_{\text{SF}}^{i}$
$\displaystyle=\begin{bmatrix}\tilde{K}_{i}[1]&\tilde{K}_{i}[2]&\dots&\tilde{K}_{i}[d]&\tilde{K}_{\star,i}\end{bmatrix},$
(20)

with $\tilde{K}_{i}[k]$ and
$\tilde{A}_{\text{CL},i}[k]:=\tilde{A}[k]-\tilde{B}[k]\tilde{K}[k]$ computed
using (12) and (14) for the $i{\text{th}}$ column problem. Matrix
$\tilde{A}_{\text{CL},\star,i}$ and $\tilde{K}_{\star,i}$ are given by the
infinite-horizon solution with static localization SLCs $\mathcal{S}_{x}\equiv
S_{x}[d]$ and $\mathcal{S}_{u}\equiv S_{u}[d]$ using the method in [9, Section
IV.A].

###### Proof.

The optimality follows directly from the column separable property of (SF-
SLS), and the equivalent transformations between (7) and (11). The finite-
horizon LQR problem with cost (13) is equivalent to (11) by Bellman’s
optimality principle. It is straightforward to verify that (19) is a state-
space realization of the solution to (11) by substituting the optimal solution
$r[k]$ via (14) into (10). ∎

Compared to [9], the state-space realization of the optimal CLMs given by our
approach has a higher order because of the first $d$-delay pattern. If we let
the first $d$ delay sparsity pattern to be the same as the localization
pattern, then our approach subsumes the results in [9].

Given the column-wise state-space description of the optimal CLMs
$\mathbf{\Phi}_{xw}^{\star}(:,i)$ and $\mathbf{\Phi}_{xw}^{\star}(:,i)$, we
can adopt the same state-space agent-level controller proposed in [9, Section
IV.B] by simply replacing the state-space implementation of the CLMs with the
ones presented here.

###  III-B Structured Kalman Filter Design

Theorem 3 can be used to solve the dual problem of optimal structured Kalman
filter design with delayed localization SLCs for (1) [15]. In particular, the
optimal structured infinite-horizon CLMs that map $\mathbf{w}$ and
$\mathbf{v}$ to state estimation error $\mathbf{e}$ under a linear observer
$\mathbf{L}$ with respect to the mean estimation error is given by the
solution to the dual problem of (SF-SLS) as shown below:

$\displaystyle\underset{\mathbf{\Phi}_{ew},\mathbf{\Phi}_{ev}\in\frac{1}{z}\mathbb{R}\mathcal{H}_{\infty}}{\text{min}}$
$\displaystyle\left\|\begin{bmatrix}W^{1/2}&0\\\
0&V^{1/2}\end{bmatrix}\begin{bmatrix}\mathbf{\Phi}_{ew}^{\top}\\\
\mathbf{\Phi}_{ev}^{\top}\end{bmatrix}\right\|_{\mathcal{H}_{2}}$ (21) subject
to
$\displaystyle\begin{bmatrix}\mathbf{\Phi}_{ew}&\mathbf{\Phi}_{ev}\end{bmatrix}\begin{bmatrix}zI-A\\\
-C\end{bmatrix}=I$ (22)
$\displaystyle\mathbf{\Phi}_{ew}\in\mathcal{S}_{x},\quad\mathbf{\Phi}_{ev}\in\mathcal{S}_{u}.$

Readers are referred to [15] for detailed derivation. We highlight the
resemblance between constraints (4) and (22), and (2). In what follows, we
will use the optimal solutions from the state-feedback and Kalman-filter SLS
problem to construct a suboptimal solution to the output-feedback SLS problem.

##  IV A solution Inspired by Separation Principle

It is well known that for a linear system, observer-based feedback is always
stabilizing if the observer error dynamics are stable and the feedback gain
stabilizes the state-feedback case. In [5], the authors pointed out that a
similar property holds for CLMs from state-feedback and kalman-filter SLS
problems described in Section III.

######  Theorem 4 ([8]).

Assume there exist stable and strictly proper transfer matrices
$\mathbf{\Phi}^{\text{SF}}=(\mathbf{\Phi}^{\text{SF}}_{xw},\mathbf{\Phi}^{\text{SF}}_{uw})$
and
$\mathbf{\Phi}^{\text{KF}}=(\mathbf{\Phi}^{\text{KF}}_{ew},\mathbf{\Phi}^{\text{KF}}_{ev})$
satisfying

$\displaystyle\begin{bmatrix}zI-A&-B\end{bmatrix}\begin{bmatrix}\mathbf{\Phi}^{\text{SF}}_{xw}\\\
\mathbf{\Phi}^{\text{SF}}_{uw}\end{bmatrix}$ $\displaystyle=I,$
$\displaystyle\begin{bmatrix}\mathbf{\Phi}^{\text{KF}}_{ew}&\mathbf{\Phi}^{\text{KF}}_{ev}\end{bmatrix}\begin{bmatrix}zI-A\\\
-C\end{bmatrix}$ $\displaystyle=I.$

The transfer functions

$\displaystyle\mathbf{\Phi}_{xx}$
$\displaystyle=\mathbf{\Phi}^{\text{SF}}_{xw}+\mathbf{\Phi}^{\text{KF}}_{ew}-\mathbf{\Phi}^{\text{SF}}_{xw}(zI-A)\mathbf{\Phi}^{\text{KF}}_{ew}$
(23) $\displaystyle\mathbf{\Phi}_{ux}$
$\displaystyle=\mathbf{\Phi}^{\text{SF}}_{uw}-\mathbf{\Phi}^{\text{SF}}_{uw}(zI-A)\mathbf{\Phi}^{\text{KF}}_{ew}$
$\displaystyle\mathbf{\Phi}_{xy}$
$\displaystyle=\mathbf{\Phi}^{\text{KF}}_{ev}-\mathbf{\Phi}^{\text{SF}}_{xw}(zI-A)\mathbf{\Phi}^{\text{KF}}_{ev}$
$\displaystyle\mathbf{\Phi}_{uy}$
$\displaystyle=-\mathbf{\Phi}^{\text{SF}}_{uw}(zI-A)\mathbf{\Phi}^{\text{KF}}_{ev}$

are strictly proper and satisfy (2).

Then, output-feedback controller (3) can be constructed using CLMs from (23)
to stabilize (1) while respecting the prescribed localization and
communication delay constraints.

##  V Local Controller implementation

This section describes Algorithm 1, which summarizes the local implementation
of the global controller (3) in Fig. 1 using the localized state-feedback
controllers and Kalman filters of Section III and Theorem 4.

_Globally_ , the controller after plugging (23) in the controller (3) is shown
in Fig. 2.

Figure 2: Controller implementation of Fig. 1 after plugging (23) in the
controller (3).

Consider the intermediate signals in Fig. 2,

$\displaystyle\boldsymbol{\zeta}$
$\displaystyle=-\mathbf{\Phi}^{\text{SF}}_{xw}\overbrace{(zI-A)\mathbf{\Phi}^{\text{KF}}_{ev}\mathbf{y}}^{\widetilde{\mathbf{v}}}+\overbrace{\mathbf{\Phi}^{\text{KF}}_{ev}\mathbf{y}}^{\widehat{\mathbf{v}}}$
(24) $\displaystyle\boldsymbol{\theta}$
$\displaystyle=-\mathbf{\Phi}^{\text{SF}}_{uw}(zI-A)\mathbf{\Phi}^{\text{KF}}_{ev}\mathbf{y}$
$\displaystyle\boldsymbol{\alpha}$
$\displaystyle=\mathbf{\Phi}^{\text{SF}}_{xw}\overbrace{(\boldsymbol{\beta}-(zI-A)\mathbf{\Phi}^{\text{KF}}_{ew}\boldsymbol{\beta})}^{\widetilde{\mathbf{w}}}+\overbrace{\mathbf{\Phi}^{\text{KF}}_{ew}\boldsymbol{\beta}}^{\widehat{\mathbf{w}}},$
$\displaystyle\boldsymbol{\gamma}$
$\displaystyle=\mathbf{\Phi}^{\text{SF}}_{uw}(\boldsymbol{\beta}-(zI-A)\mathbf{\Phi}^{\text{KF}}_{ew}\boldsymbol{\beta}).$

With these intermediate signals, we can compute the controller internal state
$\boldsymbol{\beta}$ and the control signal $\mathbf{u}$ in Fig. 1 from
$z\boldsymbol{\beta}=-z(A\boldsymbol{\alpha}+B_{2}\boldsymbol{\gamma})-z\boldsymbol{\zeta}$,
and $\mathbf{u}=z\boldsymbol{\gamma}+\boldsymbol{\theta}$.

_Locally_ , due to the communication constraints specified in Section II-B,
one can not carry out the computation described above in a centralized way. In
particular, the local computation of each signal in (24) involves delayed and
locally available information. We now describe the information exchange among
subsystems and how they compute (24). Recall that the state-feedback solution
$\mathbf{\Phi}^{\text{SF}}$ and Kalman-filters $\mathbf{\Phi}^{\text{KF}}$
from (19) are synthesized to respect the communication constraints expressed
as d-Delayed localization SLCs. Denote

$\mathbf{\Phi}^{\text{SF}}_{w}(:,i)=\left[\begin{array}[]{c|
c}A_{\text{SF}}^{i}&B_{\text{SF}}^{i}\\\ \hline\cr I&0\end{array}\right].$
(25)

Then
$\mathbf{\Phi}^{\text{SF}}_{xw}(:,i)=C^{i}_{\text{SF}}\mathbf{\Phi}^{\text{SF}}_{w}(:,i)$
and
$\mathbf{\Phi}^{\text{SF}}_{uw}(:,i)=K^{i}_{\text{SF}}\mathbf{\Phi}^{\text{SF}}_{w}(:,i)$
where $C^{i}_{\text{SF}}$ and $K^{i}_{\text{SF}}$ are from (20). Computing the
local components of $\boldsymbol{\alpha}$ and $\boldsymbol{\beta}$ requires
only one realization of $\mathbf{\Phi}^{\text{SF}}_{w}$ as they can share the
same copy of the states within each subsystem. An analogous statement holds
true for $\boldsymbol{\zeta}$ and $\boldsymbol{\theta}$. Denote the two
realizations of (25) as $\mathbf{\Phi}^{\text{SF}}_{w,\alpha}$ and
$\mathbf{\Phi}^{\text{SF}}_{w,\zeta}$. During each time step $t$, every node
observes its local output $y_{i}(t)$ and goes through four stages of
computation and communication with its neighbors leading to an update to the
internal controller states and the application of the actuator signal
$u_{i}(t)$. This is summarized in Algorithm 1 with subroutines 1–4 describing
these computations in detail.

Algorithm 1 Local computation of controller signals

1:for Each node $i=1,\ldots,N$ do

2: Input ${\mathbf{\Phi}}^{\text{SF}}_{w,\alpha}(:,i)$,
${\mathbf{\Phi}}^{\text{SF}}_{w,\zeta}(:,i)$,
${\mathbf{\Phi}}^{\text{KF}}_{ew}(:,i)$,
${\mathbf{\Phi}}^{\text{KF}}_{ev}(:,i)$

3: Initialize $\beta_{i}(0)\leftarrow 0$, $w_{i}(t)\leftarrow 0$,
$v_{i}(t)\leftarrow 0$

4:end for

5:for $t=0,1,\ldots$ do

6: for Each node $i=\\{1,\ldots,N\\}$ do $\triangleright$ parallel

7: Observe $y_{i}(t)$

8: Receive $\beta_{j}(t)$ and $y_{j}(t)$ from
$j\in\mathcal{N}_{\text{in}}^{d}(i)$

9: subroutine1()

10: Receive $\widehat{w}_{j}(t)$ and $\widehat{v}_{j}(t)$ from
$j\in\mathcal{N}_{\text{in}}^{1}(i)$

11: subroutine2()

12: Receive $\widehat{\alpha}^{(\mathcal{N}_{\text{out}}^{d}(j))}(t+1)$,
$\widehat{\zeta}^{(\mathcal{N}_{\text{out}}^{d}(j))}(t+1)$,
$\widehat{\gamma}^{(\mathcal{N}_{\text{out}}^{d}(j))}(t+1)$ and
$\widehat{\theta}^{(\mathcal{N}_{\text{out}}^{d}(j))}(t)$ from
$j\in\mathcal{N}_{\text{in}}^{d}(i)$.

13: subroutine3()

14: Receive $\alpha_{j}(t+1)$ and $\gamma_{j}(t+1)$ from
$j\in\mathcal{N}_{\text{in}}^{1}(i)$

15: subroutine4()

16: Apply $u_{i}(t)$

17: end for

18:end for

Control signal computation at subsystem $i$ begins by receiving the
measurements from neighbors $j$ at most $d$ steps away (line 8) and computing
the $i$th element of the internal signals $\hat{v}(t+1)$ and $\hat{w}(t+1)$
via Subroutine 1, which is illustrated in Fig. 1. Here the function
$\text{step}(G,u)$ means that the internal dynamics of the system $G$ is
propagated one time-step with the input $u$.

Subroutine 1 Compute $\widehat{w}_{i}(t+1)$ and $\widehat{v}_{i}(t+1)$

Receive $\beta_{j}(t)$ and $y_{j}(t)$ from
$j\in\mathcal{N}_{\text{in}}^{d}(i)$

$\beta_{[\mathcal{N}_{\text{in}}^{d}(i)]}(t)\leftarrow\text{vec}(\beta_{j_{1}}(t),\ldots,\beta_{j_{m}}(t))$

$y_{[\mathcal{N}_{\text{in}}^{d}(i)]}(t)\leftarrow\text{vec}(y_{j_{1}}(t),\ldots,y_{j_{m}}(t))$

$\widehat{w}_{i}(t+1)\leftarrow\text{step}(z{\mathbf{\Phi}}^{\text{KF}}_{ew}(i,:),\beta_{[\mathcal{N}_{\text{in}}^{d}(i)]}(t))$

$\widehat{v}_{i}(t+1)\leftarrow\text{step}(z{\mathbf{\Phi}}^{\text{KF}}_{ev}(i,:),y_{[\mathcal{N}_{\text{in}}^{d}(i)]}(t))$

$\mathbf{y}_{i}$$\mathbf{y}_{j_{1}}$$\mathbf{y}_{j_{m}}$$\vdots$$\vdots$${\mathbf{\Phi}}^{\text{KF}}_{ev}(i,:)$$\widehat{\mathbf{v}}_{i}$$\mathbf{y}_{[\mathcal{N}_{\text{in}}^{d}(i)]}$

Figure 3: Illustration of subroutine 1. The computation of $\widehat{w}$ is
similar.

In the second stage, the node receives $\widehat{v}_{j}(t)$ and
$\widehat{w}_{j}(t)$ from its closest neighbors (line 10) and computes the
outgoing components of (24). The computations are outlined in Subroutine 2 and
illustrated in Fig. 4.

$\widehat{\mathbf{v}}_{i}$$\widehat{\mathbf{v}}_{j_{1}}$$\widehat{\mathbf{v}}_{j_{m}}$$\vdots$$\vdots$$A(i,:)$$-z$$+$$\widetilde{\mathbf{v}}_{i}$$\widehat{\mathbf{v}}_{[\mathcal{N}_{\text{in}}^{1}(i)]}$${\mathbf{\Phi}}^{\text{SF}}_{w,\zeta}(:,i)$$C_{SF}^{i}$outoutout$\vdots$$\vdots$$\boldsymbol{\xi}_{i}$$\widehat{\boldsymbol{\zeta}}^{(\mathcal{N}_{\text{out}}^{1}(i))}$$\widehat{\boldsymbol{\zeta}}^{(\mathcal{N}_{\text{out}}^{1}(i))}_{j_{1}}$$\widehat{\boldsymbol{\zeta}}^{(\mathcal{N}_{\text{out}}^{1}(i))}_{i}$$\widehat{\boldsymbol{\zeta}}^{(\mathcal{N}_{\text{out}}^{1}(i))}_{j_{m}}$$K^{i}_{SF}$$\widehat{\boldsymbol{\theta}}^{(\mathcal{N}_{\text{out}}^{1}(i))}$

Figure 4: Illustration of subroutine 2. Subroutine 2 Compute the outgoing
components of (24)

$\widehat{w}_{[\mathcal{N}_{\text{in}}^{1}(i)]}(t)\leftarrow\text{vec}(\widehat{w}_{j_{1}}(t),\ldots,\widehat{w}_{j_{m}}(t))$

$\widehat{v}_{[\mathcal{N}_{\text{in}}^{1}(i)]}(t)\leftarrow\text{vec}(\widehat{v}_{j_{1}}(t),\ldots,\widehat{v}_{j_{m}}(t))$

$\widetilde{w}_{i}(t)=\beta_{i}(t)+A\widehat{w}_{[\mathcal{N}_{\text{in}}^{1}(i)]}(t)-\widehat{w}_{i}(t+1)$

$\widetilde{v}_{i}(t)=A\widehat{v}_{[\mathcal{N}_{\text{in}}^{1}(i)]}(t)-\widehat{v}_{i}(t+1)$

$\lambda_{i}(t+1)\leftarrow\text{step}({\mathbf{\Phi}}^{\text{SF}}_{w,\alpha}(:,i),e_{i}\widetilde{w}_{i}(t))$

$\xi_{i}(t+1)\leftarrow\text{step}({\mathbf{\Phi}}^{\text{SF}}_{w,\zeta}(:,i),e_{i}\widetilde{v}_{i}(t))$

$\widehat{\alpha}^{(\mathcal{N}_{\text{out}}^{d}(j))}(t+1)\leftarrow
C_{SF}^{i}\lambda_{i}(t+1)$

$\widehat{\zeta}^{(\mathcal{N}_{\text{out}}^{d}(j))}(t+1)\leftarrow
C_{SF}^{i}\xi_{i}(t+1)$

$\widehat{\gamma}^{(\mathcal{N}_{\text{out}}^{d}(j))}(t+1)\leftarrow
K^{i}_{SF}\lambda_{i}(t+1)$

$\widehat{\theta}^{(\mathcal{N}_{\text{out}}^{d}(j))}(t)\leftarrow
K^{i}_{SF}\xi_{i}(t+1)$

In the third stage, which is demonstrated in Fig. 5, the node receives the
components pertaining to its element of the signals in (23) from other nodes a
distance at most $d$ steps away with delayed information (line 12) and sums
them to compute the $i$th element of each esignal in
$\eqref{eq:greek_letters}$. This step is described in Subroutine 3.

ininin$\vdots$$\vdots$$+$$+$$\widehat{\mathbf{v}}_{i}$$\boldsymbol{\zeta}_{i}$$\widehat{\boldsymbol{\zeta}}^{(\mathcal{N}_{\text{out}}(j_{1}))}_{i}$$\widehat{\boldsymbol{\zeta}}^{(\mathcal{N}_{\text{out}}(j_{n}))}_{i}$$\widehat{\boldsymbol{\zeta}}^{(\mathcal{N}_{\text{out}}(i))}_{i}$

Figure 5: Illustration of subroutine 3. Subroutine 3 Compute the local
elements of (24)

$\alpha_{i}(t+1)\leftarrow\widehat{w}_{i}(t+1)+\sum_{j}\widehat{\alpha}^{(\mathcal{N}_{\text{out}}^{1}(j))}_{i}(t+1)$

$\gamma_{i}(t+1)\leftarrow\sum_{j}\widehat{\gamma}^{(\mathcal{N}_{\text{out}}^{1}(j))}_{i}(t+1)$

$\zeta_{i}(t+1)\leftarrow\widehat{v}_{i}(t+1)+\sum_{j}\widehat{\zeta}^{(\mathcal{N}_{\text{out}}^{1}(j))}_{i}(t+1)$

$\theta_{i}(t)\leftarrow\sum_{j}\widehat{\theta}^{(\mathcal{N}_{\text{out}}^{1}(j))}_{i}(t)$

In the final stage (Subroutine 4) the node receives $\alpha_{j}(t+1)$ and
$\gamma_{j}(t+1)$ from its closest neighbors (line 14) and computes
$\beta_{i}(t+1)$ and $u_{i}(t)$. We conclude that the node has now received
information from nodes at most $2d+2$ steps away.

Subroutine 4 Compute $u_{i}(t)$ and $\beta_{i}(t+1)$

$\alpha_{[\mathcal{N}_{\text{in}}^{1}(i)]}(t+1)\leftarrow\text{vec}\left(\alpha_{j_{1}}(t+1),\ldots,\widehat{\alpha}_{j_{m}}(t+1)\right)$

$\gamma_{[\mathcal{N}_{\text{in}}^{1}(i)]}(t+1)\leftarrow\text{vec}\left(\gamma_{j_{1}}(t+1),\ldots,\widehat{\gamma}_{j_{m}}(t+1)\right)$
$\beta_{i}(t+1)\leftarrow-A(i,:)\alpha_{[\mathcal{N}_{\text{in}}^{1}(i)]}(t+1)\\\
-B(i,:)\gamma_{[\mathcal{N}_{\text{in}}^{1}(i)]}(t+1)-\zeta_{i}(t+1)$

$u_{i}(t)\leftarrow\gamma_{i}(t+1)+\theta_{i}(t)$

We summarize the stability properties of Algorithm 1 in the following theorem:

######  Theorem 5.

Algorithm 1 with ${\mathbf{\Phi}}^{\text{SF}}_{w}$ as in (25),
${\mathbf{\Phi}}^{\text{KF}}_{ew}$ and ${\mathbf{\Phi}}^{\text{KF}}_{ev}$ as
in Section III internally stabilizes system (1). Moreover if
${\mathbf{\Phi}}^{\text{SF}}_{w}$, ${\mathbf{\Phi}}^{\text{KF}}_{ew}$ and
${\mathbf{\Phi}}^{\text{KF}}_{ev}$ are $d$-localized, the closed-loop is at
most $2d+2$-localized.

###### Proof.

By Theorem 4 the closed-loop maps satisfy (2a) and (2b). Concatenating
$\mathbf{y}_{i}$, $\boldsymbol{\beta}_{i}$ and $\mathbf{u}_{i}$ we get
precisely the signals in Fig. 1 which is internally stable [8], we need to
show that the closed-loop is internally stable for perturbations entering in
the intermediate steps outlined in Subroutines 1–4. Note that a perturbation
entering at any of the intermediate signals can be modeled as a disturbance
entering as $\boldsymbol{\delta}_{x},\ \boldsymbol{\delta}_{y}$ or
$\boldsymbol{\delta}_{\beta}$ pre-filtered through a stable linear system.
Similarly, probing any of the internal signals can be represented as probing
$\mathbf{y},\ \mathbf{u}$ or $\boldsymbol{\beta}$ post-filtered through a
stable system. We conclude Algorithm 1 is internally stable in feedback with
System 1. Finally, as $d$-localization is closed under addition, and
composition of a $d$\- and a $k$-localized operator is at most
$d+k$-localized, (23) implies that the closed loop is at most
$2d+2$-localized. ∎

##  VI Numerical simulations

Consider a bi-directional scalar chain network parameterized by $\alpha$ and
$\rho$:

$x^{i}[t+1]=\rho(1-2\alpha)x^{i}[t]+\rho\alpha\sum_{j\in\\{i\pm
1\\}}x^{j}[t]+u^{i}[t]+w^{i}[t]$

where $\alpha$ is a coupling constant and $\rho$ is the spectral radius of the
global state-transition matrix $A$, with $\rho\geq 1$ being unstable. We first
verify the optimality of the infinite-horizon state-feedback solution given in
Section III. In this simulation, we choose the number of scalar subsystems to
be 15, $\alpha=0.6$ and $\rho=1$. For the quadratic cost matrices, we let
$Q=I$ and $R=300\cdot I$. For SLCs, we let the delayed localization parameter
be $d=3$. The result is shown in Figure 6, where the optimality of our
approach is clear. Due to the high penalty on the control actions, the
performance degradation under FIR approximation can be significant.

Figure 6: The infinite-horizon SLS solution achieves the optimal cost.

Next, we investigate the optimality gap between the suboptimal infinite-
horizon output-feedback solution proposed in this work against the FIR output-
feedback solution computed numerically with a fixed FIR horizon of 20. We let
all other parameters remain the same as before, and change the number of
subsystems to $10$ in this simulation. First, we study how the $d$ delayed
localization parameter influence the optimality gap. This is illustrated in
Figure 7. As expected, the more localized the output-feedback problem is, the
bigger the optimality gap is between the constructed solution using separation
principle and the direct FIR output-feedback solution. As the delayed
localization pattern becomes more global, the proposed output-feedback
solution becomes more optimal. When the delayed localization SLCs become non-
binding (for $d\geq 6$), we see that the proposed infinite-horizon output-
feedback solution actually becomes optimal and achieves lower cost than the
FIR solution. This is due to the separation principle of centralized LQG.

Figure 7: The proposed infinite-horizon suboptimal solution to the output-
feedback SLS problem versus the FIR output-feedback solution numerically
computed for (OF-SLS) for varying SLC delayed localization parameter $d$.

Next, we investigate how the optimality gap grows with the number of
subsystems in the network. Here we have fixed the delayed localization
parameter to be $d=3$. As can be seen in Figure 8, we observe that the
optimality gap grows apparently linearly in the number of subsystems. However,
we highlight the numerical efficiency and stability of our approach despite
the suboptimality. When the number of subsystems exceeds 12 with FIR horizon
of 20, the FIR solution solved in MATLAB using CVX renders NaN due to
numerical instability (total of 11520 variables).

Figure 8: The proposed suboptimal solution to the output-feedback SLS problem
versus the FIR output-feedback solution numerically computed for (OF-SLS) for
varying number of subsystems in the network.

## References

  * [1] L. Lessard and S. Lall, “Optimal controller synthesis for the decentralized two-player problem with output feedback,” in _2012 American Control Conference (ACC)_. IEEE, 2012, pp. 6314–6321.
  * [2] Y.-S. Wang, N. Matni, and J. C. Doyle, “Localized LQR optimal control,” in _53rd IEEE Conference on Decision and Control_. IEEE, 2014, pp. 1661–1668.
  * [3] H. R. Feyzmahdavian, A. Alam, and A. Gattami, “Optimal distributed controller design with communication delays: Application to vehicle formations,” in _2012 IEEE 51st IEEE Conference on Decision and Control (CDC)_. IEEE, 2012, pp. 2232–2237.
  * [4] M. Rotkowitz and S. Lall, “A characterization of convex problems in decentralized control,” _IEEE transactions on Automatic Control_ , vol. 50, no. 12, pp. 1984–1996, 2005.
  * [5] Y.-S. Wang, N. Matni, and J. C. Doyle, “A system-level approach to controller synthesis,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 10, pp. 4079–4093, 2019.
  * [6] L. Furieri, Y. Zheng, A. Papachristodoulou, and M. Kamgarpour, “An input–output parametrization of stabilizing controllers: Amidst youla and system level synthesis,” _IEEE Control Systems Letters_ , vol. 3, no. 4, pp. 1014–1019, 2019.
  * [7] Ş. Sabău, A. Sperilă, C. Oară, and A. Jadbabaie, “Network realization functions for optimal distributed control,” _arXiv preprint arXiv:2112.09093_ , 2021.
  * [8] J. Anderson, J. C. Doyle, S. H. Low, and N. Matni, “System level synthesis,” _Annual Reviews in Control_ , vol. 47, pp. 364–393, 2019.
  * [9] J. Yu, Y.-S. Wang, and J. Anderson, “Localized and distributed $\mathcal{H}_{2}$ state feedback control,” in _2021 American Control Conference (ACC)_. IEEE, 2021, pp. 2732–2738.
  * [10] M. W. Fisher, G. Hug, and F. Dörfler, “System level synthesis beyond finite impulse response using approximation by simple poles,” _arXiv preprint arXiv:2203.16765_ , 2022.
  * [11] Y. Zheng, L. Furieri, M. Kamgarpour, and N. Li, “System-level, input–output and new parameterizations of stabilizing controllers, and their numerical computation,” _Automatica_ , vol. 140, p. 110211, 2022.
  * [12] R. E. Kalman _et al._ , “Contributions to the theory of optimal control,” _Bol. soc. mat. mexicana_ , vol. 5, no. 2, pp. 102–119, 1960.
  * [13] W. M. Wonham, “On the separation theorem of stochastic control,” _SIAM Journal on Control_ , vol. 6, no. 2, pp. 312–326, 1968.
  * [14] Y.-S. Wang, N. Matni, and J. C. Doyle, “Separable and localized system-level synthesis for large-scale systems,” _IEEE Transactions on Automatic Control_ , vol. 63, no. 12, pp. 4234–4249, 2018.
  * [15] Y.-S. Wang, S. You, and N. Matni, “Localized distributed Kalman filters for large-scale systems,” _IFAC-PapersOnLine_ , vol. 48, no. 22, pp. 52–57, 2015\.