Augmented Lagrangian Coordination (ALC)

This derivation follows Sections 6.4 and 6.6 of ^[2], Section 5 of ^[1], and Section 2 of ^[14]. Augmented Lagrangian Duality (ALD) relaxes the coupling constraints \({}^{i}_{j}c\!\left({}^{i}d,\;{}^{j}d\right)\) of the primal problem, yielding the dual problem

\[\max_{{}^{i}_{j}\lambda\;\forall\; j\in{}^{i}N,\; i\in M}\left( \begin{aligned} & \min_{{}^{i}d\;\in\;{}^{i}\mathcal{D}\;\forall\; i\in M} \quad L\!\left(\left\{{}^{i}d\right\}_{i\in M},\;\left\{{}^{i}_{j}\lambda,\;{}^{i}_{j}s\right\}_{\substack{j\in{}^{i}N \\ i\in M}}\right) \\ & \text{s.t.} \quad {}^{i}v_g\!\left({}^{i}r\right) \leq 0 \quad \forall\; i\in M, \\ & \phantom{\text{s.t.}} \quad {}^{i}v_h\!\left({}^{i}r\right) = 0 \quad \forall\; i\in M \end{aligned} \right),\]

\[L\!\left(\left\{{}^{i}d\right\}_{i\in M},\;\left\{{}^{i}_{j}\lambda,\;{}^{i}_{j}s\right\}_{\substack{j\in{}^{i}N \\ i\in M}}\right) := \sum_{i\in M} \left( {}^{i}v_f\!\left({}^{i}r\right) + \sum_{j\in{}^{i}N} {}^{i}_{j}\lambda^{T}\,{}^{i}_{j}c\!\left({}^{i}d,\;{}^{j}d\right) + \bigl\|{}^{i}_{j}s\circ{}^{i}_{j}c\!\left({}^{i}d,\;{}^{j}d\right)\bigr\|_2^2 \right).\]

Relaxing coupling constraints simplifies optimizing primal variables \({}^{i}\)\(d\) but requires finding optimal dual variables \({}^{i}_{j}\)\(c\) or \(c_c\)">\(\lambda\) (Lagrange multipliers). A sufficiently large penalty parameter \(s\) convexifies the augmented Lagrange function \(L\), improving numerical stability. The Method of Multipliers (MM) solves the dual problem by alternating between primal and dual variable updates in an outer loop.

The multiplier \(c\) or \(c_c\)">\(\lambda\) update follows a subgradient scheme (where \(\circ\) denotes element-wise multiplication):

\[\lambda^{(k+1)} \leftarrow \lambda^{(k)} + 2 \cdot s^{(k)} \circ s^{(k)} \circ c^{(k+1)}\]

The penalty parameters are adapted based on inconsistency improvement:

\[s^{(k+1)} \leftarrow \begin{cases} \beta \cdot s^{(k)} & \text{if } \left|c^{(k+1)}\right| > \gamma \cdot \left|c^{(k)}\right| \\ s^{(k)} & \text{otherwise} \end{cases}\]

The penalty parameter increases by factor \(\beta\) only when inconsistency reduction is insufficient (less than factor \(\gamma\)), avoiding unnecessarily large values while ensuring convergence.

These updates require centralized computation, making them unsuitable for distributed optimization. However, the primal update is separable into \(\left|M\right|\) independent optimization problems — one per design variable \({}^{i}\)\(d\) — except for the quadratic penalty term \(\left\|{}^{i}_{j}s\circ{}^{i}_{j}c\right\|_{2}^{2}\) in \(L\).

ALC approximately solves the primal problem via FPI schemes such as Gauss–Seidel (sequential, using the latest data) or Jacobi (parallel). This distributed primal update forms an inner loop with termination criteria as defined in ^{[1, 2, 13]}.

The resulting ALC algorithm is shown in Algorithm 1 below. The dual update may also be distributed. The variant of ^[1, 2] uses the subgradient method above. In this implementation, each subsystem \(i\) maintains multipliers and weights for both \({}^{i}_{j}\)\(c\) and \({}^{j}_{i}\)\(c\). For convergence analysis, see ^[1, 2].

All symbols are defined in the Nomenclature.

Algorithm 1 Augmented Lagrangian Coordination (ALC)

Require: hyperparameters $\gamma$, $\beta$

Require: initial \({}^{j}_{i}H\!\left({}^{j}r\right),\; {}^{i}_{j}h,\; {}^{j}_{i}z\) in interface storage \(i \leftrightarrow j \;\; \forall\; j \in {}^{i}N,\; i \in M\)

Require: initial \({}^{i}_{j}\lambda^{(0)},\; {}^{i}_{j}s^{(0)} \;\; \forall\; j \in {}^{i}N,\; i \in M\)

 

\(k \leftarrow 0\) ▷ initialize outerloop iterator

repeat

\(l \leftarrow 0\) ▷ initialize innerloop iterator

