DATE:            Friday, May 3, 2013

TIME:            3:30pm  – 4:30pm

LOCATION: Room 163, Research 1


Nonlinear Equilibrium vs. Linear Programming for Resource Allocation Problems

Roman Polyak, Ph.D.


SEOR & Mathematical Sciences Departments



When Linear Programming (LP) is used for optimal resources allocation, the prices for goods and the resources availability are given priory and independent on the production output and prices for the resources.

Nonlinear Equilibrium (NE), which is a generalization of Walras-Wald equilibrium, eliminates this basic drawback of LP.

Finding NE is equivalent to solving a variation inequality (VI) on the Cartesian product of the primal and dual non negative octants, projection on which is a very simple operation.

For solving the VI we consider two methods: projected pseudo-gradient (PPG) and extra pseudo-gradient (EPG), for which projection is the main operation at each step.

We established convergence, proved global Q-linear rate and estimated complexity of both methods under various assumptions on the input data.

Both PPG and EPG can be viewed as pricing mechanisms for establishing economic equilibrium.


Short Bio

Dr. Polyak received a B.Sc. and M.S. (honors) in mathematics and physics in 1960, and received a Ph.D from Moscow Central Institute of Mathematics and Economics at the U.S.S.R. Academy of Sciences in 1966. After emigrating to the U.S. in 1988, he was a visiting scientist at the Mathematical Sciences Department at the T.J. Watson Research Center IBM. Joining the faculty of George Mason University in January 1993, since then he has become a full professor of mathematics and operations research. During the last 15 years he received several NSF and NASA Awards for his work in NLP. He received the Fulbright Scholarship Award in 2001 for his work on NR theory and applications of the NR methods for solving real life problems. In 2003 he became an IFREE Fellow for his work in Mathematical Economics.