Multi-Grid Schemes for Multi-Scale Coordination of Energy Systems

To introduce notation, we begin by considering a convex QP with two variable partitions (i.e., $\mathcal{K}=\{1,2\}$). To simplify the presentation, we do not include internal partition constraints and focus on coupling constraints across partitions. Under these assumptions, we have the following lifted optimization problem:

	$\displaystyle\min_{{z}_{1},{z}_{2}}\quad$	$\displaystyle\frac{1}{2}\begin{bmatrix}{z}_{1}\\ {z}_{2}\end{bmatrix}^{T}\begin{bmatrix}Q_{1}&\\ &Q_{2}\end{bmatrix}\begin{bmatrix}{z}_{1}\\ {z}_{2}\end{bmatrix}-\begin{bmatrix}c_{1}\\ c_{2}\end{bmatrix}^{T}\begin{bmatrix}{z}_{1}\\ {z}_{2}\end{bmatrix}$		(4a)
	s.t.	$\displaystyle\underbrace{\begin{bmatrix}\Pi_{11}&\Pi_{12}\\ \Pi_{21}&\Pi_{22}\end{bmatrix}}_{\Pi}\underbrace{\begin{bmatrix}{z}_{1}\\ {z}_{2}\end{bmatrix}}_{z}=\begin{bmatrix}0\\ 0\end{bmatrix}\quad\begin{array}[]{c}(\lambda_{1})\\ (\lambda_{2})\end{array}$		(4d)

Here, the matrices $\Pi_{11},\Pi_{12},\Pi_{21},\Pi_{22}$ capture coupling between the variables $z_{1}$ and $z_{2}$. We highlight that, in general, $\Pi_{12}\neq\Pi_{21}$ (the coupling between partitions is not symmetric). The matrices $Q_{1}$ and $Q_{2}$ are positive definite and we assume that $\Pi_{11}$ and $\Pi_{22}$ have full row rank and that the entire coupling matrix $\Pi$ has full row rank. By positive definiteness of $Q_{1}$ and $Q_{2}$ and the full rank assumption of $\Pi$ we have that the feasible set is non-empty and the primal and dual solution of (4) is unique. The coupling between partition variables is two-directional (given by the structure of the coupling matrix $\Pi$). This structure is found in 1-D linear networks. When the coupling is only one-directional, as is the case of temporal coupling, we have that $\Pi_{12}=0$ and thus $\Pi$ is block lower triangular, indicating that the primal variables only propagate forward in time. We will see, however, that backward propagation of information also exists, but in the space of the dual variables.

The first-order KKT conditions of (4) are given by the linear system:

$$\begin{bmatrix}Q_{1}&{\Pi_{11}}^{T}&&{\Pi_{21}}^{T}\\ \Pi_{11}&&\Pi_{12}&\\ &{\Pi_{12}}^{T}&Q_{2}&{\Pi_{22}}^{T}\\ \Pi_{21}&&\Pi_{22}&\end{bmatrix}\begin{bmatrix}{z}_{1}\\ {\lambda}_{1}\\ {z}_{2}\\ {\lambda}_{2}\end{bmatrix}=\begin{bmatrix}c_{1}\\ 0\\ c_{2}\\ 0\end{bmatrix}$$

(5)

To avoid solving this system in a centralized manner we use a decentralized GS scheme with coordination update index $\ell\in\mathbb{Z}_{+}$. The scheme has the form:

	$\displaystyle\begin{bmatrix}Q_{1}&{\Pi_{11}}^{T}\\ {\Pi_{11}}\end{bmatrix}\begin{bmatrix}{z}_{1}^{\ell+1}\\ {\lambda}_{1}^{\ell+1}\end{bmatrix}$	$\displaystyle=\begin{bmatrix}c_{1}\\ 0\end{bmatrix}-\begin{bmatrix}&{\Pi_{21}}^{T}\\ {\Pi_{12}}&\end{bmatrix}\begin{bmatrix}{z}_{2}^{\ell}\\ {\lambda}_{2}^{\ell}\end{bmatrix}$		(6a)
	$\displaystyle\begin{bmatrix}Q_{2}&{\Pi_{22}}^{T}\\ {\Pi_{22}}\end{bmatrix}\begin{bmatrix}{z}_{2}^{\ell+1}\\ {\lambda}_{2}^{\ell+1}\end{bmatrix}$	$\displaystyle=\begin{bmatrix}c_{2}\\ 0\end{bmatrix}-\begin{bmatrix}&{\Pi_{12}}^{T}\\ {\Pi_{21}}&\end{bmatrix}\begin{bmatrix}{z}_{1}^{\ell+1}\\ {\lambda}_{1}^{\ell+1}\end{bmatrix}$		(6b)

