Article Contents
Article Contents

# An improved projection algorithm for variational inequality problem with multivalued mapping

•
• In this paper, we propose a new projection method (extragradient method) for solving the generalized variational inequality problem. Our method is well-defined and is proven to be globally convergent to a solution of the problem under the assumptions that the multivalued mapping is continuous and satisfies a condition that is strictly weaker than the pseudomonotonicity. Finally, to support our results and to illustrate the numerical behavior of the proposed algorithm, some fundamental experiments are provided and also compared with recent works.

Mathematics Subject Classification: Primary: 65K05, 65K15, 90C33.

 Citation:

• Table 1.  Example 1

 Alg1 Alg1' $n$ $x^{0}$ $Iter$ $cpu$ $\beta$ $\lambda$ $Iter$ $cpu$ $\beta$ $\lambda$ $(1/n, ..., 1/n)$ $05$ $0.0933$ $2.3$ $30$ $05$ $0.1013$ $4.6$ $30$ $10$ $(1, ..., 1)$ $05$ $0.07693$ $2.3$ $30$ $05$ $0.1084$ $4.6$ $30$ $(-2, ..., -2)$ $05$ $0.1752$ $2.3$ $30$ $05$ $0.1502$ $4.6$ $30$ $(1/n, ..., 1/n)$ $08$ $0.4548$ $4.6$ $30$ $05$ $0.3672$ $1.3$ $600$ $50$ $(1, ..., 1)$ $09$ $0.5292$ $2.3$ $25$ $05$ $0.3637$ $1.3$ $600$ $(-2, ..., -2)$ $25$ $2.9980$ $2.3$ $30$ $25$ $2.7703$ $03$ $04$ $(1/n, ..., 1/n)$ $19$ $4.6537$ $3.3$ $30$ $18$ $4.7851$ $1.3$ $30$ $100$ $(1, ..., 1)$ $08$ $1.2500$ $5.3$ $30$ $18$ $4.9539$ $1.3$ $30$ $(-2, ..., -2)$ $50$ $17.3849$ $1.5$ $30$ $50$ $18.6507$ $1.3$ $30$ $(1/n, ..., 1/n)$ $84$ $122.7375$ $1.5$ $30$ $07$ $4.7840$ $4.6$ $30$ $200$ $(1, ..., 1)$ $88$ $133.7441$ $3.3$ $30$ $07$ $4.8564$ $4.6$ $30$ $(-2, ..., -2)$ $100$ $167.8360$ $3.3$ $30$ $100$ $165.3262$ $03$ $30$

Table 2.  Example 1

 Alg2 Alg2' $n$ $x^{0}$ $Iter$ $cpu$ $\beta$ $\theta$ $Iter$ $cpu$ $\beta$ $\theta$ $(1/n, ..., 1/n)$ $10$ $0.1044$ $09$ $0.01$ $10$ $0.2166$ $7.2$ $0.01$ $10$ $(1, ..., 1)$ $10$ $0.2146$ $05$ $0.01$ $10$ $0.2255$ $2.8$ $0.01$ $(-2, ..., -2)$ $13$ $0.2455$ $09$ $0.01$ $13$ $0.2849$ $8.1$ $0.01$ $(1/n, ..., 1/n)$ $25$ $0.7580$ $8.1$ $0.01$ $28$ $1.7506$ $4.3$ $0.01$ $50$ $(1, ..., 1)$ $27$ $1.6024$ $5.5$ $0.001$ $27$ $1.9405$ $8.3$ $0.01$ $(-2, ..., -2)$ $53$ $4.5289$ $09$ $0.01$ $53$ $5.6964$ $4.3$ $0.01$ $(1/n, ..., 1/n)$ $43$ $9.9579$ $6.1$ $0.01$ $43$ $9.2976$ $3.3$ $0.01$ $100$ $(1, ..., 1)$ $32$ $6.6368$ $6.9$ $0.01$ $45$ $13.3148$ $34$ $0.01$ $(-2, ..., -2)$ $103$ $33.9310$ $6.1$ $0.01$ $103$ $35.7461$ $34$ $0.01$ $(1/n, ..., 1/n)$ $116$ $179.6938$ $6.6$ $0.01$ $116$ $181.6362$ $6.6$ $0.01$ $200$ $(1, ..., 1)$ $113$ $159.2788$ $3.4$ $0.01$ $112$ $161.1741$ $3.4$ $0.01$ $(-2, ..., -2)$ $203$ $369.6150$ $6.6$ $0.01$ $203$ $358.1106$ $6.6$ $0.01$

