A unifying geometric solution framework and complexity analysis for variational inequalities |
| |
Authors: | Thomas L. Magnanti Georgia Perakis |
| |
Affiliation: | (1) Sloan School of Management and School of Engineering, MIT, 02139 Cambridge, MA, USA;(2) Operations Research Center, MIT, 02139 Cambridge, MA, USA |
| |
Abstract: | In this paper, we propose a concept of polynomiality for variational inequality problems and show how to find a near optimal solution of variational inequality problems in a polynomial number of iterations. To establish this result, we build upon insights from several algorithms for linear and nonlinear programs (the ellipsoid algorithm, the method of centers of gravity, the method of inscribed ellipsoids, and Vaidya's algorithm) to develop a unifying geometric framework for solving variational inequality problems. The analysis rests upon the assumption of strong-f-monotonicity, which is weaker than strict and strong monotonicity. Since linear programs satisfy this assumption, the general framework applies to linear programs.Preparation of this paper was supported, in part, by NSF Grant 9312971-DDM from the National Science Foundation. |
| |
Keywords: | Variational inequalities Nonlinear programming Complexity analysis Monotone operators |
本文献已被 SpringerLink 等数据库收录! |
|