Optimization Online


Nonlinear Equilibrium for optimal resource allocation

Roman Polyak(rpolyak***at***gmu.edu)

Abstract: We consider Nonlinear Equilibrium (NE) for optimal allocation of limited resources. The NE is a generalization of the Walras-Wald equilibrium, which is equivalent to J. Nash equilibrium in an n-person concave game. Finding NE is equivalent to solving a variational inequality (VI) with a monotone and smooth operator on $\Omega = \Re_+^n\cross\Re_+^m$. The projection on $\Omega$ is a very simple procedure, therefore our main focus is two methods for which the projection on $\Omega$ is the main operation. Both projected pseudo-gradient (PPG) and extra pseudo-gradient (EPG) methods require $O(n^2)$ operations per step. We proved convergence, established global Q-linear rate and estimated computational complexity for both PPG and EPG methods. The methods can be viewed as pricing mechanisms for establishing economic equilibrium.

Keywords: Nonlinear Equilibrium, Duality, Walras-Wald equilibrium, Pseudo-gradient, Extra pseudo-gradient, Linear Programming

Category 1: Complementarity and Variational Inequalities

Category 2: Other Topics (Game Theory )

Citation: Technical Report 12_01_2012, SEOR/Math, George Mason University, Fairfax, VA, USA

Download: [PDF]

Entry Submitted: 05/08/2013
Entry Accepted: 05/08/2013
Entry Last Modified: 05/08/2013

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