This scheme requires an initial guess for the variables of the second partition $({z}_{2},{\lambda}_{2})$ that is used to update $(z_{1},\lambda_{1})$ and we then proceed to update the variables of the second partition. Note, however, that we have picked this coordination order arbitrarily (lexicographic order). In particular, one can start with an initial guess of the first partition to update the second partition and then update the first partition (reverse lexicographic order). This scheme has the form:

	$\displaystyle\begin{bmatrix}Q_{2}&{\Pi_{22}}^{T}\\ {\Pi_{22}}\end{bmatrix}\begin{bmatrix}{z}_{2}^{\ell+1}\\ {\lambda}_{2}^{\ell+1}\end{bmatrix}$	$\displaystyle=\begin{bmatrix}c_{2}\\ 0\end{bmatrix}-\begin{bmatrix}&{\Pi_{12}}^{T}\\ {\Pi_{21}}&\end{bmatrix}\begin{bmatrix}{z}_{1}^{\ell}\\ {\lambda}_{1}^{\ell}\end{bmatrix}$		(7a)
	$\displaystyle\begin{bmatrix}Q_{1}&{\Pi_{11}}^{T}\\ {\Pi_{11}}\end{bmatrix}\begin{bmatrix}{z}_{1}^{\ell+1}\\ {\lambda}_{1}^{\ell+1}\end{bmatrix}$	$\displaystyle=\begin{bmatrix}c_{1}\\ 0\end{bmatrix}-\begin{bmatrix}&{\Pi_{21}}^{T}\\ {\Pi_{12}}&\end{bmatrix}\begin{bmatrix}{z}_{2}^{\ell+1}\\ {\lambda}_{2}^{\ell+1}\end{bmatrix}$		(7b)

We will see that the coordination order affects the convergence properties of the GS scheme. In problems with many partitions, we will see that a large number of coordination orders are possible. Moreover, we will see that coordination orders can be designed to enable sophisticated parallel and asynchronous implementations. A key observation is that the linear systems (6) in the GS scheme are the first-order KKT conditions of the following partition problems $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, respectively:

	$\displaystyle{z}_{1}^{\ell+1}=\mathop{\textrm{argmin}}_{{z}_{1}}$	$\displaystyle\quad\frac{1}{2}z_{1}^{T}Q_{1}{z}_{1}-z_{1}^{T}\left({c_{1}}-\Pi_{21}^{T}{\lambda}_{2}^{\ell}\right)$		(8a)
	s.t.	$\displaystyle\quad\Pi_{11}{z}_{1}+\Pi_{12}{z}_{2}^{\ell}=0\quad(\lambda_{1})$		(8b)
	$\displaystyle{z}_{2}^{\ell+1}=\mathop{\textrm{argmin}}_{{z}_{2}}$	$\displaystyle\quad\frac{1}{2}z_{2}^{T}Q_{2}{z}_{2}-z_{2}^{T}\left({c_{2}}-\Pi_{12}^{T}{\lambda}_{1}^{\ell+1}\right)$		(8c)
	s.t.	$\displaystyle\quad\Pi_{22}{z}_{2}+\Pi_{21}{z}_{1}^{\ell+1}=0\quad(\lambda_{2})$		(8d)

The relevance of this observation is that one can implement the GS scheme by directly solving optimization problems, as opposed to performing intrusive linear algebra calculations zavalamultigrid . This has practical benefits, as one can use algebraic modeling languages and handle sophisticated problem formulations. This also reveals that both primal and dual variables are communicated between partitions. Primal information enters in the coupling constraints. The dual variables enter as cost terms in the objective and highlights the fact that dual variables can be interpreted as prices of the primal variable information exchanged between partitions.