Table 3.  Example 1

 Alg3 $n$ $x_{0}$ $Iter$ $cpu$ $l$ $(1/n, \ldots , 1/n)$ $35$ $1.7592$ $0.95$ $10$ $(1, \ldots , 1)$ $44$ $1.6183$ $0.95$ $(-2, \ldots , -2)$ $43$ $1.7283$ $0.95$ $(1/n, \ldots , 1/n)$ $64$ $12.3182$ $0.95$ $50$ $(1, \ldots , 1)$ $129$ $14.9710$ $0.9$ $(-2, \ldots , -2)$ $127$ $15.1543$ $0.9$ $(1/n, \ldots , 1/n)$ $90$ $37.3068$ $0.95$ $100$ $(1, \ldots , 1)$ $214$ $82.9337$ $0.95$ $(-2, \ldots , -2)$ $213$ $88.2488$ $0.95$ $(1/n, \ldots , 1/n)$ $122$ $226.3886$ $0.95$ $200$ $(1, \ldots , 1)$ $390$ $687.8674$ $0.95$ $(-2, \ldots , -2)$ $391$ $718.4568$ $0.95$

Table 4.  Example 2

 Alg1 Alg1' $n$ $x^{0}$ $Iter$ $cpu$ $\beta$ $\lambda$ $Iter$ $cpu$ $\beta$ $\lambda$ $(1, ..., 1)$ $05$ $0.1080$ $2.5$ $02$ $04$ $0.1173$ $01$ $90$ $10$ $(0.9, ..., 0.9)$ $01$ $0.0194$ $09$ $02$ $01$ $0.0375$ $01$ $90$ $(-2, ..., -2)$ $01$ $0.0571$ $0.2$ $02$ $01$ $0.0404$ $01$ $90$ $(1, ..., 1)$ $08$ $0.2907$ $0.2$ $90$ $07$ $0.2838$ $04$ $90$ $100$ $(0.9, ..., 0.9)$ $01$ $0.0498$ $0.2$ $90$ $01$ $0.0490$ $01$ $90$ $(-2, ..., -2)$ $01$ $0.1063$ $0.2$ $90$ $01$ $0.0698$ $01$ $90$ $(1, ..., 1)$ $08$ $0.4193$ $0.2$ $90$ $06$ $1.6353$ $05$ $90$ $500$ $(0.9, ..., 0.9)$ $01$ $0.0781$ $0.2$ $90$ $01$ $0.2545$ $01$ $90$ $(-2, ..., -2)$ $01$ $0.2038$ $0.2$ $90$ $01$ $0.3603$ $01$ $90$ $(1, ..., 1)$ $08$ $0.9780$ $0.2$ $90$ $06$ $8.0998$ $05$ $90$ $1000$ $(0.9, ..., 0.9)$ $01$ $0.1478$ $0.2$ $90$ $01$ $1.2334$ $01$ $90$ $(-2, ..., -2)$ $01$ $0.9753$ $0.2$ $90$ $01$ $2.1603$ $01$ $90$ $(1, ..., 1)$ $08$ $2.9927$ $0.2$ $90$ $06$ $51.5017$ $5.5$ $90$ $2000$ $(0.9, ..., 0.9)$ $01$ $0.3171$ $0.2$ $90$ $01$ $8.6067$ $05$ $90$ $(-2, ..., -2)$ $01$ $1.5950$ $0.2$ $90$ $01$ $11.3070$ $05$ $90$

