(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, time-varying 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
- 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 out-neighbors. Otherwise (if the agent is not awake) \(x_{i}^{k+1}=x_i^k\). Here \(\mathcal{N}_i\) is the current set of in-neighbors 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
- 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 doubly-stochastic. 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
- x¶
current value of the local solution
- Type
- d¶
current value of the local tracker
- Type
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 row-stochastic, while \(B=[b_{ij}]\) must be column-stochastic. The underlying graph can be directed (and unbalanced).
References
- NeOz09
Nedic, Angelia; Asuman Ozdaglar: Distributed subgradient methods for multi-agent optimization: IEEE Transactions on Automatic Control 54.1 (2009): 48.
- FaNo19
Farina, Francesco, and Notarstefano, Giuseppe. Randomized Block Proximal Methods for Distributed Stochastic Big-Data 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): 315-320.