×

Korpelevich’s method for variational inequality problems in Banach spaces. (English) Zbl 1226.49010

Summary: We propose a variant of Korpelevich’s method for solving variational inequality problems with operators in Banach spaces. A full convergence analysis of the method is presented under reasonable assumptions on the problem data.

MSC:

49J40 Variational inequalities
47J25 Iterative procedures involving nonlinear operators
49M30 Other numerical methods in calculus of variations (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Armijo L.: Minimization of functions having continuous partial derivatives. Pac. J. Math. 16, 1–3 (1966) · Zbl 0202.46105 · doi:10.2140/pjm.1966.16.1
[2] Alber Y.I.: Metric and generalized projection operators in Banach spaces: properties and applications, Theory and applications of nonlinear operators of accretive and monotone type. Lect. Notes Pure Appl. Math. 178, 15–50 (1996) · Zbl 0883.47083
[3] Alber Y.I.: On average convergence of the iterative projection methods. Taiwan. J. Math. 6, 323–341 (2002) · Zbl 1021.90041
[4] Auslender A., Teboulle M.: Interior projection-like methods for monotone variational inequalities. Math. Program. 104, 39–68 (2005) · Zbl 1159.90517 · doi:10.1007/s10107-004-0568-x
[5] Balaj M., O’Regan D.: A generalized quasi-equilibrium problem. In: Pardalos, P.M., Rassias, T.M., Kahn, A.A. (eds) Nonlinear Analysis and Variational Problems, pp. 201–210. Springer, Berlin (2010) · Zbl 1182.49004
[6] Bao T.Q., Khanh P.Q.: A projection-type algorithm for pseudomonotone nonlipschitzian multivalued variational inequalities. Nonconvex Optim. Appl. 77, 113–129 (2005) · Zbl 1066.65068
[7] Bao T.Q., Khanh P.Q.: Some algorithms for solving mixed variational inequalities. Acta Math. Vietnam. 31, 83–103 (2006)
[8] Bertsekas D.P., Tsitsiklis J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice Hall, New Jersey (1989) · Zbl 0743.65107
[9] Breton M., Zaccour G., Zahaf M.: A differential game of joint implementation of environmental projects. Automatica 41, 1737–1749 (2005) · Zbl 1125.91309 · doi:10.1016/j.automatica.2005.05.004
[10] Butnariu D., Iusem A.N.: Totally Convex Functions for Fixed Points Computation and Infinite Dimensional Optimization. Kluwer, Dordrecht (2000) · Zbl 0960.90092
[11] Butnariu, D., Resmerita, E.: Bregman distances, totally convex functions and a method for solving operator equations in Banach spaces. Abstract and Applied Analysis (2006) Art. ID 84919 · Zbl 1130.47046
[12] Cioranescu I.: Geometry of Banach Spaces, Duality Mappings, and Nonlinear Problems. Kluwer, Dordrecht (1990) · Zbl 0712.47043
[13] Facchinei F., Fischer A., Piccialli V.: On generalized Nash games and variational inequalities. Oper. Res. Lett. 35, 159–164 (2007) · Zbl 1303.91020 · doi:10.1016/j.orl.2006.03.004
[14] Fang S.-C.: An iterative method for generalized complementarity problems. IEEE Trans. Automat. Contr. 25, 1225–1227 (1980) · Zbl 0483.49027 · doi:10.1109/TAC.1980.1102537
[15] Golshtein E.G., Tretyakov N.V.: Modified Lagrangians and Monotone Maps in Optimization. Wiley, New York (1996) · Zbl 0848.49001
[16] He B.S.: A new method for a class of variational inequalities. Math. Program. 66, 137–144 (1994) · Zbl 0813.49009 · doi:10.1007/BF01581141
[17] Iiduka H., Takahashi W.: Weak convergence of a projection algorithm for variational inequalities in a Banach space. J. Math. Anal. Appl. 339, 668–679 (2008) · Zbl 1129.49012 · doi:10.1016/j.jmaa.2007.07.019
[18] Iusem A.N.: An iterative algorithm for the variational inequality problem. Comput. Appl. Math. 13, 103–114 (1994) · Zbl 0811.65049
[19] Iusem A.N., Gárciga Otero R.: Inexact versions of proximal point and augmented Lagrangian algorithms in Banach spaces. Numer. Funct. Anal. Optim. 22, 609–640 (2001) · Zbl 1018.90067 · doi:10.1081/NFA-100105310
[20] Iusem A.N., Lucambio Pérez L.R.: An extragradient-type algorithm for non-smooth variational inequalities. Optimization 48, 309–332 (2000) · Zbl 0979.49009 · doi:10.1080/02331930008844508
[21] Iusem A.N., Svaiter B.F.: A variant of Korpelevich’s method for variational inequalities with a new search strategy. Optimization 42, 309–321 (1997) · Zbl 0891.90135 · doi:10.1080/02331939708844365
[22] Jørgensen S., Zaccour G.: Developments in differential game theory and numerical methods: economic and management applications. Comput. Manage. Sci. 4, 159–181 (2007) · Zbl 1134.91334 · doi:10.1007/s10287-006-0032-x
[23] Khobotov E.N.: Modifications of the extragradient method for solving variational inequalities and certain optimization problems. USSR Comput. Math. Math. Phys. 27, 120–127 (1987) · Zbl 0665.90078 · doi:10.1016/0041-5553(87)90058-9
[24] Kinderlehrer D., Stampacchia G.: An Introduction to Variational Inequalities and Their Applications. Academic Press, New York (1980) · Zbl 0457.35001
[25] Konnov I.V.: Combined relaxation methods for finding equilibrium points and solving related problems. Russ. Math. 37, 34–51 (1993) · Zbl 0835.90123
[26] Konnov I.V.: On combined relaxation methods’ convergence rates. Russ. Math. 37, 89–92 (1993) · Zbl 0842.90108
[27] Konnov I.V.: Combined Relaxation Methods for Variational Inequalities. Springer, Berlin (2001) · Zbl 0982.49009
[28] Korpelevich G.M.: The extragradient method for finding saddle points and other problems. Ekonomika i Matematcheskie Metody 12, 747–756 (1976) · Zbl 0342.90044
[29] Lin L.J., Yang M.F., Ansari Q.H., Kassay G.: Existence results for Stampacchia and Minty type implicit variational inequalities with multivalued maps. Nonlinear Anal. Theory Methods Appl. 61, 1–19 (2005) · Zbl 1065.49008 · doi:10.1016/j.na.2004.07.038
[30] Marcotte P.: Application of Khobotov’s algorithm to variational inequalities and network equilibrium problems. Inf. Syst. Oper. Res. 29, 258–270 (1991) · Zbl 0781.90086
[31] Nagurney A.: Variational inequalities. In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopaedia of Optimization, Part 22, pp. 3989–3994. Springer, Berlin (2009)
[32] Nemirovskii A.S.: Effective iterative methods for solving equations with monotone operators. Ekonomika i Mathematcheskie Metody 17, 344–359 (1981)
[33] Nemirovskii A.S.: A prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Contr. Optim. 15, 229–251 (2004) · Zbl 1106.90059
[34] Robinson S.M., Lu S.: Solution continuity in variational conditions. J. Global Optim. 40, 405–415 (2008) · Zbl 1145.90096 · doi:10.1007/s10898-007-9192-7
[35] Rosen J.B.: Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33, 520–534 (1965) · Zbl 0142.17603 · doi:10.2307/1911749
[36] Shor N.Z.: New development trends in nonsmooth optimization methods. Cybernetics 6, 87–91 (1967) · Zbl 0377.90084
[37] Solodov M.V., Svaiter B.F.: A new projection method for variational inequality problems. SIAM J. Contr. Optim. 37, 765–776 (1999) · Zbl 0959.49007 · doi:10.1137/S0363012997317475
[38] Solodov M.V., Tseng P.: Modified projection-type methods for monotone variational inequalities. SIAM J. Contr. Optim. 34, 1814–1830 (1996) · Zbl 0866.49018 · doi:10.1137/S0363012994268655
[39] Takahashi W.: Nonlinear Functional Analysis. Yokohama Publishers, Yokohama (2000) · Zbl 0997.47002
[40] Williams R.J.: Sufficient conditions for Nash equilibria in N-person games over reflexive Banach spaces. J. Optim. Theory Appl. 30, 383–394 (1980) · Zbl 0431.90088 · doi:10.1007/BF00935494
[41] Zeidler E.: Nonlinear Functional Analysis and its Applications I. Springer, New York (1985) · Zbl 0583.47051
[42] Zhu D.L., Marcotte P.: Convergence properties of feasible descent methods for solving variational inequalities in Banach spaces. Comput. Optim. Appl. 10, 35–49 (1998) · Zbl 0904.90164 · doi:10.1023/A:1018387816972
[43] Zukhovitskii R.A., Poliak R.A., Primak M.E.: Two methods of search for equilibrium points of n-person concave games. Soviet Math. Doklady 10, 279–282 (1969) · Zbl 0191.49801
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.