A Caltech Library Service

Optimal Scaling of a Gradient Method for Distributed Resource Allocation

Xiao, L. and Boyd, S (2006) Optimal Scaling of a Gradient Method for Distributed Resource Allocation. Journal of Optimization Theory and Applications, 129 (3). pp. 469-488. ISSN 0022-3239.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We consider a class of weighted gradient methods for distributed resource allocation over a network. Each node of the network is associated with a local variable and a convex cost function; the sum of the variables (resources) across the network is fixed. Starting with a feasible allocation, each node updates its local variable in proportion to the differences between the marginal costs of itself and its neighbors. We focus on how to choose the proportional weights on the edges (scaling factors for the gradient method) to make this distributed algorithm converge and on how to make the convergence as fast as possible. We give sufficient conditions on the edge weights for the algorithm to converge monotonically to the optimal solution; these conditions have the form of a linear matrix inequality. We give some simple, explicit methods to choose the weights that satisfy these conditions. We derive a guaranteed convergence rate for the algorithm and find the weights that minimize this rate by solving a semidefinite program. Finally, we extend the main results to problems with general equality constraints and problems with block separable objective function.

Item Type:Article
Related URLs:
URLURL TypeDescription DOIArticle ReadCube access
Additional Information:© 2006 Springer Science+Business Media, Inc. Published Online: 29 November 2006. Communicated by P. Tseng. The authors are grateful to Professor Paul Tseng and the anonymous referee for their valuable comments that helped us to improve the presentation of this paper.
Subject Keywords:distributed optimization; resource allocations; weighted gradient methods; convergence rates; semidefinite programming
Issue or Number:3
Record Number:CaltechAUTHORS:20110714-135402006
Persistent URL:
Official Citation:Xiao, L. & Boyd, S. J Optim Theory Appl (2006) 129: 469.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:24426
Deposited By: Tony Diaz
Deposited On:22 Jul 2011 17:31
Last Modified:03 Oct 2019 02:56

Repository Staff Only: item control page