Optimization Online


Vanishing Price of Anarchy in Large Coordinative Nonconvex Optimization

Mengdi Wang (mengdiw***at***princeton.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

Download: [PDF]

Entry Submitted: 07/22/2015
Entry Accepted: 07/22/2015
Entry Last Modified: 07/28/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society