9634736 Magnanti This research involves the development of solution methods for solving finite dimensional fixed point and variational inequality problems. The goals of this project are to create and study algorithms that are able to solve broader classes of problems than the current state-of-the-art and to accelerate the convergence of "inefficient" algorithms. New solution methods based on a general theory of averaging will be investigated; these include averaging schemes with the identity map, averaging schemes with contractive maps and path following methods, general averaging using resolvents, component-wise averaging, and averaging relative to a potential. The investigators will apply their results on averaging to devise efficient algorithms for the traffic assignment problem and in computing economic equilibria. Fixed point and variational inequality problems are pervasive in the fields of engineering, economics and operations research. They arise in such diverse areas as differential equations, game theory, optimization, decision analysis, and extreme value theory, to name a few. This research holds the potential for significant advances in both the theory and computational solution of this class of problems. It builds an important foundation for the analysis of network equilibria. In engineering, it should ultimately find useful applications in the design and operation of transportation and telecommunications networks.
