# Distributed optimization set-ups¶

Distributed optimization problems usually arising in applications usually enjoy a proper structure in their mathematical formulation. In disropt, three different optimization set-ups are available. As for their solution, see the Algorithms page for a list of all the implemented distributed algorithms (classified by optimization set-up to which they apply).

## Cost-coupled set-up¶

In this optimization set-up, the cost function is expressed as the sum of cost functions $$f_i$$ and all of them depend on a common optimization variable $$x$$. Formally, the set-up is

$\begin{split}\min_{x} \: & \: \sum_{i=1}^N f_i(x) \\ \text{subject to} \: & \: x \in X,\end{split}$

where $$x \in \mathbb{R}^d$$ and $$X \subseteq \mathbb{R}^d$$. The global constraint set $$X$$ is common to all agents, while $$f_i : \mathbb{R}^d \rightarrow \mathbb{R}$$ is assumed to be known by agent $$i$$ only, for all $$i\in \{1, \ldots, N\}$$.

In some applications, the constraint set $$X$$ can be expressed as the intersection of local constraint sets, i.e.,

$X = \bigcap_{i=1}^N X_i$

where each $$X_i \subseteq \mathbb{R}^d$$ is meant to be known by agent $$i$$ only, for all $$i\in \{1, \ldots, N\}$$.

The goal for distributed algorithms for the cost-coupled set-up is that all agent estimates are eventually consensual to an optimal solution $$x^\star$$ of the problem.

## Common cost set-up¶

In this optimization set-up, there is a unique cost function $$f$$ that depends on a common optimization variable $$x$$, and the optimization variable must further satisfy local constraints. Formally, the set-up is

$\begin{split}\min_{x} \: & \: f(x) \\ \text{subject to} \: & \: x \in \bigcap_{i=1}^N X_i,\end{split}$

where $$x \in \mathbb{R}^d$$ and each $$X_i \subseteq \mathbb{R}^d$$. The cost function $$f$$ is assumed to be known by all the agents, while each set $$X_i$$ is assumed to be known by agent $$i$$ only, for all $$i\in \{1, \ldots, N\}$$.

The goal for distributed algorithms for the common-cost set-up is that all agent estimates are eventually consensual to an optimal solution $$x^\star$$ of the problem.

## Constraint-coupled set-up¶

In this optimization set-up, the cost function is expressed as the sum of local cost functions $$f_i$$ that depend on a local optimization variable $$x_i$$. The variables must satisfy local constraints (involving only each optimization variable $$x_i$$) and global coupling constraints (involving all the optimization variables). Formally, the set-up is

$\begin{split}\min_{x_1,\ldots,x_N} \: & \: \sum_{i=1}^N f_i(x_i) \\ \text{subject to} \: & \: x_i \in X_i, \hspace{1cm} i \in \{1, \ldots, N\} \\ & \: \sum_{i=1}^N g_i (x_i) \le 0,\end{split}$

where each $$x_i \in \mathbb{R}^{d_i}$$, $$X_i \subseteq \mathbb{R}^{d_i}$$, $$f_i : \mathbb{R}^{d_i} \rightarrow \mathbb{R}$$ and $$g_i : \mathbb{R}^{d_i} \rightarrow \mathbb{R}^S$$ for all $$i \in \{1, \ldots, N\}$$. Here the symbol $$\le$$ is also used to denote component-wise inequality for vectors. Therefore, the optimization variable consists of the stack of all $$x_i$$, namely the vector $$(x_1,\ldots,x_N)$$. All the quantities with the index $$i$$ are assumed to be known by agent $$i$$ only, for all $$i\in \{1, \ldots, N\}$$. The function $$g_i$$, with values in $$\mathbb{R}^S$$, is used to express the $$i$$-th contribution to $$S$$ coupling constraints among all the variables.

The goal for distributed algorithms for the constraint-coupled set-up is that each agent estimate is asymptotically equal to its portion $$x_i^\star \in X_i$$ of an optimal solution $$(x_1^\star, \ldots, x_N^\star)$$ of the problem.