(Sub)gradient based Algorithms¶
Distributed projected (Sub)gradient Method¶

class
disropt.algorithms.subgradient.
SubgradientMethod
(agent, initial_condition, enable_log=False)[source]¶ Bases:
disropt.algorithms.consensus.Consensus
Distributed projected (sub)gradient method.
From the perspective of agent \(i\) the algorithm works as follows. For \(k=0,1,\dots\)
\[ \begin{align}\begin{aligned} y_i^{k} &= \sum_{j=1}^N w_{ij} x_j^k\\x_i^{k+1} &= \Pi_{X}[y_i^k  \alpha^k \tilde{\nabla} f_i(y_i^k)]\end{aligned}\end{align} \]where \(x_i,y_i\in\mathbb{R}^n\), \(X\subseteq\mathbb{R}^n\), \(\alpha^k\) is a positive stepsize, \(w_{ij}\) denotes the weight assigned by agent \(i\) to agent \(j\), \(\Pi_X[]\) denotes the projection operator over the set \(X\) and \(\tilde{\nabla} f_i(y_i^k)\in\partial f_i(y_i^k)\) a (sub)gradient of \(f_i\) computed at \(y_i^k\). The weight matrix \(W=[w_{ij}]_{i,j=1}^N\) should be doubly stochastic.
The algorithm, as written above, was originally presented in [NeOz09]. Many other variants and extension has been proposed, allowing for stochastic objective functions, timevarying graphs, local stepsize sequences. All these variant can be implemented through the
SubgradientMethod
class.
run
(iterations=1000, stepsize=0.001, verbose=False)[source]¶ Run the algorithm for a given number of iterations
 Parameters
iterations (
int
) – Number of iterations. Defaults to 1000.stepsize (
Union
[float
,Callable
]) – If a float is given as input, the stepsize is constant. If a function is given, it must take an iteration k as input and output the corresponding stepsize.. Defaults to 0.1.verbose (
bool
) – If True print some information during the evolution of the algorithm. Defaults to False.
 Raises
TypeError – The number of iterations must be an int
TypeError – The stepsize must be a float or a callable
ValueError – Only sets (children of AstractSet) with explicit projections are currently supported
ValueError – Only one constraint per time is currently supported
 Return type
ndarray
 Returns
return the sequence of estimates if enable_log=True.

Randomized Block (Sub)gradient Method¶

class
disropt.algorithms.subgradient.
BlockSubgradientMethod
(agent, initial_condition, **kwargs)[source]¶ Bases:
disropt.algorithms.consensus.BlockConsensus
Distributed block subgradient method. This is a special instance of the Block Proximal Method in [FaNo19]
At each iteration, the agent can update its local estimate or not at each iteration according to a certain probability (awakening_probability). From the perspective of agent \(i\) the algorithm works as follows. At iteration \(k\) if the agent is awake, it selects a random block \(\ell_i^k\) of its local solution and updates
\[\begin{split}\begin{align} y_i^k &= \sum_{j\in\mathcal{N}_i} w_{ij} x_{j\mid i}^k \\ x_{i,\ell}^{k+1} &= \begin{cases} \Pi_{X_\ell}\left[y_i^k  \alpha_i^k [\tilde{\nabla} f_i(y_i^k)]_{\ell}\right] & \text{if } \ell = \ell_i^k \\ x_{i,\ell}^{k} & \text{otherwise} \end{cases} \end{align}\end{split}\]then it broadcasts \(x_{i,\ell_i^k}^{k+1}\) to its outneighbors. Otherwise (if the agent is not awake) \(x_{i}^{k+1}=x_i^k\). Here \(\mathcal{N}_i\) is the current set of inneighbors and \(x_{j\mid i},j\in\mathcal{N}_i\) is the local copy of \(x_j\) available at node \(i\) and \(x_{i,\ell}\) denotes the \(\ell\)th block of \(x_i\). The weight matrix \(W=[w_{ij}]_{i,j=1}^N\) should be doubly stochastic.
Notice that if there is only one block and awakening_probability=1 the
BlockSubgradientMethod
reduces to theSubgradientMethod
.
run
(iterations=1000, stepsize=0.1, verbose=False)[source]¶ Run the algorithm for a given number of iterations
 Parameters
