(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

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

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

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]

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

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.