We now seek to establish conditions guaranteeing convergence of this simplified GS scheme. To do so, we define the following matrices and vectors:

		$\displaystyle A_{1}:=\begin{bmatrix}Q_{1}&{\Pi_{11}}^{T}\\ {\Pi_{11}}\end{bmatrix},\;{x}_{1}^{\ell}:=\begin{bmatrix}{z}_{1}^{\ell}\\ {\lambda}_{1}^{\ell}\end{bmatrix},\;{b}_{1}:=\begin{bmatrix}c_{1}\\ 0\end{bmatrix},\;B_{12}:=\begin{bmatrix}&-{\Pi_{21}}^{T}\\ -{\Pi_{12}}&\end{bmatrix}$		(9a)
		$\displaystyle A_{2}:=\begin{bmatrix}Q_{2}&{\Pi_{22}}^{T}\\ {\Pi_{22}}\end{bmatrix},\;{x}_{2}^{\ell}:=\begin{bmatrix}{z}_{2}^{\ell}\\ {\lambda}_{2}^{\ell}\end{bmatrix},\;{b}_{2}:=\begin{bmatrix}c_{2}\\ 0\end{bmatrix},\;B_{21}:=\begin{bmatrix}&-{\Pi_{12}}^{T}\\ -{\Pi_{21}}&\end{bmatrix}.$		(9b)

The partition matrices $A_{1}$, $A_{2}$ are non-singular because the matrices $Q_{1}$, $Q_{2}$ are positive definite and $\Pi_{11}$, $\Pi_{22}$ have full row rank. Nonsingularity of $A_{1}$ and $A_{2}$ implies that the partition optimization subproblems $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ have a unique solution for any values of the primal and dual variables of the neighboring partition. We can now express $({x}_{1}^{\ell+1},{x}_{2}^{\ell+1})$ in terms of $({x}_{1}^{\ell},{x}_{2}^{\ell})$ to obtain a recursion of the form:

$$\displaystyle\begin{bmatrix}A_{1}&&\\ -B_{21}&A_{2}\end{bmatrix}\begin{bmatrix}{x}_{1}^{\ell+1}\\ {x}_{2}^{\ell+1}\end{bmatrix}=\begin{bmatrix}\quad&B_{12}\\ \quad&\end{bmatrix}\begin{bmatrix}{x}_{1}^{\ell}\\ {x}_{2}^{\ell}\end{bmatrix}+\begin{bmatrix}{b}_{1}\\ {b}_{2}\end{bmatrix}.$$

(10)

We can write this system in compact form by defining:

$${w}^{\ell}:=\begin{bmatrix}{x}_{1}^{\ell}\\ {x}_{2}^{\ell}\end{bmatrix},\quad S:=\begin{bmatrix}A_{1}&&\\ -B_{21}&A_{2}\end{bmatrix}^{-1}\begin{bmatrix}\quad&B_{12}\\ \quad&\end{bmatrix},\quad{r}:=\begin{bmatrix}A_{1}&&\\ -B_{21}&A_{2}\end{bmatrix}^{-1}\begin{bmatrix}{b}_{1}\\ {b}_{2}\end{bmatrix}.$$

(11)

The solution of the $\ell$-th update step of (6) can be represented as:

	$\displaystyle{w}^{\ell+1}$	$\displaystyle=S{w}^{\ell}+{r}.$		(12a)
		$\displaystyle=S^{\ell}{w}^{0}+\left(I+S+\cdots+S^{\ell-1}\right){r}.$		(12b)

The solution of the QP (4) (i.e., the solution of the KKT system (5)) solves the implicit system ${w}=S{w}+{r}$, which can also be expressed as $(I-S)w=r$ or $w=(I-S)^{-1}r$. Consequently, we note that the eigenvalues of matrix $S$ play a key role in the convergence of the GS scheme (8). We discuss this in more detail in the following section.

We now extend the previous analysis to a more general QP setting with an arbitrary number of partitions. Here, we seek to illustrate how to perform lifting in a general case where coupling is implicit in the model and how to derive a GS scheme to solve such a problem. Our discussion is based on the following convex QP:

$$\min_{{z}}\quad\frac{1}{2}{z}^{T}Q{z}-{c}^{T}{z}$$

(13)

Here ${z}=(z(1),z(2),\cdots,z(N))\in\mathbb{R}^{N}$ are the optimization variables, $Q\in\mathbb{R}^{N\times N}$ is a positive definite matrix, and $c\in\mathbb{R}^{N}$ is the cost vector. For simplicity (and without loss of generality) we assume that $n_{z}=1$ (there is only one variable per node). We let $Q_{ij}$ represent the $(i,j)$-th component of matrix $Q$ and we let $\mathcal{N}=\{1,2,\cdots,N\}$ be the variable indices (in this case also the node indices). Problem (13) has a unique solution because the matrix $Q$ is positive definite.