Table 5.  Example 2

 Alg2 Alg2' $n$ $x^{0}$ $Iter$ $cpu$ $\beta$ $\theta$ $Iter$ $cpu$ $\beta$ $\theta$ $(1, ..., 1)$ $06$ $0.1537$ $15$ $0.1$ $06$ $0.1133$ $09$ $0.1$ $10$ $(0.9, ..., 0.9)$ $01$ $0.0505$ $15$ $0.1$ $01$ $0.0157$ $09$ $0.1$ $(-2, ..., -2)$ $01$ $0.0579$ $15$ $0.1$ $01$ $0.0521$ $09$ $0.1$ $(1, ..., 1)$ $42$ $3.5722$ $1.5$ $0.1$ $09$ $0.6863$ $190$ $0.3$ $100$ $(0.9, ..., 0.9)$ $01$ $0.0605$ $15$ $0.1$ $01$ $0.0745$ $09$ $0.3$ $(-2, ..., -2)$ $01$ $0.0493$ $15$ $0.1$ $01$ $0.1952$ $90$ $0.3$ $(1, ..., 1)$ $41$ $72.716$ $1.5$ $0.1$ $09$ $17.1776$ $190$ $0.3$ $500$ $(0.9, ..., 0.9)$ $01$ $0.2051$ $15$ $0.1$ $01$ $10.5841$ $90$ $0.3$ $(-2, ..., -2)$ $01$ $11.4440$ $15$ $0.1$ $01$ $10.9202$ $90$ $0.3$ $(1, ..., 1)$ $92$ $1589.711$ $0.5$ $0.1$ $07$ $98.3717$ $600$ $0.3$ $1000$ $(0.9, ..., 0.9)$ $01$ $0.8017$ $15$ $0.1$ $01$ $1.6180$ $09$ $0.3$ $(-2, ..., -2)$ $01$ $69.5720$ $15$ $0.1$ $01$ $75.3165$ $90$ $0.3$ $(1, ..., 1)$ $38$ $3255.6828$ $1.5$ $0.1$ $11$ $841.6456$ $190$ $0.9$ $2000$ $(0.9, ..., 0.9)$ $01$ $22.9217$ $15$ $0.1$ $01$ $4.6524$ $09$ $0.3$ $(-2, ..., -2)$ $01$ $621.5315$ $15$ $0.1$ $01$ $583.3619$ $90$ $0.3$

Table 6.  Example 2

 Alg 3 $n$ $x^{0}$ $Iter$ $cpu$ $(1, ..., 1)$ $15$ $0.3515$ $10$ $(0.9, ..., 0.9)$ $15$ $0.4098$ $(-2, ..., -2)$ $17$ $0.3880$ $(1, ..., 1)$ $96$ $3.7692$ $100$ $(0.9, ..., 0.9)$ $21$ $0.7153$ $(-2, ..., -2)$ $21$ $0.7609$ $(1, ..., 1)$ $101$ $26.0059$ $500$ $(0.9, ..., 0.9)$ $21$ $6.1334$ $(-2, ..., -2)$ $21$ $5.4223$ $(1, ..., 1)$ $101$ $131.7395$ $1000$ $(0.9, ..., 0.9)$ $21$ $29.3578$ $(-2, ..., -2)$ $21$ $30.2118$ $(1, ..., 1)$ $95$ $785.6897$ $2000$ $(0.9, ..., 0.9)$ $21$ $193.5405$ $(-2, ..., -2)$ $21$ $200.4297$
