Vanishing price of decentralization in large coordinative nonconvex optimization

Research output: Contribution to journalArticle

Abstract

We focus on nonconvex multi-agent optimization where a large number of participants collaboratively optimize some social cost function and their individual preferences. We focus on the semidecentralized multi-agent best response setting where a central planner attempts to coordinate the agents and each participant pursues self-interest. By studying the duality framework, we provide geometric and analytic characterizations of the duality gap and the price of decentralization. We prove that the nonconvex problem becomes increasingly convex as the problem scales up in dimension. Upon appropriate coordination, the price of decentralization asymptotically vanishes to zero as the number of participants grows. We develop a duality-based coordination procedure for the central planner to adapt the price vector and select a particular best response for each participant. The coordination algorithm is able to induce individual best responses to dynamically converge to an approximate global optimum, regardless of the initial solution. A convergence rate and complexity analysis as well as numerical results are provided. In the case without any coordination, we provide counterexamples showing that the price of decentralization can be disastrously high.

Original languageEnglish (US)
Pages (from-to)1977-2009
Number of pages33
JournalSIAM Journal on Optimization
Volume27
Issue number3
DOIs
StatePublished - 2017

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science

Keywords

  • Cooperative optimization
  • Cutting plane method
  • Duality gap
  • Multi-agent optimization
  • Nonconvex optimization
  • Price of decentralization

Fingerprint Dive into the research topics of 'Vanishing price of decentralization in large coordinative nonconvex optimization'. Together they form a unique fingerprint.

  • Cite this