29  Large scale systems

Author

Affiliation

Aditya Mahajan

McGill University

Keywords

LQR, mean-field control

Summary

The Riccati update for LQ systems has a complexity $\mathcal{O}(d_x^3)$, which $d_x$ is the size of the state space. So even computing the otimal gains in a large-scale system is computationally challenging. In this section we show that under certain regularity and symmetry assumptions, the optimal solution of a large-scale system can be computed with low complexity.

29.1 Mean-field control

Consider a system consisting of $N$ subsystems, indexed by the set $\mathcal{N}:=\{1,\dots ,N\}$. Each subsystem $i\in \mathcal{N}$ has a state $x_t^i\in {\mathbb{R}}^{d_x}$ and a control input $u_t^i\in {\mathbb{R}}^{d_u}$. The dynamics of each subsystem are given as $$\begin{array}{}\text{(1)}& x_{t+1}^i=A{x}_t^i+B{u}_t^i+D{\overline{x}}_t+E{\overline{u}}_t+w_t^i\end{array}$$ where $$\begin{array}{}\text{(2)}& {\overline{x}}_t:=\frac{1}{N}\sum _{i\in \mathcal{N}}{x}_t^i\text{and}{\overline{u}}_t:=\frac{1}{N}\sum _{i\in \mathcal{N}}{u}_t^i\end{array}$$ are the emperical mean-field of the state and control, respectively and $A$, $B$, $D$, $E$ are matrices of appropriate dimensions. The noise processes $\{w_t^i{\}}_{t\ge 1}$, $i\in \mathcal{N}$ are correlated across subsystem but are assumed to be independent across time.

We use $x{x}_t:=(x_t^1,\dots ,x_t^N)$ and $u{u}_t:=(u_t^1,\dots ,u_t^N)$ to denote the global state and control of the system. The system incurs a per-step cost given by $$\begin{array}{}\text{(3)}& c(x{x}_t,u{u}_t)={\overline{x}}_t^{⊺}\overline{Q}{\overline{x}}_t+{\overline{u}}_t^{⊺}\overline{R}{\overline{u}}_t+\frac{1}{N}\sum _{i\in \mathcal{N}}[(x_t^i{)}^{⊺}Q{x}_t^i+(u_t^i{)}^{⊺}R{u}_t^i]\end{array}$$ and a terminal cost $$\begin{array}{}\text{(4)}& c_T(x{x}_T)={\overline{x}}_T^{⊺}{\overline{Q}}_T{\overline{x}}_T+\frac{1}{N}\sum _{i\in \mathcal{N}}(x_T^i{)}^{⊺}{Q}_T{x}_T^i\end{array}$$

We are interested in identifying policies $g=(g_1,\dots ,g_{T-1})$ where $u{u}_t=g_t(x{x}_t)$ to minimize $$\begin{array}{}\text{(5)}& J(g)={\mathbb{E}}^g[\sum _{t=1}^{T-1}c(x{x}_t,u{u}_t)+c_T(x{x}_T)]\end{array}$$

Weakly coupled dynamics and cost

Note that the subsystems are weakly coupled in the dynamics and cost. A naive solution using by solving a single Riccati equation has a complexity of $\mathcal{O}(d_x^3{N}^3)$, which scales cubically in the number of agents.

29.1.1 State space decomposition

We now present a decomposition method to simplify the above optimization problem. Note that $\text{(1)}$ implies that $$\begin{array}{}\text{(6)}& {\overline{x}}_t=(A+D){\overline{x}}_t+(B+E){\overline{u}}_t+{\overline{w}}_t\end{array}$$ where ${\overline{w}}_t=(\sum _{i\in \mathcal{N}}{w}_t^i)/N$. Define $${\breve{x}}_t^i=x_t^i-{\overline{x}}_t\text{and}{\breve{u}}_t^i=u_t^i-{\overline{u}}_t.$$ Then, subtracting $\text{(6)}$ from $\text{(1)}$, we get $$\begin{array}{}\text{(7)}& {\breve{x}}_t^i=A{\breve{x}}_t^i+B{\breve{u}}_t^i+{\breve{w}}_t^i\end{array}$$ where ${\breve{w}}_t^i=w_t^i-{\overline{w}}_t$.

We can think of ${\overline{x}}_t$ as the “center of mass” of the system and ${\breve{x}}_t^i$ to be the relative coordinates of subsystem $i$ wrt the center of mass. Building on this intuition, we make the following simple observation, which may be viewed as an analog of the parallel axis theorem in physics.

Lemma 29.1 We have the following:

