时变网络下的分布式优化算法
DIGing（时变无向图）参考文献：Nedic, Angelia & Olshevsky, Alex & Shi, Wei. (2016). Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs. SIAM Journal on Optimization.
假设：时变无向图；一致联合连通；双随机矩阵。
紧凑形式：
https://www.zhihu.com/equation?tex=+%5Cbegin%7Balign%2A%7D+%26x%28k%2B1%29+%3D+W%28k%29x%28k%29-%5Calpha+y%28k%29%2C%5C%5C+%26y%28k%2B1%29+%3D+W%28k%29y%28k%29%2B%5Cnabla+f%28x%28k%2B1%29%29+-+%5Cnabla+f%28x%28k%29%29%EF%BC%8C+%5Cend%7Balign%2A%7D+
其中， https://www.zhihu.com/equation?tex=W%28k%29 是一个双随机矩阵，是一个固定步长。
非紧凑形式：
https://www.zhihu.com/equation?tex=+%5Cbegin%7Balign%2A%7D+%26x_i%28k%2B1%29+%3D+%5Csum_%7Bj%3D1%7D%5En+w_%7Bij%7D%28k%29x_j%28k%29-%5Calpha+y_i%28k%29%2C%5C%5C+%26y_i%28k%2B1%29+%3D+%5Csum_%7Bj%3D1%7D%5En+w_%7Bij%7D%28k%29y_j%28k%29+%2B+%5Cnabla+f_i%28x_i%28k%2B1%29%29+-+%5Cnabla+f_i%28x_i%28k%29%29.+%5Cend%7Balign%2A%7D+
PANDA（时变无向图）
参考文献：M. Maros and J. Jaldén, "PANDA: A Dual Linearly Converging Method for Distributed Optimization Over Time-Varying Undirected Graphs," 2018 IEEE Conference on Decision and Control (CDC), 2018, pp. 6520-6525.
假设：时变无向图；一致联合连通；双随机矩阵。
紧凑形式：
https://www.zhihu.com/equation?tex=+%5Cbegin%7Balign%2A%7D+%26x%28k%2B1%29+%3D+%5Cmathop%7B%5Carg%5Cmin%7D%5Climits_%7Bx%7D%5C+f%28x%29-%5Cbig%28y%28k%29%5Cbig%29%5ETx%2C%5C%5C+%26z%28k%2B1%29+%3D+%5Cbig%28W%28k%29+%E2%8A%97I_p%5Cbig%29z%28k%29%2Bx%28k%2B1%29-x%28k%29%2C%5C%5C+%26y%28k%2B1%29+%3D+y%28k%29-c%5Cbig%28x%28k%2B1%29-z%28k%2B1%29%5Cbig%29.+%5Cend%7Balign%2A%7D+
非紧凑形式：
https://www.zhihu.com/equation?tex=+%5Cbegin%7Balign%2A%7D+%26x_i%28k%2B1%29+%3D+%5Cmathop%7B%5Carg%5Cmin%7D%5Climits_%7Bx_i%7D%5C+f_i%28x_i%29-%5Cbig%28y_i%28k%29%5Cbig%29%5ETx_i%2C%5C%5C+%26z_i%28k%2B1%29+%3D+%5Csum_%7Bj%5Cin%5Cmathcal%7BN%7D_i%5Ccup%5C%7Bi%5C%7D%7Dw_%7Bij%7D%28k%29z_j%28k%29%2Bx_i%28k%2B1%29-x_i%28k%29%2C%5C%5C+%26y_i%28k%2B1%29+%3D+y_i%28k%29-c%5Cbig%28x_i%28k%2B1%29-z_i%28k%2B1%29%5Cbig%29.+%5Cend%7Balign%2A%7D+
Accelerated Gradient Tracking (时变无向图)
参考文献：Li, Huan & Lin, Zhouchen. (2021). Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization.
假设：时变无向图；一致联合连通；双随机矩阵。
https://www.zhihu.com/equation?tex=+%5Cbegin%7Balign%2A%7D+%26y%28k%29+%3D+%5Ctheta%28k%29z%28k%29%2B%281-%5Ctheta%28k%29%29x%28k%29%2C%5C%5C+%26s%28k%29+%3D+W_1%28k%29s%28k-1%29%2B%5Cnabla+f%28y%28k%29%29-%5Cnabla+f%28y%28k-1%29%29%2C%5C%5C+%26z%28k%2B1%29+%3D+%5Cfrac%7B1%7D%7B1%2B%5Cfrac%7B%5Cmu%5Calpha%7D%7B%5Ctheta%28k%29%7D%7D%5Cbigg%28+W_2%28k%29+%5CBig%28+%5Cfrac%7B%5Cmu%5Calpha%7D%7B%5Ctheta%28k%29%7Dy%28k%29+%2B+z%28k%29+%5CBig%29+-%5Cfrac%7B%5Calpha%7D%7B%5Ctheta%28k%29%7Ds%28k%29+%5Cbigg%29%2C+%5C%5C+%26x%28k%2B1%29+%3D+%5Ctheta%28k%29z%28k%2B1%29+%2B+%281-%5Ctheta%28k%29%29W_3%28k%29x%28k%29.+%5Cend%7Balign%2A%7D+
TV-AB（时变有向图）
参考文献：F. Saadatniaki, R. Xin and U. A. Khan, "Decentralized Optimization Over Time-Varying Directed Graphs With Row and Column-Stochastic Matrices," in IEEE Transactions on Automatic Control, 2020, vol. 65, no. 11, pp. 4769-4780.
假设：时变有向图；一致联合强连通；行和列随机矩阵。
紧凑形式：
https://www.zhihu.com/equation?tex=+%5Cbegin%7Balign%2A%7D+%26x%28k%2B1%29+%3D+A%28k%29x%28k%29-%5Ceta+y%28k%29%2C%5C%5C+%26y%28k%2B1%29+%3D+B%28k%29y%28k%29%2B%5Cnabla+f%28x%28k%2B1%29%29+-+%5Cnabla+f%28x%28k%29%29%2C+%5Cend%7Balign%2A%7D+
其中， https://www.zhihu.com/equation?tex=A%28k%29 和 https://www.zhihu.com/equation?tex=B%28k%29 分别是行随机矩阵和列随机矩阵。
非紧凑形式：
https://www.zhihu.com/equation?tex=+%5Cbegin%7Balign%2A%7D+%26x_i%28k%2B1%29+%3D+%5Csum_%7Bj%3D1%7D%5En+a_%7Bij%7D%28k%29x_j%28k%29-%5Ceta+y_i%28k%29%2C%5C%5C+%26y_i%28k%2B1%29+%3D+%5Csum_%7Bj%3D1%7D%5En+b_%7Bij%7D%28k%29y_j%28k%29%2B%5Cnabla+f_i%28x_i%28k%2B1%29%29+-+%5Cnabla+f_i%28x_i%28k%29%29.+%5Cend%7Balign%2A%7D+
Push-Sum based（时变有向图）
参考文献：A. Nedi and A. Olshevsky, "Distributed Optimization Over Time-Varying Directed Graphs," in IEEE Transactions on Automatic Control, vol. 60, no. 3, pp. 601-615, March 2015.
假设：时变有向图；一致联合强连通；列随机矩阵。
https://www.zhihu.com/equation?tex=+%5Cbegin%7Balign%2A%7D+%26w_i%28k%2B1%29%3D%5Csum_%7Bj%5Cin+N_i%5E%7Bin%7D%28k%29%7D%5Cfrac%7Bx_j%28k%29%7D%7Bd_j%28k%29%7D%2C%5C%5C+%26y_i%28k%2B1%29%3D%5Csum_%7Bj%5Cin+N_i%5E%7Bin%7D%28k%29%7D%5Cfrac%7By_j%28k%29%7D%7Bd_j%28k%29%7D%2C%5C%5C+%26z_i%28k%2B1%29%3D%5Cfrac%7Bw_i%28k%2B1%29%7D%7By_i%28k%2B1%29%7D%2C%5C%5C+%26x_i%28k%2B1%29%3Dw_i%28k%2B1%29-%5Calpha%28k%2B1%29g_i%28k%2B1%29%2C+%5Cend%7Balign%2A%7D+
其中，前两项的权重系数满足列随机； https://www.zhihu.com/equation?tex=y_i%280%29%3D1 ； https://www.zhihu.com/equation?tex=g_i%28k%2B1%29 是函数 https://www.zhihu.com/equation?tex=f_i%28z%29 在 https://www.zhihu.com/equation?tex=z%3Dz_i%28k%2B1%29 处的次梯度。
Push-DIGing (时变有向图)
参考资料：Nedic, Angelia & Olshevsky, Alex & Shi, Wei. (2016). Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs. SIAM Journal on Optimization. 27.
假设：时变有向图；一致联合强连通；列随机矩阵。 https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D%26u_i%28k%2B1%29+%3D+%5Csum_%7Bj%3D1%7D%5E%7Bn%7DC_%7Bij%7D%28k%29%5Cbig%28+u_j%28k%29-%5Calpha+y_j%28k%29+%5Cbig%29%2C%5C%5C+%26v_i%28k%2B1%29+%3D+%5Csum_%7Bj%3D1%7D%5E%7Bn%7DC_%7Bij%7D%28k%29v_j%28k%29%2C%5C%5C+%26x_i%28k%2B1%29+%3D+u_i%28k%2B1%29%2Fv_i%28k%2B1%29%2C%5C%5C+%26y_i%28k%2B1%29+%3D+%5Csum_%7Bj%3D1%7D%5E%7Bn%7DC_%7Bij%7D%28k%29y_j%28k%29%2B%5Cnabla+f_i%28x_i%28k%2B1%29%29+-+%5Cnabla+f_i%28x_i%28k%29%29%2C+%5Cend%7Balign%2A%7D
其中， https://www.zhihu.com/equation?tex=C%28k%29%3D%5BC_%7Bij%7D%28k%29%5D 满足列随机；是一个固定步长； https://www.zhihu.com/equation?tex=v_i%280%29%3D1 。
页:
[1]