We focus our analysis on the QP (13) because we note that equality constraints $\bar{A}z+\bar{B}d=0$ in (1) (with $\bar{A}^{T}=[A^{T}\,\Pi^{T}]$ and $\bar{B}^{T}=[B^{T}\,0]$) can be eliminated by using a null-space projection procedure. To see how this can be achieved we note that, if $A$ has full row rank, we can always construct a matrix $Z\in\mathbb{R}^{N\times\tilde{N}}$ whose columns span the null-space of $\bar{A}$ (i.e., $\bar{A}Z\tilde{z}=0$ for any $\tilde{z}\in\mathbb{R}^{\tilde{N}}$) and with $\tilde{N}<N$. Similarly, we can construct a matrix $Y\in\mathbb{R}^{N\times(N-\tilde{N})}$ whose columns span the range-space of $\bar{A}^{T}$ (i.e., $Y\tilde{y}\in\textrm{Range}(\bar{A}^{T})$ for any $\tilde{y}\in\mathbb{R}^{N-\tilde{N}}$). We can express any $z\in\mathbb{R}^{N}$ as $z=Z\tilde{z}+Y\tilde{y}$. We thus have that $\bar{A}z=\bar{A}Y\tilde{y}$ for all $\tilde{z}$ and thus $\tilde{y}=-(\bar{A}Y)^{-1}\bar{B}d$ and $z=-Y(AY)^{-1}\bar{B}d+Z\tilde{z}$ satisfies $\bar{A}z=-\bar{B}d$ for any $\tilde{z}$. With this, we can express the quadratic objective as $\frac{1}{2}{z}^{T}Q{z}-{c}^{T}{z}$ as $\frac{1}{2}\tilde{z}^{T}Z^{T}QZ\tilde{z}-{c}^{T}Z\tilde{z}-(Y(AY)^{-1}\overline{B}d)^{T}QZ\tilde{z}+\kappa$, where $\kappa$ is a constant. We thus obtain a QP of the same form as (13) but with matrix $Q\leftarrow Z^{T}QZ$, reduced cost $c\leftarrow Z^{T}c+Z^{T}QY(AY)^{-1}\overline{B}d$, and variable vector $z\leftarrow\tilde{z}$. We highlight that this reduction procedure does not need to be applied in a practical implementation but we only use it to justify that the formulation (13) is general.

We thus have that the variables $z$ in (13) are coupled implicitly via the matrix $Q$ and we seek to express this problem in the lifted form. We proceed to partition the set $\mathcal{N}$ into a set of partitions $\mathcal{K}=\{1,..,K\}$ to give the partition sets $\mathcal{N}_{1},\mathcal{N}_{2},\cdots,\mathcal{N}_{K}\subseteq\mathcal{N}$ satisfying $\mathcal{N}=\mathcal{N}_{1}\cup\mathcal{N}_{2}\cup\cdots\cup\mathcal{N}_{K}$ and $\mathcal{N}_{k}\cap\mathcal{N}_{k^{\prime}}=\emptyset\quad\text{for all }k,k^{\prime}\in\mathcal{K}\text{ and }k\neq k^{\prime}$. Coupling between variables arises when $Q_{ij}\neq 0$ for $i\in\mathcal{N}_{k}$, $j\in\mathcal{N}_{k}^{\prime}$, and $k\neq k^{\prime}$. We perform lifting by defining index sets:

$\displaystyle\underline{\mathcal{N}}_{k}:=\{j\in\mathcal{N}\setminus\mathcal{N}_{k}\mid\exists\,i\in\mathcal{N}_{k}\text{ s.t. }Q_{ij}\neq 0\},\quad\overline{\mathcal{N}}_{k}:=\mathcal{N}_{k}\cup\underline{\mathcal{N}}_{k}$

(14)

The set $\underline{\mathcal{N}}_{k}$ includes all the coupled variables in the partition set $\mathcal{N}_{k}$ that are not in partition $k$. The set $\overline{\mathcal{N}}_{k}$ includes all variables in partition $\mathcal{N}_{k}$ and its coupled variables. These definitions allow us to express problem (13) as:

$$\min_{{z}}\quad\frac{1}{2}\sum_{k\in\mathcal{K}}\sum_{i\in\mathcal{N}_{k}}\sum_{j\in\overline{\mathcal{N}}_{k}}Q_{ij}z(i)z(j)-\sum_{k\in\mathcal{K}}\sum_{i\in\mathcal{N}_{k}}c_{i}z(i).$$

(15)