•  [1] E. Allevi, A. Gnudi and I. V. Konnov, The proximal point method for nonmonotone variational inequalities, Mathematical Methods of Operations Research, 63 (2006), 553-565.  doi: 10.1007/s00186-005-0052-2. [2] J. P. Aubin and I. Ekeland, Applied Nonlinear Analysis, Wiley, New York, 1984. [3] J. P. Aubin and H. Frankowska, Set-Valued Analysis, Volume 2 of Systems and Control: Foundations and Applications, Birkhäuser Boston Inc., Boston, MA, 1990. [4] A. Auslender and M. Teboulle, Lagrangian duality and related multiplier methods for variational inequality problems, SIAM Journal on Optimization, 10 (2000), 1097-1115.  doi: 10.1137/S1052623499352656. [5] T. Q. Bao and P. Q. Khanh, A projection-type algorithm for pseudomonotone nonlipschitzian multivalued variational inequalities, Generalized Convexity, Generalized Monotonicity and Applications, Vol. 77 of Nonconvex Optimization and Its Applications, Springer, New York, NY, USA, (2005), 113–129. doi: 10.1007/0-387-23639-2_6. [6] L. C. Ceng, G. Mastroeni and J. C. Yao, An inexact proximal-type method for the generalized variational inequality in Banach spaces, Journal of Inequalities and Applications, (2007), Article ID 78124, 14 pages. doi: 10.1155/2007/78124. [7] S. C. Fang and E. L. Peterson, Generalized variational inequalities, Journal of Optimization Theory and Applications, 38 (1982), 363-383.  doi: 10.1007/BF00935344. [8] C. J. Fang and Y. He, A double projection algorithm for multi-valued variational inequalities and a unified framework of the method, Applied Mathematics and Computation, 217 (2011), 9543-9551.  doi: 10.1016/j.amc.2011.04.009. [9] M. Fukushima, The primal Douglas-Rachford splitting algorithm for a class of monotone mappings with application to the traffic equilibrium problem, Mathematical Programming, 72 (1996), 1-15.  doi: 10.1016/0025-5610(95)00012-7. [10] H. Grar and D. Benterki, New effective projection method for variational inequalities problem, RAIRO Operations Research, 49 (2015), 805-820.  doi: 10.1051/ro/2015006. [11] Y. He, A new double projection algorithm for variational inequalities, Journal of Computational and Applied Mathematics, 185 (2006), 166-173.  doi: 10.1016/j.cam.2005.01.031. [12] A. N. Iusem and B. F. Svaiter, A variant of Korpolevich's method for variational inequalities with a new search strategy, Optimization, 42 (1997), 309-321.  doi: 10.1080/02331939708844365. [13] A. N. Iusem and L. R. L. Perez, An extragradient-type algorithm for non-smooth variational inequalities, Optimization, 48 (2000), 309-332.  doi: 10.1080/02331930008844508. [14] A. N. Iusem, An iterative algorithm for variational inequalities problem, Computational and Applied Mathematics, 13 (1994), 103-114. [15] I. V. Konnov, On the rate of convergence of combined relaxation methods, Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 12 (1993), 89-92. [16] I. V. Konnov, Combined Relaxation Methods for Variational Inequalities, Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Germany, 495 (2001). doi: 10.1007/978-3-642-56886-2. [17] I. V. Konnov, Combined relaxation methods for generalized monotone variational inequalities, in: eneralized convexity and related topics, Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Germany, 583 (2007), 3–31. doi: 10.1007/978-3-540-37007-9_1. [18] G. M. Korpolevich, The extragradient method for finding saddle points and other problems, Matecon, 12 (1976), 747-756. [19] F. Li and Y. He, An algorithm for generalized variational inequality with pseudomonotone mapping, Journal of Computational and Applied Mathematics, 228 (2009), 212-218.  doi: 10.1016/j.cam.2008.09.014. [20] J. P. Penot and P. H. Quang, Generalized convexity of functions and generalized monotonicity of set-valued maps, J. Optimiz. Theory App., 92 (1997), 343-356.  doi: 10.1023/A:1022659230603. [21] B. T. Polyak, Introduction to Optimization, Optimization Sofware Incorporation, Publications Division, New York, USA, 1987. [22] R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization, 14 (1976), 877-898.  doi: 10.1137/0314056. [23] M. V. Solodov and B. F. Svaiter, A new projection method for variational inequality problems, SIAM Journal on Control and Optimization, 37 (1999), 765-776.  doi: 10.1137/S0363012997317475. [24] Y. J. Wang, N. Xiu and C. Y. Wang, Unified framework of extragradient-type method for pseudomonotone variational inequalities, Journal of Optimization Theory and Applications, 111 (2001), 641-656.  doi: 10.1023/A:1012606212823. [25] M. Ye, An improved projection method for solving generalized variational inequality problems, Optimization, 67 (2018), 1523-1533.  doi: 10.1080/02331934.2018.1478971.

Tables(6)