decent_bench.distributed_algorithms

class decent_bench.distributed_algorithms.DstAlgorithm

Bases: ABC

Distributed algorithm - agents collaborate to solve an optimization problem using peer-to-peer communication.

abstract property name: str

Name of the algorithm.

abstractmethod run(network: Network) → None

Run the algorithm.

Parameters:

network – provides agents, neighbors etc.

class decent_bench.distributed_algorithms.DGD(iterations: int, step_size: float, name: str = 'DGD')

Bases: DstAlgorithm

Distributed gradient descent characterized by the update step below.

\[\mathbf{x}_{i, k+1} = (\sum_{j} \mathbf{W}_{ij} \mathbf{x}_{j,k}) - \rho \nabla f_i(\mathbf{x}_{i,k})\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, j is a neighbor of i or i itself, \(\mathbf{W}_{ij}\) is the metropolis weight between agent i and j, \(\rho\) is the step size, and \(f_i\) is agent i’s local cost function.

iterations: int

step_size: float

name: str = 'DGD'

run(network: Network) → None

Run the algorithm with all \(\mathbf{x}\) initialized using numpy.zeros().

Parameters:

network – provides agents, neighbors etc.

class decent_bench.distributed_algorithms.GT1(iterations: int, step_size: float, name: str = 'GT1')

Bases: DstAlgorithm

Gradient tracking algorithm characterized by the update step below.

\[\mathbf{y}_{i, k+1} = \mathbf{x}_{i, k} - \rho \nabla f_i(\mathbf{x}_{i,k})\]

\[\mathbf{x}_{i, k+1} = \mathbf{y}_{i, k+1} - \mathbf{y}_{i, k} + \sum_j \mathbf{W}_{ij} \mathbf{x}_{j,k}\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, \(\rho\) is the step size, \(f_i\) is agent i’s local cost function, j is a neighbor of i or i itself, and \(\mathbf{W}_{ij}\) is the metropolis weight between agent i and j.

iterations: int

step_size: float

name: str = 'GT1'

run(network: Network) → None

Run the algorithm with all \(\mathbf{x}\) and \(\mathbf{y}\) initialized using numpy.zeros().

Parameters:

network – provides agents, neighbors etc.

class decent_bench.distributed_algorithms.GT2(iterations: int, step_size: float, name: str = 'GT2')

Bases: DstAlgorithm

Gradient tracking algorithm characterized by the update step below.

\[\mathbf{y}_{i, k+1} = \mathbf{x}_{i, k} - \rho \nabla f_i(\mathbf{x}_{i,k})\]

\[\mathbf{x}_{i, k+1} = \sum_j \frac{1}{2} (\mathbf{I} + \mathbf{W})_{ij} (\mathbf{x}_{j,k} + \mathbf{y}_{j, k+1} - \mathbf{y}_{j, k})\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, \(\rho\) is the step size, \(f_i\) is agent i’s local cost function, j is a neighbor of i or i itself, and \(\mathbf{W}_{ij}\) is the metropolis weight between agent i and j.

iterations: int

step_size: float

name: str = 'GT2'

run(network: Network) → None

Run the algorithm with all \(\mathbf{x}\) and \(\mathbf{y}\) initialized using numpy.zeros().

Parameters:

network – provides agents, neighbors etc.

class decent_bench.distributed_algorithms.ADMM(iterations: int, rho: float, alpha: float, name: str = 'ADMM')

Bases: DstAlgorithm

Distributed Alternating Direction Method of Multipliers characterized by the update step below.

\[\mathbf{x}_{i, k+1} = \operatorname{prox}_{\frac{1}{\rho N_i} f_i} \left(\sum_j \mathbf{Z}_{ij, k} \frac{1}{\rho N_i} \right)\]

\[\mathbf{Z}_{ij, k+1} = (1-\alpha) \mathbf{Z}_{ij, k} - \alpha (\mathbf{Z}_{ji, k} - 2 \rho \mathbf{x}_{j, k+1})\]

where \(\mathbf{x}_{i, k}\) is agent i’s local optimization variable at iteration k, \(\operatorname{prox}\) is the proximal operator described in CostFunction.proximal(), \(\rho > 0\) is the Lagrangian penalty parameter, \(N_i\) is the number of neighbors of i, \(f_i\) is i’s local cost function, j is a neighbor of i, and \(\alpha \in (0, 1)\) is the relaxation parameter.

iterations: int

rho: float

alpha: float

name: str = 'ADMM'

run(network: Network) → None

Run the algorithm with \(\mathbf{Z}\) initialized using numpy.zeros().

Parameters:

network – provides agents, neighbors etc.