An $O(1/k)$ Gradient Method for Network Resource Allocation Problems
Top Cited Papers
- 5 March 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Control of Network Systems
- Vol. 1 (1), 64-73
- https://doi.org/10.1109/tcns.2014.2309751
Abstract
We present a fast distributed gradient method for a convex optimization problem with linear inequalities, with a particular focus on the network utility maximization (NUM) problem. Most existing works in the literature use (sub)gradient methods for solving the dual of this problem which can be implemented in a distributed manner. However, these (sub)gradient methods suffer from an O (1/√ k ) rate of convergence (where k is the number of iterations). In this paper, we assume that the utility functions are strongly concave, an assumption satisfied by most standard utility functions considered in the literature. We develop a completely distributed fast gradient method for solving the dual of the NUM problem. We show that the generated primal sequences converge to the unique optimal solution of the NUM problem at rate O (1/ k ).Keywords
This publication has 19 references indexed in Scilit:
- Accelerated dual descent for constrained convex network flow optimizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- Approximate Primal Solutions and Rate Analysis for Dual Subgradient MethodsSIAM Journal on Optimization, 2009
- Layering as Optimization Decomposition: A Mathematical Theory of Network ArchitecturesProceedings of the IEEE, 2007
- Network Optimization and ControlFoundations and Trends® in Networking, 2007
- Fair end-to-end window-based congestion controlIEEE/ACM Transactions on Networking, 2000
- Ergodic, primal convergence in dual subgradient schemes for convex programmingMathematical Programming, 1999
- Optimization flow control. I. Basic algorithm and convergenceIEEE/ACM Transactions on Networking, 1999
- Rate control for communication networks: shadow prices, proportional fairness and stabilityJournal of the Operational Research Society, 1998
- Ergodic convergence in subgradient optimizationOptimization Methods and Software, 1998
- Matrix AnalysisPublished by Cambridge University Press (CUP) ,1985