Combined Relaxation Methods for Variational Inequalities (Lecture Notes in Economics and Mathematical Systems Book 495)

Variational inequalities proved to be a very useful tool for investigation and solution of various equilibrium type problems arising in Economics, Operations Research, Mathematical Physics, and Transportation. This book is devoted to a new general approach to constructing solution methods for variational inequalities, which was called the combined relaxation approach. This approach is rather flexible and allows one to construct various methods both for single-valued and for multi-valued variational inequalities, including nonlinear constrained problems. The other essential feature of the combined relaxation methods is that they are convergent under very mild assumptions. The book can be viewed as an attempt to discribe the existing combined relaxation methods as a whole. Cover......Page 1 Title Page......Page 4 Copyright Page......Page 5 Dedication......Page 6 Preface......Page 8 Table of Contents......Page 10 Notation and Convention......Page 14 1.1.1 Existence and Uniqueness Results......Page 16 1.1.2 Variational Inequalities and Related Problems......Page 21 1.2.1 Newton-like Iterations......Page 28 1.2.2 Basic Properties of CR Methods......Page 32 1.3.1 A CR Method and its Properties......Page 37 1.3.2 Convergence and Rates of Convergence......Page 39 1.3.3 A Modified Line Search......Page 45 1.3.4 Acceleration Techniques for CR Methods......Page 48 1.4.1 A Modified Rule for Computing the Stepsize......Page 51 1.4.2 A Modified Rule for Computing the Descent Direction......Page 55 1.5.1 Description of the Method......Page 60 1.5.2 Convergence......Page 61 1.6.1 A Modified Basic Scheme for CR Methods......Page 63 1.6.2 Description of the Method......Page 64 1.6.3 Convergence......Page 66 2.1.1 Existence and Uniqueness Results......Page 70 2.1.2 Generalized Variational Inequalities and Related Problems......Page 73 2.1.3 Equilibrium and Mixed Variational Inequality Problems......Page 78 2.2.1 Description of the Method......Page 85 2.2.2 Convergence......Page 87 2.2.3 Rate of Convergence......Page 90 2.3.1 Description of the Method......Page 93 2.3.2 Properties of Auxiliary Mappings......Page 95 2.3.3 Convergence......Page 96 2.3.4 Complexity Estimates......Page 98 2.3.5 Modifications......Page 105 2.4.1 An Inexact CR Method for Multivalued Inclusions......Page 108 2.4.2 Convergence......Page 110 2.5 Decomposable CR Method......Page 114 2.5.1 Properties of Auxiliary Mappings......Page 115 2.5.2 Description of the Method......Page 117 2.5.3 Convergence......Page 119 3.1.1 The Proximal Point Method......Page 122 3.1.2 Regularization and Averaging Methods......Page 125 3.1.3 The Ellipsoid Method......Page 127 3.1.4 The Extragradient Method......Page 129 3.2.1 Economic Equilibrium Models as Complementarity Problems......Page 131 3.2.2 Economic Equilibrium Models with Monotone Mappings......Page 132 3.2.3 The Linear Exchange Model......Page 134 3.2.4 The General Equilibrium Model......Page 139 3.2.5 The Oligopolistic Equilibrium Model......Page 141 3.3.1 Systems of Linear Equations......Page 146 3.3.2 Linear Complementarity Problems......Page 147 3.3.3 Linear Variational Inequalities......Page 149 3.3.4 Nonlinear Complementarity Problems......Page 151 3.3.5 Nonlinear Variational Inequalities......Page 153 4.1.1 Exterior Point Algorithms......Page 156 4.1.2 Feasible Point Algorithms......Page 158 4.2.1 Preliminaries......Page 163 4.2.2 Error Bounds......Page 165 4.3.1 Description of the Method......Page 167 4.3.2 Convergence......Page 168 4.3.3 Rate of Convergence......Page 172 Bibliographical Notes......Page 174 References......Page 180 Index......Page 192 Variational inequalities proved to be a very useful and powerful tool for in­ vestigation and solution of many equilibrium type problems in Economics, Engineering, Operations Research and Mathematical Physics. In fact, varia­ tional inequalities for example provide a unifying framework for the study of such diverse problems as boundary value problems, price equilibrium prob­ lems and traffic network equilibrium problems. Besides, they are closely re­ lated with many general problems of Nonlinear Analysis, such as fixed point, optimization and complementarity problems. As a result, the theory and so­ lution methods for variational inequalities have been studied extensively, and considerable advances have been made in these areas. This book is devoted to a new general approach to constructing solution methods for variational inequalities, which was called the combined relax­ ation (CR) approach. This approach is based on combining, modifying and generalizing ideas contained in various relaxation methods. In fact, each com­ bined relaxation method has a two-level structure, i.e., a descent direction and a stepsize at each iteration are computed by finite relaxation procedures. A text using a new general approach to construction solution methods for variational inequalities, based on combining modifying, and generalizing ideas contained in various relaxation methods. The new approach, termed combined relaxation, is explained and demonstrated. Softcover. In this chapter, we consider basic schemes of combined relaxation (CR) methods and implementable algorithms for solving variational inequality problems with continuous single-valued mappings under a finite-dimensional space setting.