{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T20:22:53Z","timestamp":1787343773475,"version":"build-2736575974"},"reference-count":50,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1619818"],"award-info":[{"award-number":["DMS-1619818"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/16m1068207","type":"journal-article","created":{"date-parts":[[2017,9,7]],"date-time":"2017-09-07T13:57:35Z","timestamp":1504792655000},"page":"1977-2009","source":"Crossref","is-referenced-by-count":8,"title":["Vanishing Price of Decentralization in Large Coordinative Nonconvex Optimization"],"prefix":"10.1137","volume":"27","author":[{"given":"Mengdi","family":"Wang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,9,7]]},"reference":[{"key":"atypb1","first-page":"2306","author":"Abichandani P.","year":"2011","journal-title":"Washington, DC"},{"key":"atypb2","unstructured":"K. J. Arrow, F. Hahn, et al.\n                      General Competitive Analysis\n                      , Holden-Day, San Francisco, CA, 1971."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2013.2248002"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1.3.225"},{"key":"atypb5","first-page":"521","author":"Bento J.","year":"2013","journal-title":"NV"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF00937167"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1983.1103136"},{"key":"atypb8","unstructured":"D. P. Bertsekas,\n                      Nonlinear Programming\n                      , Athena Scientific, Belmont, MA, 1999."},{"key":"atypb9","unstructured":"D. P. Bertsekas,\n                      Convex Optimization Theory\n                      , Athena Scientific, Belmont, MA, 2009."},{"key":"atypb10","unstructured":"D. P. Bertsekas, A. Nedic\u0301, and A. Ozdaglar,\n                      Min common\/max crossing duality: A simple geometric framework for convex optimization and minimax theory\n                      , Rep. LIDS-P-2536, 2002; available online fromhttp:\/\/www.ifp.illinois.edu\/~angelia\/min_common.pdf."},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"D. P. Bertsekas and N. Sandell,\n                      Estimates of the duality gap for large-scale separable nonconvex optimization problems\n                      , in Proceedings of the 21st IEEE Conference on Decision and Control (Orlando, FL, 1982), IEEE, Washington, DC, 1982, pp. 782-785.","DOI":"10.1109\/CDC.1982.268248"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2008.11.009"},{"key":"atypb14","first-page":"433","author":"Cassels J.","year":"1975","journal-title":"UK"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-99-04788-7"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1081\/NFA-120039682"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"I. Ekeland and R. Temam,\n                      Convex Analysis and Variational Problems\n                      , corrected reprint of the 1976 English ed., Classics Appl. Math. 28, SIAM, Philadelphia, 1999,https:\/\/doi.org\/10.1137\/1.9781611971088.","DOI":"10.1137\/1.9781611971088"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017599310112"},{"key":"atypb19","unstructured":"E. X. Fang, L. Han, and W. Mengdi,\n                      Blessing of Massive Scale: Spatial Graphical Model Inference with a Total Cardinality Constraint\n                      , Working paper, 2015."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1177\/027836499801700706"},{"key":"atypb21","first-page":"248","author":"Grodal B.","year":"2009","journal-title":"U.A.E."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.2307\/1914042"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"M. I. Jordan,\n                      Learning in Graphical Models\n                      , Nato Sci. Ser. D 89, Springer, Dordrecht, The Netherlands, 1998.","DOI":"10.1007\/978-94-011-5014-9"},{"key":"atypb24","unstructured":"S. Kakade, S. Shalev-Shwartz, and A. Tewari,\n                      On the Duality of Strong Convexity and Strong Smoothness: Learning Applications and Matrix Regularization\n                      , Unpublished manuscript; available online fromhttp:\/\/ttic.uchicago.edu\/~shai\/papers\/KakadeShalevTewari09.pdf, 2009."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500106"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011429"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2009.2016871"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1287\/moor.9.2.244"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.1.63"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-006-9122-0"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1287\/moor.11.1.30"},{"key":"atypb32","first-page":"151","author":"Puri M. L.","year":"1985","journal-title":"UK"},{"key":"atypb33","first-page":"2453","author":"Raffard R. L.","year":"2004","journal-title":"Washington, DC"},{"key":"atypb34","first-page":"25","author":"Rahbar K.","year":"2014","journal-title":"Proceedings of the IEEE International Conference on Smart Grid Communications (SmartGridComm), IEEE, Washington, DC"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"A. Richards, J. Bellingham, M. Tillerson, and J. How,\n                      Coordination and control of multiple UAVs\n                      , in AIAA Guidance, Navigation, and Control Conference, Monterey, CA, 2002.","DOI":"10.2514\/6.2002-4588"},{"key":"atypb36","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, Princeton, NJ, 1970."},{"key":"atypb37","first-page":"80","author":"Scutari G.","year":"2012","journal-title":"Washington, DC"},{"key":"atypb38","unstructured":"A. Simonetto and G. Leus,\n                      Distributed Maximum Likelihood Sensor Network Localization\n                      , preprint,https:\/\/arxiv.org\/abs\/1309.2502, 2013."},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1109\/T-WC.2008.070241"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.2307\/1909201"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(81)90010-7"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"R. M. Starr,\n                      General Equilibrium Theory: An Introduction\n                      , Cambridge University Press, Cambridge, UK, 2011.","DOI":"10.1017\/CBO9780511975356"},{"key":"atypb43","first-page":"311","volume":"11","author":"Teo C. H.","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"atypb44","unstructured":"M. Udell and S. Boyd,\n                      Bounding Duality Gap for Separable Problems with Linear Constraints\n                      , preprint,https:\/\/arxiv.org\/abs\/1410.4158, 2014."},{"key":"atypb45","unstructured":"R. J. Vanderbei,\n                      Linear Programming: Foundations and Extensions\n                      , 3rd ed., Internat. Ser. Oper. Res. Management Sci. 37, Kluwer Academic Publishers, Boston, MA, 2001."},{"key":"atypb47","first-page":"804","author":"Vujanic R.","year":"2014","journal-title":"Washington, DC"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.2307\/1914230"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2006.877962"},{"key":"atypb50","first-page":"2541","author":"Zhang X.","year":"2010","journal-title":"Canada"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1007\/BF01212924"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1068207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:22:53Z","timestamp":1787340173000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1068207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1068207"],"URL":"https:\/\/doi.org\/10.1137\/16m1068207","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}