Abstract.
We introduce a general adaptive line search framework for solving fixed point and variational inequality problems. Our goals are to develop iterative schemes that (i) compute solutions when the underlying map satisfies properties weaker than contractiveness, for example, weaker forms of nonexpansiveness, (ii) are more efficient than the classical methods even when the underlying map is contractive, and (iii) unify and extend several convergence results from the fixed point and variational inequality literatures. To achieve these goals, we introduce and study joint compatibility conditions imposed upon the underlying map and the iterative step sizes at each iteration and consider line searches that optimize certain potential functions. As a special case, we introduce a modified steepest descent method for solving systems of equations that does not require a previous condition from the literature (the square of the Jacobian matrix is positive definite). Since the line searches we propose might be difficult to perform exactly, we also consider inexact line searches.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Baillon, J.B.: Un theoreme de type ergodique pour les contractions non lineaires dans un espace de Hilbert. C.R. Acad. Sc., Serie A, Paris t.28, 1511–1514 (1975)
Bertsekas, D.P.: Nonlinear programming. Athena Scientific, Belmont, MA (1996)
Bottom, J.(1998): Generation of Anticipatory Route Guidance, presentation in TRISTAN III, Triennial Symposium on Transportation Analysis, San Juan, Puerto Rico, also in Optimization Days, Montreal, May 1999
Bottom, J., Ben-Akiva, M., Bierlaire, M., Chabini, I., Koutsopoulos, H., Yang, Q.: Investigation of route guidance generation issues by simulation with DynaMIT”, to appear in Proceedings of 14th International Symposium on Transportation and Traffic Theory, Jerusalem (1999)
Browder, F.E.: Convergence of approximants to fixed points of nonexpansive nonlinear mappings in Banach spaces. Arch. Rational Mech. Anal. 24, 82–90 (1967)
Browder, F.E., Petryshn, W.V.: Construction of fixed points of nonlinear mappings in a Hilbert space. Journal of Analysis and Applications 20, 197–228 (1967)
Bruck, Jr. R.E.: The iterative solution of the equation y ∈x+T(x) for a maximal monotone map T in Hilbert space. Journal of Mathematical Analysis and Applications 48, 114–126 (1973)
Bruck, Jr. R.E. : On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space. Journal of Mathematical Analysis and Applications 61, 159–164 (1977)
Calamai, P.H., More, J.J.: Projected gradient methods for linearly constrained problems. Mathematical Programming 39, 93–116 (1987)
Christodouleas, J.: Applications of fixed point problems in scheduling. Private communication (1996)
Dafermos, S.C.: An iterative scheme for variational inequalities. Mathematical Programming 26, 40–47 (1983)
Dunn, J.C.: On recursive averaging processes and Hilbert space extensions of the contraction mapping principle. Journal of the Franklin Institute 295, 117–133 (1973)
Dunn, J.C.: Convergence rates for conditional gradient sequences generated by implicit step length rules. SIAM Journal on Control and Optimization 18 (5), 473–487 (1980)
Dunn, J.C.: Newton’s method and the Goldstein step length rue for constrained minimization problems. SIAM Journal on Control and Optimization 18, 659–674 (1980)
Dunn, J.C.: Global and asymptotic convergence rate estimates for a class of projected gradient processes. SIAM Journal on Control and Optimization 19 (3), 368–400 (1981)
Dunn, J.C., Harshbarger, S.: Conditional gradient algorithms with open loop step size rules. Journal of Mathematical Analysis and Applications 62, 432–444 (1978)
Eckstein, J., Bertsekas, D. P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming 55, 293–318 (1992)
Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Volumes I and II, Springer Verlag, Berlin (2003)
Florian, M., Hearn, D.: Network Equilibria. Handbook of Operations Research and Management Science. Volume Network Routing (M. Ball, T. Magnanti, C. Monma and G. Nemhauser eds.), Elsevier (1995)
M. Fukushima: Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Mathematical Programming 53 (1), 99–110 (1992)
Gabay, D.: Applications of the method of multipliers to variational inequalities, in M. Fortin, R. Glowinski, eds., Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, North-Holland, Amsterdam (1983)
Halpern, B.: Fixed points of nonexpansive maps. Bulletin of the American Mathematical Society 73, 957–961 (1967)
Hammond, J.H., Magnanti, T.L.: Generalized descent methods for asymmetric systems of equations. Mathematics of Operations Research 12, 678–699 (1987)
Harker, P.T.: Lectures on computation of equilibria with equation-based methods. CORE Lecture Series, Center for Operations Research and Econometrics, University of Louvain, Louvain la Neuve, Belgium (1993)
Harker, P.T., Pang, J.S.: Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Mathematical Programming 48, 161–220 (1990)
Hoang, T.: Computing fixed points by global optimization methods, in Fixed point theory and applications M.A. Thera and J-B Baillon Eds. 231–244 (1991)
Ishikawa, S.: Fixed points and iteration of a nonexpansive mapping in a Banach space. Proceedings of the American Mathematical Society 59 (1), 65–71 (1976)
Itoh, T., Fukushima, M., Ibaraki, T.: An iterative method for variational inequalities with application to traffic equilibrium problems. Journal of the Operations Research Society of Japan 31 (1), 82–103 (1988)
Kaniel, S.: Construction of a fixed point for contractions in banach space. Israel J. Math. 9, 535–540 (1971)
Kinderlehrer, D., Stampacchia, G.: An introduction to variational inequalities and their application. Academic Press, New York (1980)
Knopp, K.: Theory and application of infinite series. Hafner Publishing Company N.Y. (1947)
Kolmogorov, A.N., Fomin, S.V.: Introduction to real analysis. Dover Publications, New York (1970)
Magnanti, T.L., Perakis, G.: A unifying geometric solution framework and complexity analysis for variational inequalities. Mathematical Programming 71, 327–351 (1995)
Magnanti, T.L., Perakis, G.: The orthogonality theorem and the strong-f-monotonicity condition for variational inequality algorithms. SIAM Journal of Optimization 7 (1), 248–273 (1997)
Magnanti, T.L., Perakis, G.: Averaging schemes for variational inequalities and systems of equations. Mathematics of Operations Research 22 (3), 568–587 (1997)
Mann, W.R.: On recursive averaging processes and Hilbert space extensions of a contraction mapping principle. Proceedings of the American Mathematical Society 4, 506–510 (1953)
Marcotte, P., Dussault, J-P: A note on a globally convergent Newton method for solving monotone variational inequalities. Operations Research Letters 6 (1), 35–42 (1987)
Marcotte, P., Wu, J.H.: On the convergence of projection methods: application to the decomposition of affine variational inequalities. JOTA 85 (2), 347–362 (1995)
Nagurney, A.: Network Economics. Kluwer Academic Publishers, Boston (1993)
Opial, Z.: Weak convergence of the successive approximation for non-expansive mappings in Banach Spaces. Bulletin A.M.S. 73, 123–135 (1967)
Ortega, J.M., Rheinboldt, W.C.: Iterative solution of nonlinear equations in several variables. Academic Press , New York (1970)
Pang, J.S., Chan, D.: Iterative methods for variational and complementarity problems. Mathematical Programming 24, 284–313 (1982)
Pang, J.S.: Complementarity problems. Handbook of Global Optimization, eds. R. Horst and P. Pardalos, 271–329, Kluwer Academic Publishers. (1994)
Passty, G.B.: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space. Journal of Mathematical Analysis and Applications 72, 383–390 (1979)
Rockafellar, R.T.: Monotone operators and the proximal algorithm. SIAM Journal on Control and Optimization 14, 877–898 (1976)
Sibony, M.: Methodes iteratives pour les equations et inequations aux derivees partielles nonlinearies de type monotone. Calcolo 7, 65–183 (1970)
Sine, R.C.: Fixed Points and Nonexpansive Mappings. Contemporary Mathematics, 18, American Mathematical Society (1983)
Sun, J.: An affine scaling method for linearly constrained convex programs. Preprint, Department of Industrial Engineering and Management Sciences, Northwestern University (1990)
Taji, K., Fukushima, M., Ibaraki, T.: A globally convergent Newton method for solving strongly monotone variational inequalities. Mathematical Programming 58 (3), 369–383 (1993)
Todd, M.J.: The computation of fixed points and applications. Lecture Notes in Economics and Mathematical Systems 124, Springer-Verlag (1976)
Tseng, P.: Further applications of a matrix splitting algorithm to decomposition in variational inequalities and convex programming. Mathematical Programming 48, 249–264 (1990)
Tseng, P., Bertsekas, D.P., Tsitsiklis, J.N.: Partially asynchronous, parallel algorithms for network flow problems and other problems. SIAM Journal on Control and Optimization 28 (3), 678–710 (1990)
Wu, J.H., Florian, M., Marcotte, P.: A general descent framework for the monotone variational inequality problem. Mathematical Programming 61 (3), 281–300 (1993)
Zhu, D.L., Marcotte, P.: Co-coercivity and its role in the convergence of iterative schemes for solving variational inequalities. SIAM Journal on Optimization 3 (6), 714–726(1996)
Zhu, D.L., Marcotte, P.: Modified descent methods for solving the monotone variational inequality problem. Operations Research Letters 14 (2), 111–120 (1993)
Author information
Authors and Affiliations
Additional information
Preparation of this paper was supported, in part, from the National Science Foundation NSF Grant 9634736-DMI, as well as the Singapore-MIT Alliance
Acknowledgments.We are grateful to the associate editor and the referees for their insightful comments and suggestions that have helped us improve both the exposition and the content of this paper.
Rights and permissions
About this article
Cite this article
Magnanti, T., Perakis, G. Solving variational inequality and fixed point problems by line searches and potential optimization. Math. Program., Ser. A 101, 435–461 (2004). https://doi.org/10.1007/s10107-003-0476-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-003-0476-5