To induce lifting, we introduce a new set of variables $\{{z}_{1},{z}_{2},\cdots,{z}_{K}\}$ defined as:

$${z}_{k}:=\begin{bmatrix}z(k_{1})\\ \vdots\\ z(k_{N_{k}})\end{bmatrix},\quad\underline{{z}}_{k}=\begin{bmatrix}z(k_{N_{k}+1})\\ \vdots\\ z(k_{N_{k}+\underline{N}_{k}})\end{bmatrix},\quad\overline{{z}}_{k}:=\begin{bmatrix}{z}_{k}\\ \underline{{z}}_{k}\end{bmatrix}$$

(16)

where $\mathcal{N}_{k}=\{k_{1},k_{2},\cdots,k_{N_{k}}\}$, $\underline{\mathcal{N}}_{k}=\{k_{N_{k}+1},k_{N_{k}+2},\cdots,k_{N_{k}+\underline{N}_{k}}\}$, $N_{k}$ is the number of variables in partition $\mathcal{N}_{k}$, and $\underline{N}_{k}$ is the number of variables coupled to partition $k$. With this, we can express problem (15) in the following lifted form:

	$\displaystyle\min_{{z}}\quad$	$\displaystyle\sum_{k\in\mathcal{K}}\frac{1}{2}{\overline{{z}}_{k}}^{T}\overline{Q}_{k}\overline{{z}}_{k}-{\overline{{c}}_{k}}^{T}\overline{{z}}_{k}.$		(17a)
	s.t.	$\displaystyle{\Pi}_{kk}\overline{{z}}_{k}+\sum_{k^{\prime}\in\mathcal{K}\setminus\{k\}}{\Pi}_{kk^{\prime}}\overline{{z}}_{k^{\prime}}=0,\quad k\in\mathcal{K}.$		(17b)

Here, $\overline{Q}_{k}\in\mathbb{R}^{(N_{k}+\underline{N}_{k})\times(N_{k}+\underline{N}_{k})}$ and $\overline{c}_{k}\in\mathbb{R}^{(N_{k}+\underline{N}_{k})}$ are given by:

	$\displaystyle(\overline{Q}_{k})_{ij}=\begin{cases}Q_{k_{i}k_{j}},&\text{for }k_{i},k_{j}\in\mathcal{N}_{k}\\ \frac{1}{2}Q_{k_{i}k_{j}},&\text{for }k_{i}\in\mathcal{N}_{k}\text{ and }k_{j}\notin\mathcal{N}_{k}\\ \frac{1}{2}Q_{k_{i}k_{j}},&\text{for }k_{i}\notin\mathcal{N}_{k}\text{ and }k_{j}\in\mathcal{N}_{k}\\ 0,\quad&\text{otherwise}\end{cases},\qquad(\overline{{c}}_{k})_{i}=\begin{cases}c_{k_{i}},&\text{for }k_{i}\in\mathcal{N}_{k}\\ 0,&\text{for }k_{i}\notin\mathcal{N}_{k}\end{cases}$		(18a)

The coefficient matrices $\Pi_{kk}\in\mathbb{R}^{\underline{N}_{k}\times(N_{k}+\underline{N}_{k})}$ are given by:

$$\Pi_{kk}=\begin{bmatrix}{e_{N_{k}+1}}^{T}\\ \vdots\\ {e_{N_{k}+\underline{N}_{k}}}^{T}\end{bmatrix},$$

(19)

where $e_{i}\in\mathbb{R}^{N_{k}+\underline{N}_{k}}$ are elementary column vectors. Note that for $Q_{ij}\neq 0$, $i\in\mathcal{N}_{k}$, $j\in\mathcal{N}_{k^{\prime}}$, and $k\neq k^{\prime}$, $Q_{ij}$ can be included in the objective function of either partition $k$, partition $k^{\prime}$, or both. In the lifting scheme shown in (18a), we assume that these terms are equally divided and included in each partition. However, this approach is arbitrary, and other lifting schemes are possible. In other words, we can manipulate the lifting scheme to set the partition sets to satisfy either $j\in\underline{\mathcal{N}}_{k}$ or $j\notin\underline{\mathcal{N}}_{k}$. Interestingly, one can show that the solution of the lifted problem is unique and is the same as that of problem (13). The proof of this assertion is intricate and will not be discussed here due to the lack of space. To simplify the notation we express the lifted variables $\bar{z}_{k}$, matrices $\bar{Q}_{k}$, and cost vectors $\bar{c}_{k}$ in (17) simply as $z_{k},Q_{k},c_{k}$.

