Vanishing Price of Anarchy in Large Coordinative Nonconvex Optimization
Mengdi Wang (mengdiwprinceton.edu)
Abstract: We focus on a class of nonconvex cooperative optimization problems that involve multiple participants. We study the duality framework and provide geometric and analytic character- izations of the duality gap. The dual problem is related to a market setting in which each participant pursuits self interests at a given price of common goods. The duality gap is a form of price of anarchy. We prove that the nonconvex problem becomes increasingly convex as the problem scales up in dimension. In other words, the price of anarchy vanishes to zero as the number of participants grows. We prove the existence of a solution to the dual problem that is an approximate global optimum and achieves the minimal price of anarchy. We develop a coor- dination procedure to identify it from the set of all individualís best responses. Furthermore, we propose a globally convergent duality-based algorithm that relies on individual best responses to achieve the approximate social optimum. Convergence and rate of convergence analysis as well as numerical results are provided.
Keywords: nonconvex optimization, duality gap, price of anarchy, cooperative optimization, cutting plane method.
Category 1: Convex and Nonsmooth Optimization (Convex Optimization )
Category 2: Global Optimization (Theory )
Citation: ORFE, Princeton Univeristy. July, 2015
Entry Submitted: 07/22/2015
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|