iterations (
int
) – Number of iterations. Defaults to 1000.stepsize (
Union
[float
,Callable
]) – If a float is given as input, the stepsize is constant. If a function is given, it must take an iteration k as input and output the corresponding stepsize.. Defaults to 0.1.verbose (
bool
) – If True print some information during the evolution of the algorithm. Defaults to False.
 Raises
TypeError – The number of iterations must be an int
TypeError – The stepsize must be a float or a callable
ValueError – Only sets (children of AstractSet) with explicit projections are currently supported
ValueError – Only one constraint per time is currently supported
 Return type
ndarray
 Returns
return the sequence of estimates if enable_log=True.

Distributed Gradient Tracking¶

class
disropt.algorithms.gradient_tracking.
GradientTracking
(agent, initial_condition, enable_log=False)[source]¶ Bases:
disropt.algorithms.algorithm.Algorithm
Gradient Tracking Algorithm […]_
From the perspective of agent \(i\) the algorithm works as follows. For \(k=0,1,\dots\)
\[\begin{split}x_i^{k+1} & = \sum_{j=1}^N w_{ij} x_j^k  \alpha d_i^k \\ d_i^{k+1} & = \sum_{j=1}^N w_{ij} d_j^k  [ \nabla f_i (x_i^{k+1})  \nabla f_i (x_i^k)]\end{split}\]where \(x_i\in\mathbb{R}^n\) and \(d_i\in\mathbb{R}^n\). The weight matrix \(W=[w_{ij}]\) must be doublystochastic. Extensions to other class of weight matrices \(W\) are not currently supported.
 Parameters
agent (Agent) – agent to execute the algorithm
initial_condition (numpy.ndarray) – initial condition for \(x_i\)
enable_log (bool) – True for enabling log

x0
¶ initial condition
 Type
numpy.ndarray

x
¶ current value of the local solution
 Type
numpy.ndarray

d
¶ current value of the local tracker
 Type
numpy.ndarray

shape
¶ shape of the variable
 Type
tuple

x_neigh
¶ dictionary containing the local solution of the (in)neighbors
 Type
dict

d_neigh
¶ dictionary containing the local tracker of the (in)neighbors
 Type
dict

enable_log
¶ True for enabling log
 Type
bool

run
(iterations=1000, stepsize=0.1, verbose=False)[source]¶ Run the gradient tracking algorithm for a given number of iterations
 Parameters
iterations (
int
) – Number of iterations. Defaults to 1000.stepsize (
Union
[float
,Callable
]) – If a float is given as input, the stepsize is constant. Default is 0.01.verbose (
bool
) – If True print some information during the evolution of the algorithm. Defaults to False.
 Raises
TypeError – The number of iterations must be an int
TypeError – The stepsize must be a float
 Return type
ndarray
 Returns
return the sequence of estimates if enable_log=True.
Distributed Gradient Tracking (over directed, unbalanced graphs)¶

class
disropt.algorithms.gradient_tracking.
DirectedGradientTracking
(agent, initial_condition, enable_log=False)[source]¶ Bases:
disropt.algorithms.consensus.PushSumConsensus
Gradient Tracking Algorithm [XiKh18]
From the perspective of agent \(i\) the algorithm works as follows. For \(k=0,1,\dots\)
\[\begin{split}x_i^{k+1} & = \sum_{j=1}^N a_{ij} x_j^k  \alpha y_i^k \\ y_i^{k+1} & = \sum_{j=1}^N b_{ij} (y_j^k  [ \nabla f_j (x_j^{k+1})  \nabla f_j (x_j^k)])\end{split}\]where \(x_i\in\mathbb{R}^n\) and \(y_i\in\mathbb{R}^n\). The weight matrix \(A=[a_{ij}]\) must be rowstochastic, while \(B=[b_{ij}]\) must be columnstochastic. The underlying graph can be directed (and unbalanced).
References
 NeOz09
Nedic, Angelia; Asuman Ozdaglar: Distributed subgradient methods for multiagent optimization: IEEE Transactions on Automatic Control 54.1 (2009): 48.
 FaNo19
Farina, Francesco, and Notarstefano, Giuseppe. Randomized Block Proximal Methods for Distributed Stochastic BigData Optimization. arXiv preprint arXiv:1905.04214 (2019).
 XiKh18
Xin, Ran, and Usman A. Khan: A linear algorithm for optimization over directed graphs with geometric convergence. IEEE Control Systems Letters 2.3 (2018): 315320.