The primal-dual solution of (17) can be obtained by solving the KKT conditions:

$$\begin{bmatrix}Q_{1}&\Pi_{11}^{T}&&\Pi_{21}^{T}&&\cdots&&\Pi_{K1}^{T}\\ \Pi_{11}&&\Pi_{12}&&\cdots&&\Pi_{1K}&\\ &\Pi_{12}^{T}&Q_{2}&\Pi_{22}^{T}&&&&\vdots\\ \Pi_{21}&&\Pi_{22}&&&&\vdots&\\ &\vdots&&&\ddots&&&\vdots\\ \vdots&&&&&\ddots&\vdots&\\ &\Pi_{1K}^{T}&&\cdots&&\cdots&Q_{K}&\Pi_{KK}^{T}\\ \Pi_{K1}&&\cdots&&\cdots&&\Pi_{KK}&\\ \end{bmatrix}\begin{bmatrix}z_{1}\\ \lambda_{1}\\ z_{2}\\ \lambda_{2}\\ \vdots\\ z_{K}\\ \lambda_{K}\end{bmatrix}=\begin{bmatrix}c_{1}\\ {0}\\ c_{2}\\ {0}\\ \vdots\\ c_{K}\\ {0}\end{bmatrix}$$

(20)

By exploiting the structure of this system, we can derive a GS scheme of the form:

$$\begin{bmatrix}Q_{k}&\Pi_{kk}^{T}\\ \Pi_{kk}&\end{bmatrix}\begin{bmatrix}z_{k}^{\ell+1}\\ \lambda_{k}^{\ell+1}\end{bmatrix}=\begin{bmatrix}c_{k}\\ {0}\end{bmatrix}-\sum_{k^{\prime}=1}^{k-1}\begin{bmatrix}0&\Pi_{k^{\prime}k}^{T}\\ \Pi_{kk^{\prime}}&0\end{bmatrix}\begin{bmatrix}z_{k^{\prime}}^{\ell+1}\\ \lambda_{k^{\prime}}^{\ell+1}\end{bmatrix}-\sum_{k^{\prime}=k+1}^{K}\begin{bmatrix}0&\Pi_{k^{\prime}k}^{T}\\ \Pi_{kk^{\prime}}&0\end{bmatrix}\begin{bmatrix}z_{k^{\prime}}^{\ell}\\ \lambda_{k^{\prime}}^{\ell}\end{bmatrix}.$$

(21)

Here, we have used a lexicographic coordination order. We note that the solution of the linear system (21) solves the optimization problem:

	$\displaystyle z_{k}^{\ell+1}=\mathop{\textrm{argmin}}_{z_{k}}$	$\displaystyle\quad\frac{1}{2}{z_{k}}^{T}Q_{k}z_{k}-{{{z}}}_{k}^{T}\left({{{c}_{k}}}-\sum^{k-1}_{k^{\prime}=1}\Pi_{k^{\prime}k}^{T}\lambda_{k^{\prime}}^{\ell+1}-\sum^{K}_{k^{\prime}=k+1}\Pi_{k^{\prime}k}^{T}\lambda_{k^{\prime}}^{\ell}\right)$		(22a)
	s.t.	$\displaystyle\quad{\Pi}_{kk}z_{k}+\sum_{k^{\prime}=1}^{k-1}{\Pi}_{kk^{\prime}}z_{k^{\prime}}^{\ell+1}+\sum_{k^{\prime}=k+1}^{K}{\Pi}_{kk^{\prime}}z_{k^{\prime}}^{\ell}=0\quad(\lambda_{k}).$		(22b)

From this structure, we can see how the primal and dual variables propagate forward and backward relative to the partition $k$, due to the inherent block triangular nature of the GS scheme. We now seek to establish a condition that guarantees convergence of the GS scheme in this more general setting. To do so, we define:

$$A_{k}:=\begin{bmatrix}Q_{k}&{\Pi_{kk}}^{T}\\ \Pi_{kk}&\end{bmatrix},\quad{x}_{k}^{\ell}:=\begin{bmatrix}{z}_{k}^{\ell}\\ {\lambda}_{k}^{\ell}\end{bmatrix},\quad{b}_{k}:=\begin{bmatrix}c_{k}\\ {0}\end{bmatrix},\quad B_{kk^{\prime}}:=\begin{bmatrix}&-{\Pi_{k^{\prime}k}}^{T}\\ -\Pi_{kk^{\prime}}&\end{bmatrix}.$$