repeat ▷ decentralized Primal Update approximation

for every \(i \in M\) in sequence or parallel do

Copy \({}^{j}_{i}H\!\left({}^{j}r\right),\; {}^{i}_{j}h,\; {}^{j}_{i}z\) from interface storage \(i \leftrightarrow j \;\; \forall\; j \in {}^{i}N\)

\[\begin{aligned} {}^{i}d^{(k,\,l+1)} \leftarrow{} & \argmin_{{}^{i}d \;\in\; {}^{i}\mathcal{D}} \;\; {}^{i}v_f\!\left({}^{i}r\right) \\ & + \sum_{j \in {}^{i}N} \left( \left({}^{i}_{j}\lambda^{(k)}\right)^{T} \begin{bmatrix} {}^{i}_{j}H\!\left({}^{i}r\right) - {}^{i}_{j}h \\ {}^{i}_{j}S_{z}\,{}^{i}d - {}^{j}_{i}z \end{bmatrix} + \left\|{}^{i}_{j}s^{(k)} \circ \begin{bmatrix} {}^{i}_{j}H\!\left({}^{i}r\right) - {}^{i}_{j}h \\ {}^{i}_{j}S_{z}\,{}^{i}d - {}^{j}_{i}z \end{bmatrix} \right\|_{2}^{2} \right. \\ & \left. \quad\quad + \left({}^{j}_{i}\lambda^{(k)}\right)^{T} \begin{bmatrix} {}^{j}_{i}H\!\left({}^{j}r\right) - {}^{j}_{i}S_{h}\,{}^{i}d \\ {}^{j}_{i}z - {}^{i}_{j}S_{z}\,{}^{i}d \end{bmatrix} + \left\|{}^{j}_{i}s^{(k)} \circ \begin{bmatrix} {}^{j}_{i}H\!\left({}^{j}r\right) - {}^{j}_{i}S_{h}\,{}^{i}d \\ {}^{j}_{i}z - {}^{i}_{j}S_{z}\,{}^{i}d \end{bmatrix} \right\|_{2}^{2} \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. \end{aligned}\]

Copy \({}^{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 innerloop convergence criterion (e.g., ^{[1, 2, 13]})

\(l \leftarrow l + 1\)

until innerloop convergence criterion is met

 

\({}^{i}d^{(k+1)} \leftarrow {}^{i}d^{(k,\,l)} \;\forall\; i \in M\)

 

for every \(i \in M\) in parallel do ▷ decentralized Dual and Penalty Update

Copy \({}^{j}_{i}H\!\left({}^{j}r\right),\; {}^{i}_{j}h,\; {}^{j}_{i}z\) from interface storage \(i \leftrightarrow j \;\; \forall\; j \in {}^{i}N\)

\[\begin{aligned} {}^{i}_{j}c^{(k+1)} &\leftarrow \begin{bmatrix} {}^{i}_{j}H\!\left({}^{i}r\right) - {}^{i}_{j}h \\ {}^{i}_{j}S_{z}\,{}^{i}d^{(k+1)} - {}^{j}_{i}z \end{bmatrix}, \\[0.5em] {}^{j}_{i}c^{(k+1)} &\leftarrow \begin{bmatrix} {}^{j}_{i}H\!\left({}^{j}r\right) - {}^{j}_{i}S_{h}\,{}^{i}d^{(k+1)} \\ {}^{j}_{i}z - {}^{i}_{j}S_{z}\,{}^{i}d^{(k+1)} \end{bmatrix} \end{aligned}\]

\[\begin{aligned} {}^{i}_{j}\lambda^{(k+1)} &\leftarrow \operatorname{DualUpdate}\!\left( {}^{i}_{j}\lambda^{(k)},\; {}^{i}_{j}s^{(k)},\; {}^{i}_{j}c^{(k+1)} \right) \quad \forall\; j \in {}^{i}N \\ {}^{j}_{i}\lambda^{(k+1)} &\leftarrow \operatorname{DualUpdate}\!\left( {}^{j}_{i}\lambda^{(k)},\; {}^{j}_{i}s^{(k)},\; {}^{j}_{i}c^{(k+1)} \right) \quad \forall\; j \in {}^{i}N \\[0.5em] {}^{i}_{j}s^{(k+1)} &\leftarrow \operatorname{PenaltyUpdate}\!\left( \beta,\; \gamma,\; {}^{i}_{j}s^{(k)},\; {}^{i}_{j}c^{(k+1)},\; {}^{i}_{j}c^{(k)} \right) \quad \forall\; j \in {}^{i}N \\ {}^{j}_{i}s^{(k+1)} &\leftarrow \operatorname{PenaltyUpdate}\!\left( \beta,\; \gamma,\; {}^{j}_{i}s^{(k)},\; {}^{j}_{i}c^{(k+1)},\; {}^{j}_{i}c^{(k)} \right) \quad \forall\; j \in {}^{i}N \end{aligned}\]

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}\)