时变网络下的分布式优化算法

johnsoncodehk · 发表于 2022-7-22 09:45

DIGing（时变无向图）

参考文献：Nedic, Angelia & Olshevsky, Alex & Shi, Wei. (2016). Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs. SIAM Journal on Optimization.
假设：时变无向图；一致联合连通；双随机矩阵。
紧凑形式：
$\begin{align*} &x(k+1) = W(k)x(k)-\alpha y(k),\\ &y(k+1) = W(k)y(k)+\nabla f(x(k+1)) - \nabla f(x(k))， \end{align*}$
其中， $W(k)$ 是一个双随机矩阵，是一个固定步长。
非紧凑形式：
$\begin{align*} &x_i(k+1) = \sum_{j=1}^n w_{ij}(k)x_j(k)-\alpha y_i(k),\\ &y_i(k+1) = \sum_{j=1}^n w_{ij}(k)y_j(k) + \nabla f_i(x_i(k+1)) - \nabla f_i(x_i(k)). \end{align*}$
PANDA（时变无向图）

参考文献：M. Maros and J. Jaldén, &#34;PANDA: A Dual Linearly Converging Method for Distributed Optimization Over Time-Varying Undirected Graphs,&#34; 2018 IEEE Conference on Decision and Control (CDC), 2018, pp. 6520-6525.
假设：时变无向图；一致联合连通；双随机矩阵。
紧凑形式：
$\begin{align*} &x(k+1) = \mathop{\arg\min}\limits_{x}\ f(x)-\big(y(k)\big)^Tx,\\ &z(k+1) = \big(W(k) ⊗I_p\big)z(k)+x(k+1)-x(k),\\ &y(k+1) = y(k)-c\big(x(k+1)-z(k+1)\big). \end{align*}$
非紧凑形式：
$\begin{align*} &x_i(k+1) = \mathop{\arg\min}\limits_{x_i}\ f_i(x_i)-\big(y_i(k)\big)^Tx_i,\\ &z_i(k+1) = \sum_{j\in\mathcal{N}_i\cup\{i\}}w_{ij}(k)z_j(k)+x_i(k+1)-x_i(k),\\ &y_i(k+1) = y_i(k)-c\big(x_i(k+1)-z_i(k+1)\big). \end{align*}$
Accelerated Gradient Tracking (时变无向图)

参考文献：Li, Huan & Lin, Zhouchen. (2021). Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization.
假设：时变无向图；一致联合连通；双随机矩阵。
$\begin{align*} &y(k) = \theta(k)z(k)+(1-\theta(k))x(k),\\ &s(k) = W_1(k)s(k-1)+\nabla f(y(k))-\nabla f(y(k-1)),\\ &z(k+1) = \frac{1}{1+\frac{\mu\alpha}{\theta(k)}}\bigg( W_2(k) \Big( \frac{\mu\alpha}{\theta(k)}y(k) + z(k) \Big) -\frac{\alpha}{\theta(k)}s(k) \bigg), \\ &x(k+1) = \theta(k)z(k+1) + (1-\theta(k))W_3(k)x(k). \end{align*}$
TV-AB（时变有向图）

参考文献：F. Saadatniaki, R. Xin and U. A. Khan, &#34;Decentralized Optimization Over Time-Varying Directed Graphs With Row and Column-Stochastic Matrices,&#34; in IEEE Transactions on Automatic Control, 2020, vol. 65, no. 11, pp. 4769-4780.
假设：时变有向图；一致联合强连通；行和列随机矩阵。
紧凑形式：
$\begin{align*} &x(k+1) = A(k)x(k)-\eta y(k),\\ &y(k+1) = B(k)y(k)+\nabla f(x(k+1)) - \nabla f(x(k)), \end{align*}$
其中， $A(k)$ 和 $B(k)$ 分别是行随机矩阵和列随机矩阵。
非紧凑形式：
$\begin{align*} &x_i(k+1) = \sum_{j=1}^n a_{ij}(k)x_j(k)-\eta y_i(k),\\ &y_i(k+1) = \sum_{j=1}^n b_{ij}(k)y_j(k)+\nabla f_i(x_i(k+1)) - \nabla f_i(x_i(k)). \end{align*}$
Push-Sum based（时变有向图）

参考文献：A. Nedi and A. Olshevsky, &#34;Distributed Optimization Over Time-Varying Directed Graphs,&#34; in IEEE Transactions on Automatic Control, vol. 60, no. 3, pp. 601-615, March 2015.
假设：时变有向图；一致联合强连通；列随机矩阵。
$\begin{align*} &w_i(k+1)=\sum_{j\in N_i^{in}(k)}\frac{x_j(k)}{d_j(k)},\\ &y_i(k+1)=\sum_{j\in N_i^{in}(k)}\frac{y_j(k)}{d_j(k)},\\ &z_i(k+1)=\frac{w_i(k+1)}{y_i(k+1)},\\ &x_i(k+1)=w_i(k+1)-\alpha(k+1)g_i(k+1), \end{align*}$
其中，前两项的权重系数满足列随机； $y_i(0)=1$ ； $g_i(k+1)$ 是函数 $f_i(z)$ 在 $z=z_i(k+1)$ 处的次梯度。
Push-DIGing (时变有向图)

参考资料：Nedic, Angelia & Olshevsky, Alex & Shi, Wei. (2016). Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs. SIAM Journal on Optimization. 27.
假设：时变有向图；一致联合强连通；列随机矩阵。 $\begin{align*}&u_i(k+1) = \sum_{j=1}^{n}C_{ij}(k)\big( u_j(k)-\alpha y_j(k) \big),\\ &v_i(k+1) = \sum_{j=1}^{n}C_{ij}(k)v_j(k),\\ &x_i(k+1) = u_i(k+1)/v_i(k+1),\\ &y_i(k+1) = \sum_{j=1}^{n}C_{ij}(k)y_j(k)+\nabla f_i(x_i(k+1)) - \nabla f_i(x_i(k)), \end{align*}$
其中， $C(k)=[C_{ij}(k)]$ 满足列随机；是一个固定步长； $v_i(0)=1$ 。

		自动登录	找回密码
密码			立即注册