Towards Fast-Convergence, Low-Delay and Low-Complexity Network Optimization

doi:10.1145/3154492

Towards Fast-Convergence, Low-Delay and Low-Complexity Network Optimization

2017-12-19

0

OA

AI

DOI：10.1145/3154492

原文链接

查看原文

摘要

En 中文

Distributed network optimization has been studied for well over a decade. However, we still do not have a good idea of how to design schemes that can simultaneously provide good performance across the dimensions of utility optimality, convergence speed, and delay. To address these challenges, in this paper, we propose a new algorithmic framework with all these metrics approaching optimality. The salient features of our new algorithm are three-fold: (i) fast convergence: it converges with only O(\log(1/\epsilon)) iterations that is the fastest speed among all the existing algorithms; (ii) low delay: it guarantees optimal utility with finite queue length; (iii) simple implementation: the control variables of this algorithm are based on virtual queues that do not require maintaining per-flow information. The new technique builds on a kind of inexact Uzawa method in the Alternating Directional Method of Multiplier, and provides a new theoretical path to prove global and linear convergence rate of such a method without requiring the full rank assumption of the constraint matrix.

Towards Fast-Convergence, Low-Delay and Low-Complexity Network Optimization

摘要

AI总结

期刊

机构

引用论文