Otro enfoque es este: Si asumes que cada índice $i \in \{1, \ldots , N\}$ es un nodo de un gráfico conectado, puedes definir variables locales $y_i$ para cada uno $i \in \{1, \ldots , N\}$ y luego hacer cumplir la obligación $y_i=y_j$ siempre que $i$ y $j$ son vecinos. Si quieres, puedes hacer lo mismo para el $x_i$ variables: Definir $x_i^{(k)}$ como el nodo $i$ estimación de $x_k$ . El problema resultante es:
Minimizar:
$$ \sum_ {i=1}^N f_i(x_i^{(i)}, y_i) $$
Sujeto a:
$$ y_i = y_j \: \mbox { whenever $ i $ and $ j $ are neighbors} $$
$$ \sum_ {k=1}^N x_i^{k} = y_i \: \mbox { for all $ i $} $$
$$ x_i^{k} = x_j^{k} \: \forall k, \mbox { whenever $ i $ and $ j $ are neighbors} $$
$$ y_i \in \mathcal {Y}, x_i^k \in \mathcal {X}_k $$
Este es un enfoque de fuerza bruta que introduce muchas variables, puedes reducir algunas de las variables si utilizas un árbol (un gráfico conectado "minimalista"). Hice esto en el siguiente artículo, que puede ser de interés: "Computación distribuida y segura de programas convexos sobre una red de procesadores conectados": http://www-bcf.usc.edu/~mjneely/pdf_papers/dist_comp_dcdis2.pdf
La propiedad clave de esta formulación es que la función objetiva es una suma separable de términos, en la que cada término implica sólo funciones y variables asociadas a un nodo concreto. Del mismo modo, todas las restricciones son tales sumas separables, y además los términos de las restricciones implican sólo variables vecinas (de modo que el paso de mensajes entre vecinos puede satisfacer estas restricciones). En el documento anterior se desarrolla un algoritmo distribuido que resuelve esto, en el que cada nodo conoce sólo su propio $f_i( \cdot )$ función.
Un uso alternativo de una estructura de árbol
Si no te gustan todos los $x_i^k$ variables (lo cual no hago), podrías usar una estructura de árbol con una raíz en algún nodo, digamos el nodo 1. Entonces podrías definir $s_i$ como una variable que es la suma de $x_i$ y el $s_j$ valores de sus hijos, y luego definir la restricción adicional $ s_1 = y_1$ . Esto refuerza el deseado $ \sum_ {i=1}^Nx_i=y$ la restricción. Doy un algoritmo para esto en la última sección de abajo.
Un enfoque de actualización retardada
Alternativamente, se podría designar al nodo 1 como "guardián de las restricciones" y luego asumir que todos los nodos pueden comunicarse con el nodo 1 después de un retardo fijo de $D \geq 0$ franjas horarias. El problema resultante y un algoritmo es:
Minimizar:
$$ \sum_ {i=1}^N f_i(x_i, y_i) $$
Sujeto a:
$$ y_i = y_1 \: \mbox { for all $ i \in \{2, 3, \ldots N\} $} $$
$$ \sum_ {i=1}^N x_i = y_1 $$
$$ x_i \in \mathcal {X}_i \: , \: y_i \in \mathcal {Y} $$
Entonces se puede utilizar un "enfoque de deriva retardada más pena" como hice en un documento más reciente "Optimización estocástica distribuida mediante programación correlativa" (véase la ecuación (24) allí): http://ee.usc.edu/stochastic-nets/docs/distributed-opt-infocom2014.pdf
Específicamente, puedes hacer cumplir las restricciones con "colas virtuales" $Q_i(t)$ y $Z(t)$ (relacionado con las actualizaciones de los multiplicadores de Lagrange) que utilizan versiones retrasadas del $x_i$ variables. Éstas se actualizan cada vez que el paso $t \in \{0, 1, 2, \ldots\ }$ por:
$$ Q_i(t+1) = Q_i(t) + y_i(t-D) - y_1(t-D) \: \mbox { for all $ i \in \{2, 3, \ldots , N\} $}$$
$$ Z(t+1) = Z(t) + \sum_ {i=1}^{N-1}x_i(t-D) - y_1(t-D) $$
Supongamos que el $ \mathcal {X}_i$ y $ \mathcal {Y}$ Los conjuntos son compactos, así que las colas virtuales cambian como máximo una constante limitada en cada ranura.
Algoritmo:
Arreglar $ \epsilon >0$ . Cada vez que se da un paso $t \in\ {0,1,2, \ldots\ }$ cada nodo $i$ observa $ \tilde {Q}_i(t)$ y $ \tilde {Z}(t)$ siendo cualquier valor que difiera de los verdaderos $Q_i(t)$ y $Z(t)$ variables a lo sumo por alguna constante aditiva $C$ (donde $C$ no depende de $t$ o el $Q_i(t)$ , $Z_i(t)$ valores... usando $ \tilde {Q}_i(t) = Q_i(t-D)$ obras). Entonces..:
i) Nodos $i \in \{2, \ldots , N\}$ elige $x_i(t), y_i(t)$ por:
Minimizar: $ \frac {1}{ \epsilon } f_i(x_i(t), y_i(t)) + \tilde {Q}_i(t)y_i(t) + \tilde {Z}(t)x_i(t)$
Sujeto a: $x_i(t) \in \mathcal {X}_i, y_i(t) \in \mathcal {Y}$
ii) Nodo $1$ elige $x_1(t), y_1(t)$ por:
Minimizar: $ \frac {1}{ \epsilon } f_1(x_1(t), y_1(t)) - y_1(t) \left (Z(t) + \sum_ {i=2}^NQ_i(t) \right )$
Sujeto a: $x_1(t) \in \mathcal {X}_1, y_1(t) \in \mathcal {Y}$ .
iii) El nodo 1 actualiza las colas virtuales $Q_i(t)$ y $Z(t)$ usando información retrasada $x_i(t-D)$ y $y_i(t-D)$ como se especifica en las ecuaciones de cola anteriores.
El algoritmo resultante produce promedios de tiempo $ \overline {x}_i(t)$ y $ \overline {y}_i(t)$ que son un $O( \epsilon )$ -aproximación a la solución del programa convexo, donde:
$$ \overline {x}_i(t) = \frac {1}{t} \sum_ { \tau =0}^{t-1} x_i( \tau ) \: \: , \: \: \overline {y}_i(t) = \frac {1}{t} \sum_ { \tau =0}^{t-1} y_i( \tau ) $$
Esto es cierto independientemente de la constante de aproximación $C$ aunque una gran $C$ afectará al coeficiente de la $O( \epsilon )$ así como el tiempo de convergencia. Las funciones $f_i( \cdot )$ deben ser convexos, pero no necesariamente estrictamente convexos. Por ejemplo, funciona para programas lineales.
El algoritmo basado en el árbol
Asumamos la estructura del árbol, con el nodo 1 como "raíz". Para cada nodo $i \in \{1, \ldots , N\}$ define $C(i)$ como el conjunto de nodos que son hijos de nodo $i$ . El conjunto $C(i)$ está vacío si el nodo $i$ es una hoja. Para cada uno $i \in \{2, 3, \ldots , N\}$ define $P(i)$ como padre del nodo $i$ . Por simplicidad, supongamos que los conjuntos $ \mathcal {X}_i$ son conjuntos de números no negativos.
Minimizar: $$ \sum_ {i=1}^N f_i(x_i, y_i) $$
Sujeto a:
$$ y_i = y_{P(i)} \: \: \mbox { for all $ i \in \{2, \ldots , N\} $} $$ $$ y_1 = s_1 $$ $$ s_i = x_i + \sum_ {j \in C(i)} s_j \: \: \mbox { for all $ i \in \{1, \ldots , N\} $} $$ $$ y_i \in \mathcal {Y}, x_i \in \mathcal {X}_i, s_i \in [0, s_{max}] $$
donde $s_{max}$ es un máximo conocido en la suma de los $x_i$ (tal máximo existe desde que la $ \mathcal {X}_i$ los juegos son compactos).
El método de la deriva más la pena:
Para cada restricción, defina una cola virtual con ecuaciones de actualización dadas por:
$$ Q_i(t+1) = Q_i(t) + y_i(t) - y_{P(i)}(t) \: \: \mbox { for all $ i \in \{2, \ldots , N\} $} $$
$$ Z(t+1) = Z(t) + y_1(t) - s_1(t) $$
$$ H_i(t+1) = H_i(t) + s_i(t) - x_i(t) - \sum_ {j \in C(i)} s_j(t) \: \: \mbox { for all $ i \in \{1, \ldots , N\} $} $$
Los valores $Q_i(t)$ y $H_i(t)$ se mantienen en el nodo $i$ . El $Z(t)$ se mantiene en el nodo 1. Cada franja horaria $t$ hacer:
i) Nodos $i \in\ {2, \ldots , N\}$ observan su propia cola $H_i(t)$ y la cola $H_{P(i)}(t)$ de sus padres, y elige $s_i(t) \in [0, s_{max}]$ para minimizar: $$ s_i(t)[H_i(t) - H_{P(i)}(t)] $$ Esto se reduce a elegir $s_i(t)=0$ si $H_i(t) \geq H_{P(i)}(t)$ y $s_i(t)=s_{max}$ sino
ii) Nodos $i \in \{2, \ldots , N\}$ observan sus propias colas $Q_i(t), H_i(t)$ y las colas $Q_j(t)$ para sus hijos $j \in C(i)$ y elegir $x_i(t) \in \mathcal {X}_i$ , $y_i(t) \in\mathcal {Y}$ para minimizar: $$ \frac {1}{ \epsilon }f_i(x_i(t), y_i(t)) + y_i(t) \left [Q_i(t) - \sum_ {j \in C(i)} Q_j(t) \right ] -x_i(t)H_i(t) $$
iii) El nodo 1 observa su propia $Z(t)$ la cola y las colas $Q_j(t)$ para sus hijos $j \in C(1)$ y elige $y_1(t) \in \mathcal {Y}$ , $x_1(t) \in \mathcal {X}_1$ para minimizar: $$ \frac {1}{ \epsilon }f_1(x_1(t), y_1(t)) + y_1(t) \left [Z(t) - \sum_ {j \in C(1)}Q_j(t) \right ] $$
iv) El nodo 1 observa su propio $Z(t), H_1(t)$ y elige $s_1(t) \in [0, s_{max}]$ para minimizar: $$ s_1(t)[-Z(t) + H_1(t)] $$
v) Cada nodo actualiza sus propias colas de acuerdo con las ecuaciones de actualización indicadas anteriormente.
