class disropt.algorithms.subgradient.SubgradientMethod(agent, initial_condition, enable_log=False)[source]

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

ndarray

Returns

return the sequence of estimates if enable_log=True.

class disropt.algorithms.subgradient.BlockSubgradientMethod(agent, initial_condition, **kwargs)[source]

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 the SubgradientMethod.

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.

class disropt.algorithms.gradient_tracking.GradientTracking(agent, initial_condition, enable_log=False)[source]

Bases: disropt.algorithms.algorithm.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

agent

agent to execute the algorithm

Type

Agent

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

get_result()[source]

Return the actual value of x

Returns

value of x

Return type

numpy.ndarray

iterate_run(stepsize, **kwargs)[source]

Run a single iterate of the gradient tracking algorithm

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]

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).

get_result()[source]

Return the actual value of x

Returns

value of x

Return type

numpy.ndarray

iterate_run(**kwargs)[source]

Run a single iterate of the algorithm

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.