IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v129y2006i3d10.1007_s10957-006-9080-1.html
   My bibliography  Save this article

Optimal Scaling of a Gradient Method for Distributed Resource Allocation

Author

Listed:
  • L. Xiao

    (California Institute of Technology)

  • S. Boyd

    (Stanford University)

Abstract

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.

Suggested Citation

  • L. Xiao & S. Boyd, 2006. "Optimal Scaling of a Gradient Method for Distributed Resource Allocation," Journal of Optimization Theory and Applications, Springer, vol. 129(3), pages 469-488, June.
    • Handle: RePEc:spr:joptap:v:129:y:2006:i:3:d:10.1007_s10957-006-9080-1
    DOI: 10.1007/s10957-006-9080-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-006-9080-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-006-9080-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hurwicz, Leonid, 1973. "The Design of Mechanisms for Resource Allocation," American Economic Review, American Economic Association, vol. 63(2), pages 1-30, May.
    2. G. M. Heal, 1969. "Planning without Prices," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 36(3), pages 347-362.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Huang, Lei & Sun, Wei & Li, Qiyue & Li, Weitao, 2023. "Distributed real-time economic dispatch for islanded microgrids with dynamic power demand," Applied Energy, Elsevier, vol. 342(C).
    2. Ion Necoara & Andrei Patrascu, 2014. "A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints," Computational Optimization and Applications, Springer, vol. 57(2), pages 307-337, March.
    3. Andrea Simonetto & Hadi Jamali-Rad, 2016. "Primal Recovery from Consensus-Based Dual Decomposition for Distributed Convex Optimization," Journal of Optimization Theory and Applications, Springer, vol. 168(1), pages 172-197, January.
    4. Yajie Jiang & Siyuan Cheng & Haoze Wang, 2023. "Distributed Integral Convex Optimization-Based Current Control for Power Loss Optimization in Direct Current Microgrids," Energies, MDPI, vol. 16(24), pages 1-17, December.
    5. Andrea Cristofari, 2019. "An almost cyclic 2-coordinate descent method for singly linearly constrained problems," Computational Optimization and Applications, Springer, vol. 73(2), pages 411-452, June.
    6. Wu, Kunming & Li, Qiang & Chen, Ziyu & Lin, Jiayang & Yi, Yongli & Chen, Minyou, 2021. "Distributed optimization method with weighted gradients for economic dispatch problem of multi-microgrid systems," Energy, Elsevier, vol. 222(C).
    7. Sjur Didrik Flåm, 2019. "Blocks of coordinates, stochastic programming, and markets," Computational Management Science, Springer, vol. 16(1), pages 3-16, February.
    8. Ion Necoara & Yurii Nesterov & François Glineur, 2017. "Random Block Coordinate Descent Methods for Linearly Constrained Optimization over Networks," Journal of Optimization Theory and Applications, Springer, vol. 173(1), pages 227-254, April.
    9. William La Cruz, 2022. "A genetic algorithm with a self-reproduction operator to solve systems of nonlinear equations," Journal of Global Optimization, Springer, vol. 84(4), pages 1005-1032, December.
    10. Hua Han & Lang Li & Lina Wang & Mei Su & Yue Zhao & Josep M. Guerrero, 2017. "A Novel Decentralized Economic Operation in Islanded AC Microgrids," Energies, MDPI, vol. 10(6), pages 1-18, June.
    11. Flåm, Sjur Didrik, 2015. "Bilateral exchange and competitive equilibrium," Working Papers in Economics 05/15, University of Bergen, Department of Economics.
    12. Sjur Didrik Flåm, 2016. "Noncooperative games, coupling constraints, and partial efficiency," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 4(2), pages 213-229, October.
    13. Hongsheng Liu & Shu Lu, 2019. "Convergence of the augmented decomposition algorithm," Computational Optimization and Applications, Springer, vol. 72(1), pages 179-213, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dilip Mookherjee, 2008. "The 2007 Nobel Memorial Prize in Mechanism Design Theory," Scandinavian Journal of Economics, Wiley Blackwell, vol. 110(2), pages 237-260, June.
    2. Andrea Attar & Thomas Mariotti & François Salanié, 2020. "The Social Costs of Side Trading," The Economic Journal, Royal Economic Society, vol. 130(630), pages 1608-1622.
    3. Robert Cooter & Winand Emons, 2004. "Truth-Bonding and Other Truth-Revealing Mechanisms for Courts," European Journal of Law and Economics, Springer, vol. 17(3), pages 307-327, May.
    4. Warr, Peter G., 1974. "The Economics Of Shadow Pricing: Market Distortions And Public Investment," Staff Papers 14116, University of Minnesota, Department of Applied Economics.
    5. Tian, Guoqiang, 2004. "On the Informational Requirements of Decentralized Pareto-Satisfactory Mechanisms in Economies with Increasing Returns," MPRA Paper 41226, University Library of Munich, Germany, revised Oct 2006.
    6. Chorus, Caspar & van Cranenburgh, Sander & Daniel, Aemiro Melkamu & Sandorf, Erlend Dancke & Sobhani, Anae & Szép, Teodóra, 2021. "Obfuscation maximization-based decision-making: Theory, methodology and first empirical evidence," Mathematical Social Sciences, Elsevier, vol. 109(C), pages 28-44.
    7. Masahiko Aoki, 2013. "Institutions as cognitive media between strategic interactions and individual beliefs," Chapters, in: Comparative Institutional Analysis, chapter 17, pages 298-312, Edward Elgar Publishing.
    8. Attar, Andrea & Campioni, Eloisa & Mariotti, Thomas & Pavan, Alessandro, 2021. "Keeping the Agents in the Dark: Private Disclosures in Competing Mechanisms," TSE Working Papers 21-1227, Toulouse School of Economics (TSE), revised Dec 2023.
    9. Schnizler, Björn & Neumann, Dirk & Veit, Daniel & Napoletano, Mauro & Catalano, Michele & Gallegati, Mauro & Reinicke, Michael & Streitberger, Werner & Eymann, Torsten, 2005. "Environmental analysis for application layer networks," Bayreuth Reports on Information Systems Management 1, University of Bayreuth, Chair of Information Systems Management.
    10. Luis Garicano & Luis Rayo, 2016. "Why Organizations Fail: Models and Cases," Journal of Economic Literature, American Economic Association, vol. 54(1), pages 137-192, March.
    11. Kangning Zheng & Zuopeng Zhang & Jeffrey Gauthier, 2022. "RETRACTED ARTICLE: Blockchain-based intelligent contract for factoring business in supply chains," Annals of Operations Research, Springer, vol. 308(1), pages 777-797, January.
    12. Mehrdad Vahabi, 1999. "From Walrasian General Equilibrium to Incomplete Contracts: Making Sense of Institutions," Post-Print halshs-03704424, HAL.
    13. Roger Myerson, 2009. "Fundamental theory of institutions: a lecture in honor of Leo Hurwicz," Review of Economic Design, Springer;Society for Economic Design, vol. 13(1), pages 59-75, April.
    14. Serrano, Roberto, 2002. "Decentralized information and the Walrasian outcome: a pairwise meetings market with private values," Journal of Mathematical Economics, Elsevier, vol. 38(1-2), pages 65-89, September.
    15. Roswitha King, 2010. "Regional business development policy in Central and Eastern Europe: a mechanism design perspective," Review of Economic Design, Springer;Society for Economic Design, vol. 14(1), pages 221-242, March.
    16. Louis Makowski & Joseph M. Ostroy, 1991. "The Margin of Appropriation and an Extension of the First Theorem of Welfare Economists," UCLA Economics Working Papers 629, UCLA Department of Economics.
    17. Jean-Marie Blin & Mark A. Satterthwaite, 1975. "An Impossibility Theorem for Deterministic Organizations," Discussion Papers 129, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    18. Matthew O. Jackson, 2001. "A crash course in implementation theory," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 18(4), pages 655-708.
    19. Dirk Neumann & Morad Benyoucef & Sarita Bassil & Julie Vachon, 2003. "Applying the Montreal Taxonomy to State of the Art E-Negotiation Systems," Group Decision and Negotiation, Springer, vol. 12(4), pages 287-310, July.
    20. Malone, Thomas W. & Crowston, Kevin., 1993. "The interdisciplinary study of coordination," Working papers 3630-93. CCSTR ; #157., Massachusetts Institute of Technology (MIT), Sloan School of Management.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:129:y:2006:i:3:d:10.1007_s10957-006-9080-1. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.