Decentralized Prediction-Correction Methods for Networked Time-Varying Convex Optimization
Decentralized Prediction-Correction Methods for Networked Time-Varying Convex Optimization
复制标题
DOI：
10.1109/tac.2017.2694611
复制
发表时间：
2016-02
影响因子：
6.8
通讯作者：
Andrea Simonetto;Alec Koppel;Aryan Mokhtari;G. Leus;Alejandro Ribeiro
中科院分区：
文献类型：
--
作者：
Andrea Simonetto;Alec Koppel;Aryan Mokhtari;G. Leus;Alejandro Ribeiro
我们开发的算法，发现和跟踪的时变凸优化问题，包括本地和网络相关的目标的最优解轨迹。该算法来自预测校正方法，其对应于在离散时间实例处对时变问题进行采样的策略，然后，通过交替执行关于下一时间样本处的优化器如何改变的预测和关于它们实际上如何改变的校正来生成序列。预测是基于最优性条件如何随时间演变，而校正是基于梯度或牛顿法，导致分散预测-校正梯度和分散预测-校正牛顿。我们扩展这些方法的情况下，知识的优化程序是如何改变的时间只是近似的，并提出分散近似预测校正梯度和分散近似预测校正牛顿。所有提出的方法的收敛特性进行了研究，并在无线网络中的资源分配问题的应用上显示经验性能。我们观察到，所提出的方法优于现有的运行算法的数量级。数值结果显示收敛精度，采样周期和网络通信之间的权衡。
We develop algorithms that find and track the optimal solution trajectory of time-varying convex optimization problems that consist of local and network-related objectives. The algorithms are derived from the prediction-correction methodology, which corresponds to a strategy where the time-varying problem is sampled at discrete time instances, and then, a sequence is generated via alternatively executing predictions on how the optimizers at the next time sample are changing and corrections on how they actually have changed. Prediction is based on how the optimality conditions evolve in time, while correction is based on a gradient or Newton method, leading to decentralized prediction-correction gradient and decentralized prediction-correction Newton. We extend these methods to cases where the knowledge on how the optimization programs are changing in time is only approximate and propose decentralized approximate prediction-correction gradient and decentralized approximate prediction-correction Newton. Convergence properties of all the proposed methods are studied and empirical performance is shown on an application of a resource allocation problem in a wireless network. We observe that the proposed methods outperform existing running algorithms by orders of magnitude. The numerical results showcase a tradeoff between convergence accuracy, sampling period, and network communications.