(23)

By using (23), we can express (21) as:

$$A_{k}{x}_{k}^{\ell+1}={b}_{k}+\sum^{k-1}_{k^{\prime}=1}B_{kk^{\prime}}{x}_{k^{\prime}}^{\ell+1}+\sum^{K}_{k^{\prime}=k+1}B_{kk^{\prime}}{x}_{k^{\prime}}^{\ell}.$$

(24)

This can be expressed in matrix form as:

$$\displaystyle\begin{bmatrix}A_{1}&&&\\ -B_{21}&A_{2}&&\\ \vdots&\ddots&\ddots&\\ -B_{K1}&\cdots&-B_{KK-1}&A_{K}\end{bmatrix}\begin{bmatrix}{x}_{1}^{\ell+1}\\ {x}_{2}^{\ell+1}\\ \vdots\\ {x}_{K}^{\ell+1}\end{bmatrix}=\begin{bmatrix}\quad&B_{12}&\cdots&B_{1K}\\ \quad&&\ddots&\vdots\\ \quad&&&B_{K-1K}\\ \quad\end{bmatrix}\begin{bmatrix}{x}_{1}^{\ell}\\ {x}_{2}^{\ell}\\ \vdots\\ {x}_{K}^{\ell}\end{bmatrix}+\begin{bmatrix}{b}_{1}\\ {b}_{2}\\ \vdots\\ {b}_{K}\end{bmatrix}.$$

(25)

We can see that the partition matrices $A_{k}$ are nonsingular by inspecting the block structure of $Q_{k}$. In particular, by the definition of $Q_{k}$ in (18a) (we denoted $Q_{k}$ as $\overline{Q}_{k}$ here) and the definition of $\Pi_{kk}$ in (19), we can express $A_{k}$ as:

$$A_{k}=\begin{bmatrix}\hat{Q}_{k}&\underline{Q}_{k}^{T}&\\ {\underline{Q}_{k}}&&I\\ &I&\end{bmatrix}$$

(26)

where each components of $\hat{Q}_{k}\in\mathbb{R}^{N_{k}\times N_{k}}$ and $\underline{Q}_{k}\in\mathbb{R}^{\underline{N}_{k}\times N_{k}}$ are defined in (18a). Since $Q$ is positive definite, $\hat{Q}_{k}$ is also positive definite. Noting that $\hat{Q}_{k}$ is nonsingular, we can see that the columns of $A_{k}$ are linearly independent and thus $A_{k}$ is nonsingular as well. This implies that the block lower triangular matrix on the left-hand side of (25) is also nonsingular. To simplify notation we define:

	$\displaystyle{w}^{\ell}$	$\displaystyle:=\begin{bmatrix}{x}_{1}^{\ell}\\ {x}_{2}^{\ell}\\ \vdots\\ {x}_{K}^{\ell}\end{bmatrix},\quad{r}:=\begin{bmatrix}A_{1}&&&\\ -B_{21}&A_{2}&&\\ \vdots&\ddots&\ddots&\\ -B_{K1}&\cdots&-B_{KK-1}&A_{K}\end{bmatrix}^{-1}\begin{bmatrix}{b}_{1}\\ {b}_{2}\\ \vdots\\ {b}_{K}\end{bmatrix}$		(27a)
	$\displaystyle S$	$\displaystyle:=\begin{bmatrix}A_{1}&&&\\ -B_{21}&A_{2}&&\\ \vdots&\ddots&\ddots&\\ -B_{K1}&\cdots&-B_{KK-1}&A_{K}\end{bmatrix}^{-1}\begin{bmatrix}\quad&B_{12}&\cdots&B_{1K}\\ \quad&&\ddots&\vdots\\ \quad&&&B_{K-1K}\\ \quad\end{bmatrix}.$		(27b)

We express (25) by using the compact form ${w}^{\ell+1}=S{w}^{\ell}+{r}$ or $w^{\ell+1}=S^{\ell}{w}^{0}+\left(I+S+\cdots+S^{\ell-1}\right){r}$. The solution of (20) satisfies ${{w}}=S{w}+{r}$. This implies that the solution of the lifted problem also solves the original problem (13). We now formally establish the following convergence result for the GS scheme.

