×

zbMATH — the first resource for mathematics

Solving quasi-variational inequalities via their KKT conditions. (English) Zbl 1293.65100
The authors propose a totally different approach to the solution of quasi-variational inequalities (QVIs). Assuming that the feasible set mapping \(K(\cdot)\) is described by a finite number of parametric inequalities, the Karush-Kuhn-Tucker (KKT) conditions of the QVI is reformulated then as a system of constrained equations, and then an interior-point method is applied. Main result: The authors propose and analyze a globally convergent algorithm for the solution of a finite-dimensional QVI. The convergence is established for a wide array of different classes of problems including QVIs with the feasible set given by moving sets, linear systems with variable right-hand sides, box constraints with variable bounds, and bilinear constraints. These results surpass by far existing convergence analyses, the latter all having a somewhat limited scope. The results in this paper constitute an important step towards the development of theoretically reliable and numerically efficient methods for the solution of QVIs.

MSC:
65K15 Numerical methods for variational inequalities and related problems
49J40 Variational inequalities
49M37 Numerical methods based on nonlinear programming
90C51 Interior-point methods
Software:
PATH Solver; QVILIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baillon, J-B; Haddad, G, Quelques propriétés des opérateurs angle-bornés et n-cycliquement monotones, Isr. J. Math., 26, 137-150, (1977) · Zbl 0352.47023
[2] Baiocchi, C., Capelo, A.: Variational and Quasivariational Inequalities: Applications to Free Boundary Problems. Wiley, New York (1984) · Zbl 0551.49007
[3] Bensoussan, A, Points de Nash dans le cas de fonctionnelles quadratiques et jeux differentiels lineaires a N personnes, SIAM J. Control, 12, 460-499, (1974) · Zbl 0254.90066
[4] Bensoussan, A; Goursat, M; Lions, J-L, Contrôle impulsionnel et inéquations quasi-variationnelles stationnaires, C. R. Acad. Sci. Paris Sér. A, 276, 1279-1284, (1973) · Zbl 0264.49004
[5] Bensoussan, A; Lions, J-L, Nouvelle formulation de problèmes de contrôle impulsionnel et applications, C. R. Acad. Sci. Paris Sér. A, 276, 1189-1192, (1973) · Zbl 0266.49007
[6] Bensoussan, A; Lions, J-L, Nouvelles méthodes en contrôle impulsionnel, Appl. Math. Optim., 1, 289-312, (1975) · Zbl 0339.93033
[7] Beremlijski, P; Haslinger, J; Kočvara, M; Outrata, J, Shape optimization in contact problems with Coulomb friction, SIAM J. Optim., 13, 561-587, (2002) · Zbl 1025.49026
[8] Bliemer, M; Bovy, P, Quasi-variational inequality formulation of the multiclass dynamic traffic assignment problem, Transp. Res. B Methodol., 37, 501-519, (2003)
[9] Chan, D; Pang, J-S, The generalized quasi-variational inequality problem, Math. Oper. Res., 7, 211-222, (1982) · Zbl 0502.90080
[10] Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, New York (1992) · Zbl 0757.90078
[11] Luca, M; Maugeri, A; Giannessi, F (ed.), Discontinuous quasi-variational inequalities and applications to equilibrium problems, 70-75, (1992), Amsterdam · Zbl 1050.49502
[12] Dirkse, SP; Ferris, MC, The PATH solver: a non-monotone stabilization scheme for mixed complementarity problems, Optim. Methods Softw., 5, 123-156, (1995)
[13] Donato, MB; Milasi, M; Vitanza, C, An existence result of a quasi-variational inequality associated to an equilibrium problem, J. Glob. Optim., 40, 87-97, (2008) · Zbl 1295.49007
[14] Dreves, A; Facchinei, F; Kanzow, C; Sagratella, S, On the solution of the KKT conditions of generalized Nash equilibrium problems, SIAM J. Optim., 21, 1082-1108, (2011) · Zbl 1230.90176
[15] Facchinei, F; Kanzow, C, Penalty methods for the solution of generalized Nash equilibrium problems, SIAM J. Optim., 20, 2228-2253, (2010) · Zbl 1211.90228
[16] Facchinei, F; Kanzow, C, Generalized Nash equilibrium problems, Ann. Oper. Res., 175, 177-211, (2010) · Zbl 1185.91016
[17] Facchinei, F., Kanzow, C., Sagratella, S.: QVILIB: A library of quasi-variational inequality test problems. To appear in Pac. J. Optim. · Zbl 1267.65078
[18] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vols. I and II. Springer, New York (2003) · Zbl 1062.90002
[19] Ferris, MC; Munson, TS, Interfaces to PATH 3.0: design, implementation and usage, Comput. Optim. Appl., 12, 207-227, (1999) · Zbl 1040.90549
[20] Fukushima, M, A class of gap functions for quasi-variational inequality problems, J. Ind. Manag. Optim., 3, 165-171, (2007) · Zbl 1170.90487
[21] Glowinski, R.: Numerical methods for variational inequalities. Springer, Berlin (2008, reprint of the 1984 edition) · Zbl 1139.65050
[22] Glowinski, R., Lions, J.L., Trémolières, R.: Numerical Analysis of Variational Inequalities. North-Holland, Amsterdam (1981) · Zbl 0463.65046
[23] Hammerstein, P; Selten, R; Aumann, RJ (ed.); Hart, S (ed.), Game theory and evolutionary biology, No. 2, 929-993, (1994), Amsterdam · Zbl 0925.90088
[24] Harker, PT, Generalized Nash games and quasi-variational inequalities, Eur. J. Oper. Res., 54, 81-94, (1991) · Zbl 0754.90070
[25] Haslinger, J; Panagiotopoulos, PD, The reciprocal variational approach to the Signorini problem with friction. approximation results, Proc. R. Soc. Edinb. Sect. A Math., 98, 365-383, (1984) · Zbl 0547.73096
[26] Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1990) · Zbl 0704.15002
[27] Ichiishi, T.: Game Theory for Economic Analysis. Academic Press, New York (1983) · Zbl 0522.90104
[28] Kharroubi, I; Ma, J; Pham, H; Zhang, J, Backward SDEs with constrained jumps and quasi-variational inequalities, Ann. Probab., 38, 794-840, (2010) · Zbl 1205.60114
[29] Kravchuk, A.S., Neittaanmaki, P.J.: Variational and Quasi-variational Inequalities in Mechanics. Springer, Dordrecht (2007) · Zbl 1131.49001
[30] Kubota, K; Fukushima, M, Gap function approach to the generalized Nash equilibrium problem, J. Optim. Theory Appl., 144, 511-531, (2010) · Zbl 1188.91021
[31] Kunze, M; Rodrigues, JF, An elliptic quasi-variational inequality with gradient constraints and some of its applications, Math. Methods Appl. Sci., 23, 897-908, (2000) · Zbl 0956.35059
[32] Monteiro, RDC; Pang, J-S, A potential reduction Newton method for constrained equations, SIAM J. Optim., 9, 729-754, (1999) · Zbl 0958.65069
[33] Mosco, U.: Implicit variational problems and quasi variational inequalities. In: Gossez, J., Lami Dozo, E., Mawhin, J., Waelbroeck, L. (eds.) Nonlinear Operators and the Calculus of Variations, Lecture Notes in Mathematics, vol. 543, pp. 83-156. Springer, Berlin (1976) · Zbl 0339.93033
[34] Nesterov, Y., Scrimali, L.: Solving strongly monotone variational and quasi-variational inequalities. CORE discussion paper 2006/107, Catholic University of Louvain, Center for Operations Research and Econometrics (2006) · Zbl 1238.49019
[35] Noor, MA, On general quasi-variational inequalities, J. King Saud Univ., 24, 81-88, (2012)
[36] Noor, MA, An iterative scheme for a class of quasi variational inequalities, J. Math. Anal. Appl., 110, 463-468, (1985) · Zbl 0581.65051
[37] Ortega, J.M., Rheinboldt, J.C.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York (1970). (reprinted by SIAM, Philadelphia (2000)) · Zbl 0241.65046
[38] Outrata, J; Kocvara, M, On a class of quasi-variational inequalities, Optim. Methods Softw., 5, 275-295, (1995)
[39] Outrata, J., Kocvara, M., Zowe, J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints. Kluwer, Dordrecht (1998) · Zbl 0947.90093
[40] Outrata, J; Zowe, J, A Newton method for a class of quasi-variational inequalities, Comput. Optim. Appl., 4, 5-21, (1995) · Zbl 0827.49007
[41] Pang, J-S; Mangasarian, OL (ed.); Meyer, RR (ed.); Robinson, SM (ed.), The implicit complementarity problem, 487-518, (1981), New York
[42] Pang, J-S, On the convergence of a basic iterative method for the implicit complementarity problem, J. Optim. Theory Appl., 37, 149-162, (1982) · Zbl 0482.90084
[43] Pang, J-S, Error bounds in mathematical programming, Math. Program., 79, 299-332, (1997) · Zbl 0887.90165
[44] Pang, J.-S., Fukushima, M.: Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Computational Management Science 2, 21-56 (2005) [Erratum: ibid 6, 373-375 (2009)] · Zbl 1115.90059
[45] Ryazantseva, IP, First-order methods for certain quasi-variational inequalities in Hilbert space, Comput. Math. Math. Phys, 47, 183-190, (2007) · Zbl 1210.39028
[46] Scrimali, L.: Quasi-variational inequality formulation of the mixed equilibrium in mixed multiclass routing games. CORE discussion paper 2007/7, Catholic University of Louvain, Center for Operations Research and Econometrics (2007) · Zbl 1040.90549
[47] Siddiqi, AH; Ansari, QH, Strongly nonlinear quasivariational inequalities, J. Math. Anal. Appl., 149, 444-450, (1990) · Zbl 0712.49009
[48] Wei, JY; Smeers, Y, Spatial oligopolistic electricity models with Cournot generators and regulated transmission prices, Oper. Res., 47, 102-112, (1999) · Zbl 1175.91080
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.