1. ${\displaystyle \frac{1}{N}\sum _{i\in \mathcal{N}}(x_t^i{)}^{⊺}Q{x}_t^i={\overline{x}}_t^{⊺}Q{\overline{x}}_t+\frac{1}{N}\sum _{i\in \mathcal{N}}({\breve{x}}_t^i{)}^{⊺}Q{\breve{x}}_t^i}$.
2. ${\displaystyle \frac{1}{N}\sum _{i\in \mathcal{N}}(u_t^i{)}^{⊺}Q{u}_t^i={\overline{u}}_t^{⊺}Q{\overline{u}}_t+\frac{1}{N}\sum _{i\in \mathcal{N}}({\breve{u}}_t^i{)}^{⊺}Q{\breve{u}}_t^i}$.

Proof

The proof follows from the observation that $\sum _{i\in \mathcal{N}}{\breve{x}}_t^i=0$ and elementary algebra.

An immediate implication of Lemma 29.1 is that the per-step cost can be decomposed as follows: $$\begin{array}{}\text{(8)}& c(x{x}_t,u{u}_t)=\overline{c}({\overline{x}}_t,{\overline{u}}_t)+\frac{1}{N}\sum _{i\in \mathcal{N}}{\breve{c}}^i({\breve{x}}_t^i,{\breve{u}}_t^i)\end{array}$$ where $$\begin{array}{rl}\overline{c}({\overline{x}}_t,{\overline{u}}_t)& ={\overline{x}}_t^{⊺}(Q+\overline{Q}){\overline{x}}_t+{\overline{u}}_t^{⊺}(R+\overline{R}){\overline{u}}_t,\\ {\breve{c}}^i({\breve{x}}_t^i,{\breve{u}}_t^i)& =\frac{1}{N}\sum _{i\in \mathcal{N}}[({\breve{x}}_t^i{)}^{⊺}Q{\breve{x}}_t^i+({\breve{u}}_t^i{)}^{⊺}Q{\breve{u}}_t^i].\end{array}$$ A similar decomposition also holds for the terminal cost $c_t(x{x}_t,u{u}_t)$.

Thus, the original system is equivalent to $N+1$ coupled subsystems:

• a mean-field subsystem with state ${\overline{x}}_t$, control input ${\overline{u}}_t$, and per-step cost $\overline{c}({\overline{x}}_t,{\overline{u}}_t)$.
• $N$ auxiliary subsytems, where subsystem $i\in \mathcal{N}$ has state ${\breve{x}}_t^i$, control input ${\breve{u}}_t^i$, and per-step cost $\breve{c}({\breve{x}}_t^i,{\breve{u}}_t^i)$.

Note that the only coupling between the subsystems is through the noise. Therefore, by the argument presented in Exercise 28.3, the optimal control strategy is of the following form.

Proposition 29.1 The optimal control policy for the mean-field control system described above is given by $$u_t=-{\overline{K}}_t{\overline{x}}_t+{\breve{K}}_t(x_t^i-{\overline{x}}_t)$$ where

• ${\overline{K}}_{1:T-1}={\mathrm{LQR}}_T(A+D,B+E,Q+\overline{Q},R+\overline{R};Q_T+{\overline{Q}}_T)$
• ${\breve{K}}_{1:T-1}={\mathrm{LQR}}_T(A,B,Q,R;Q_T)$.

Significance of the result

The above result is significant, both for synthesis and implementation.

For synthesis, rather than solving one Riccati equation with state dimension $nN$, we need to solve two Riccati equations with dimension $d_x$. Thus, the complexity of computing the optimal controller gains does not depend on the number $N$ of subsystems.

For implementation, each subsystem does not need access to the global state $x{x}_t$; instead it just needs access to the mean-field ${\overline{x}}_t$ in addition to its local state $x_t^i$.

29.2 Network coupled subsystems

Notes

The results for mean-field control are adapted from Arabneydi and Mahajan (2016). The discussion above is restricted to the simplest setting of homogenous subsystems. Generalization to hetrogeneous subsystems and infinite horizon settings are also presented in Arabneydi and Mahajan (2016). A similar result for $N\to \mathrm{\infty }$ is also presented in Elliott et al. (2013).

The results for network coupled subsystems are adapted from Gao and Mahajan (2022).

Arabneydi, J. and Mahajan, A. 2016. Linear quadratic mean field teams: Optimal and approximately optimal decentralized solutions. Available at: https://arxiv.org/abs/1609.00056v2.

Elliott, R., Li, X., and Ni, Y.-H. 2013. Discrete time mean-field stochastic linear-quadratic optimal control problems. Automatica 49, 11, 3222–3233. DOI: 10.1016/j.automatica.2013.08.017.

Gao, S. and Mahajan, A. 2022. Optimal control of network-coupled subsystems: Spectral decomposition and low-dimensional solutions. IEEE Transactions on Control of Network Systems 9, 2, 657–669. DOI: 10.1109/tcns.2021.3124259.