Convergence is achieved without any assumptions on the initial guess ${w}^{0}$. The error between the solution of problem (13) and the solution of the $\ell$-th coordination update of the GS scheme (21) (i.e., $(I-S)^{-1}{r}-{w}^{\ell}$) is given by ${\epsilon}^{\ell}=S^{\ell}\left((I-S)^{-1}{r}-{w}^{0}\right)$. We will call $\|\epsilon^{\ell}\|$ the error of the $\ell$-th coordination step. If we express the initial error term as $\|\epsilon^{0}\|$, we can write $\|\epsilon^{\ell}\|=\|S^{\ell}\epsilon^{0}\|$. Moreover, if we define $\rho(S)=\lambda_{max}(S)$ then, for any $\delta>0$, there exists $\kappa>0$ such that the bound $\|S^{\ell}\|\leq\kappa|\rho(S)+\delta|^{\ell}$ holds for all $\ell$ and where $\|S\|$ is a matrix norm of $S$. Using this inequality we can establish that $\|\epsilon^{\ell}\|\leq\kappa|\rho(S)+\delta|^{\ell}\|\epsilon^{0}\|$. Since we can choose $\delta$ to be arbitrarily small, we can see that the decaying rate of the error is $O\left(\rho(S)^{\ell}\right)$. Although the error decays exponentially we note that, if $\rho(S)$ is close to one, convergence can be slow and thus having a good initial guess ${w}^{0}$ is essential. We also note that $\rho(S)$ is tightly related to the topology of the coupling between partitions, indicating that the partition structure contributes to the convergence rate.

We highlight that the GS concepts discussed here focus on problems with no inequality constraints. In practice, however, GS schemes can also be applied to such problems by using projected GS schemes zavalamultigrid ; borzi2005multigrid ; zavala2010real .

In the lexicographic coordination order proposed in (21), we use the update sequence $k=1,2,\cdots,K$. We note that the order affects the structure of the matrix $\Sigma$ and thus convergence can be affected as well. To see this, consider a new order given by the sequence $\sigma(1),\sigma(2),\cdots,\sigma(K)$ where $\sigma:\{1,2,\cdots,K\}\rightarrow\{1,2,\cdots,K\}$ is a bijective mapping. We can use this mapping to rearrange the partition variables as:

$$[z_{1},\lambda_{1},z_{2},\lambda_{2},\dots z_{K},\lambda_{K}]\rightarrow[z_{\sigma(1)},\lambda_{\sigma(1)},z_{\sigma(2)},\lambda_{\sigma(2)},\dots z_{\sigma(K)},\lambda_{\sigma(K)}].$$

(28)

This gives the reordered matrix:

$$\displaystyle S=\begin{bmatrix}A_{\sigma(1)}&&&\\ -B_{\sigma(2)\sigma(1)}&A_{\sigma(2)}&&\\ \vdots&\ddots&\ddots&\\ -B_{\sigma(K)\sigma(1)}&\cdots&-B_{\sigma(K)\sigma(K-1)}&A_{\sigma(K)}\end{bmatrix}^{-1}\begin{bmatrix}\quad&B_{\sigma(1)\sigma(2)}&\cdots&B_{\sigma(1)\sigma(K)}\\ \quad&&\ddots&\vdots\\ \quad&&&B_{\sigma(K-1)\sigma(K)}\\ \quad\end{bmatrix}$$

(29)

Importantly, the change in update order is not necessarily a similarity transformation of matrix $S$ and thus the eigenvalues will be altered. The GS scheme converges as long as eigenvalues of the reordered matrix $S$ have magnitude less than one but the convergence rate will be affected. Interestingly, GS schemes are highly flexible and allow for a large number of update orders. For instance, in some cases one can derive ordering sequences that enable parallelization. As an example, the 1-D spatial problem has a special structure with $B_{kk^{\prime}}$=0 for any $(k,k^{\prime})$ such that $|k-k^{\prime}|\geq 2$. The GS scheme becomes:

$\displaystyle A_{k}{x}_{k}^{\ell+1}$

$\displaystyle={b}_{k}+B_{kk-1}{x}_{k-1}^{\ell+1}+B_{kk+1}{x}_{k+1}^{\ell}$

(30)

Instead, we consider the following ordering $\sigma(i)=2i-1$ for $1\leq i\leq\frac{K}{2}$ and $\sigma(i)=2i-K$ for $\frac{K}{2}+1\leq i\leq K$. Here we assume that the number of partitions is even. This is a called a red-black ordering and is widely popular in the solution of PDEs. By changing the index using $\sigma(\cdot)$, we can express (30) as: