An improved projection algorithm for variational inequality problem with multivalued mapping

Ouafa Belguidoum; Hassina Grar

doi:10.3934/naco.2022002

Article Contents

2023, Volume 13, Issue 2: 210-223. Doi: 10.3934/naco.2022002

This issue Previous Article Exact controllability for a degenerate and singular wave equation with moving boundary Next Article Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term

An improved projection algorithm for variational inequality problem with multivalued mapping

Ouafa Belguidoum and
Hassina Grar^,

Fondamental and Numerical Mathematics Laboratory, Faculty of sciences, University Sétif-1, Algeria

Received: August 2021

Revised: January 2022

Early access: February 2022

Published: January 2023

Abstract / Introduction Full Text(HTML) Figure(0) / Table(6) Related Papers Cited by

Abstract

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.

Keywords:

Generalized variational inequality problem,
projection method,
multivalued mapping,
fixed point theorem.

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

Citation:

FullText(HTML)

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 $

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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.