optimización convexa mediante ADMM

Question

En la presentación consensuada de ADMM por Boyd (pg 37 en https://web.stanford.edu/~boyd/papers/pdf/admm_slides.pdf ), se afirma que:

La suma $\sum\limits_{i = 1}^{N}y_i^k = 0$ para todas las variables duales $y_i$ de las restricciones de igualdad consensuadas en cada paso $k$ . ¿Por qué es así? Agradecería una explicación y una prueba.

Gracias

Answer 1

La suma $\sum_{i=1}^N y_i^k = 0$ se deriva en realidad de $\nabla L(x,y,z) = 0$ , donde $L(x,y,z)$ es la función lagrangiana del problema original.

Pero aún así, podemos obtener este resultado en la formulación ADMM. Ya que tenemos \begin{equation} \begin{aligned} x_{i}^{k+1} &:=\underset{x_{i}}{\operatorname{argmin}}\left(f_{i}\left(x_{i}\right)+y_{i}^{k T}\left(x_{i}-z^{k}\right)+(\rho / 2)\left\|x_{i}-z^{k}\right\|_{2}^{2}\right), \\ z^{k+1} &:=\frac{1}{N} \sum_{i=1}^{N}\left(x_{i}^{k+1}+(1 / \rho) y_{i}^{k}\right) ,\\ y_{i}^{k+1} &:=y_{i}^{k}+\rho\left(x_{i}^{k+1}-z^{k+1}\right). \end{aligned} \end{equation} calcular la suma de $y_i^{k+1}$ es decir, \begin{equation} \sum_{i=1}^N y_i^{k+1} = \sum_{i=1}^N y_i^k + \rho \left(\sum_{i=1}^N x_i^{k+1}- \sum_{i=1}^{N} z^{k+1} \right), \end{equation} donde \begin{equation} \sum_{i=1}^N z^{k+1} = N \cdot z^{k+1} = \sum_{i=1}^N\left(x_{i}^{k+1}+(1 / \rho) y_{i}^{k}\right). \end{equation} Así, \begin{equation} \sum_{i=1}^N y_i^{k+1} = \sum_{i=1}^N y_i^k + \rho \left(\sum_{i=1}^N x_i^{k+1}- \sum_{i=1}^{N}\left(x_{i}^{k+1}+(1 / \rho) y_{i}^{k}\right) \right) = 0. \end{equation}