Sensitivity Based Distributed Programming (SBDP)
SBDP [19, 10] augments each subsystem's objective with a first-order sensitivity correction that approximates how changes in \({}^{i}\)\(d\) affect the Lagrangians of neighboring subsystems. This section applies the framework to the primal problem.
Each coupling constraint is assigned to exactly one subsystem. Here \({}^{i}_{j}\)\(c\) belongs to subsystem \(i\), simplifying the correction term. The constraint \({}^{i}_{j}c\!\left({}^{i}d,\;{}^{j}d\right)\) is kept in subsystem \(i\)'s problem with \({}^{j}d\) fixed at its previous iterate for decoupling [10, 19]. The full procedure is given in Algorithm 3.
The total Lagrangian reads
\[\begin{aligned}
L
:={} &
\sum_{i\in M}
\Biggl(
{}^{i}v_f\!\left({}^{i}r\right)
+
{}^{i}\kappa_g^{T}\,
{}^{i}v_g\!\left({}^{i}r\right)
+
{}^{i}\kappa_h^{T}\,
{}^{i}v_h\!\left({}^{i}r\right)
+
{}^{i}\kappa_d^{T}\,
{}^{i}v_D\!\left({}^{i}d\right)
\\
& \quad\quad\;\; +
\sum_{j\in{}^{i}N}
{}^{i}_{j}\lambda^{T}\,
{}^{i}_{j}c\!\left({}^{i}d,\;{}^{j}d\right)
\Biggr),
\end{aligned}\]
which partitions into subsystem-local Lagrangians
\[L
=
\sum_{i\in M}
{}^{i}L\!\left({}^{i}d,\;\left\{{}^{j}d\right\}_{j\in{}^{i}N}\right),\]
with
\[\begin{aligned}
{}^{i}L\!\left({}^{i}d,\;\left\{{}^{j}d\right\}_{j\in{}^{i}N}\right)
:={} &
{}^{i}v_f\!\left({}^{i}r\right)
+
{}^{i}\kappa_g^{T}\,
{}^{i}v_g\!\left({}^{i}r\right)
+
{}^{i}\kappa_h^{T}\,
{}^{i}v_h\!\left({}^{i}r\right)
+
{}^{i}\kappa_d^{T}\,
{}^{i}v_D\!\left({}^{i}d\right)
\\
&+
\sum_{j\in{}^{i}N}
{}^{i}_{j}\lambda^{T}\,
{}^{i}_{j}c\!\left({}^{i}d,\;{}^{j}d\right).
\end{aligned}\]
The sensitivity correction for subsystem \(i\) is the derivative of \({}^{j}L\) with respect to \({}^{i}d\) at iterate \(k\). Since \({}^{j}v_f\), \({}^{j}v_g\), \({}^{j}v_h\), \({}^{j}v_D\) depend only on \({}^{j}d\), only the coupling term \({}^{j}_{i}\)\(c\) contributes to \(\nabla_{{}^{i}d}{}^{j}L^{(k)}\):
\[\begin{aligned}
\nabla_{{}^{i}d}{}^{j}L^{(k)}
={} &
\nabla_{{}^{i}d}^{T}\,
{}^{j}_{i}c\!\left({}^{j}d,\;{}^{i}d\right)\,
{}^{j}_{i}\lambda^{(k)}
\\
={} &
\begin{bmatrix}
-{}^{j}_{i}S_{h} \\
-{}^{i}_{j}S_{z}
\end{bmatrix}^{T}
\begin{bmatrix}
{}^{j}_{i}\lambda_{h}^{(k)} \\
{}^{j}_{i}\lambda_{z}^{(k)}
\end{bmatrix}
\end{aligned}\]
For convergence analysis and necessary assumptions, see [19, 10]. After the original SBDP publication [10], modifications improving convergence were proposed, yielding SBDP+ [19].
All symbols are defined in the Nomenclature.
Algorithm 3 Sensitivity Based Distributed Programming (
SBDP)
Require: hyperparameter \(\epsilon_k\)
Require: initial \({}^{j}_{i}\lambda,\; {}^{i}_{j}h,\; {}^{j}_{i}z\) in interface storage \(i \leftrightarrow j \;\; \forall\; j \in {}^{i}N,\; i \in M\)
\(k \leftarrow 0\)
repeat
for every \(i \in M\) in parallel do
Copy \({}^{j}_{i}\lambda,\; {}^{j}_{i}H\!\left({}^{j}r\right),\; {}^{i}_{j}h,\; {}^{j}_{i}z\) from interface storage \(i \leftrightarrow j \;\; \forall\; j \in {}^{i}N\)
Determine \(\nabla_{{}^{i}d}{}^{j}L^{(k)} \;\; \forall\; j \in {}^{i}N\)
\[\begin{aligned}
{}^{i}d^{(k+1)} \leftarrow{} & \argmin_{{}^{i}d \;\in\; {}^{i}\mathcal{D}} \;\;
{}^{i}v_f\!\left({}^{i}r\right)
+ \sum_{j \in {}^{i}N} \left(
\bigl(\nabla_{{}^{i}d}{}^{j}L^{(k)}\bigr)^{T}
\left({}^{i}d - {}^{i}d^{(k)}\right)
\right) \\
& \text{s.t.} \;\; {}^{i}v_g\!\left({}^{i}r\right) \leq 0, \\
& \phantom{\text{s.t.}} \;\; {}^{i}v_h\!\left({}^{i}r\right) = 0, \\
& \phantom{\text{s.t.}} \;\;
\begin{bmatrix}
{}^{i}_{j}H\!\left({}^{i}r\right) - {}^{i}_{j}h \\
{}^{i}_{j}S_{z}\,{}^{i}d - {}^{j}_{i}z
\end{bmatrix} = 0
\quad | \;
{}^{i}_{j}\lambda
\quad \forall\; j \in {}^{i}N.
\end{aligned}\]
Determine \({}^{i}_{j}\lambda \;\; \forall\; j \in {}^{i}N\)
Copy \({}^{i}_{j}\lambda,\; {}^{i}_{j}H\!\left({}^{i}r\right),\; {}^{j}_{i}h,\; {}^{i}_{j}z\) to interface storage \(i \leftrightarrow j \;\; \forall\; j \in {}^{i}N\)
end for
Compute outerloop convergence criterion (e.g., [1, 2])
\(k \leftarrow k + 1\)
until outerloop convergence criterion is met
return \(\left\{{}^{i}d^{(k)}\right\}_{i \in M}\)