TY - JOUR
T1 - Vanishing price of decentralization in large coordinative nonconvex optimization
AU - Wang, Mengdi
N1 - Funding Information:
∗Received by the editors March 29, 2016; accepted for publication (in revised form) July 3, 2017; published electronically September 7, 2017. http://www.siam.org/journals/siopt/27-3/M106820.html Funding: This work was funded by NSF grant DMS-1619818. †Operations Research and Financial Engineering, Princeton University, Princeton, NJ 08540 (mengdiw@princeton.edu).
Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
KW - Cooperative optimization
KW - Cutting plane method
KW - Duality gap
KW - Multi-agent optimization
KW - Nonconvex optimization
KW - Price of decentralization
UR - http://www.scopus.com/inward/record.url?scp=85032863149&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85032863149&partnerID=8YFLogxK
U2 - 10.1137/16M1068207
DO - 10.1137/16M1068207
M3 - Article
AN - SCOPUS:85032863149
SN - 1052-6234
VL - 27
SP - 1977
EP - 2009
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
IS - 3
ER -