A projection algorithm for non-monotone variational inequalities. (English) Zbl 1434.90201
Summary: We introduce a projection-type algorithm for solving the variational inequality problem for point-to-set operators, and establish its convergence properties. Namely, we assume that the operator of the variational inequality is continuous in the point-to-set sense, i.e., inner- and outer-semicontinuous. Under the assumption that the dual solution set is not empty, we prove that our method converges to a solution of the variational inequality. Instead of the monotonicity assumption, we require the non-emptiness of the solution set of the dual formulation of the variational inequality. We provide numerical experiments illustrating the behaviour of our iterates. Moreover, we compare our new method with a recent similar one.
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 49J40 | Variational inequalities |
| 47J20 | Variational and other types of inequalities involving nonlinear operators (general) |
| 65K15 | Numerical methods for variational inequalities and related problems |
Keywords:
variational inequality; projection algorithms; outer-semicontinuous operator; inner-semicontinuous operatorReferences:
| [1] | Bauschke, HH; Combettes, PL, Convex analysis and monotone operator theory in Hilbert spaces (2011), New York: Springer, New York · Zbl 1218.47001 |
| [2] | Bello Cruz, JY; Díaz Millán, R., A direct splitting method for nonsmooth variational inequalities, J. Optim. Theory Appl., 161, 3, 728-737 (2014) · Zbl 1293.49016 · doi:10.1007/s10957-013-0478-2 |
| [3] | Bello Cruz, JY; Díaz millán, R., A variant of Forward-Backward splitting method for the sum of two monotone operators with a new search strategy, Optimization, 64, 7, 1471-1486 (2015) · Zbl 1337.49009 · doi:10.1080/02331934.2014.883510 |
| [4] | Bello Cruz, JY; Díaz Millán, R., A relaxed-projection splitting algorithm for variational inequalities in Hilbert spaces, J. Glob. Optim., 65, 3, 597-614 (2016) · Zbl 1342.90223 · doi:10.1007/s10898-015-0397-x |
| [5] | Bello Cruz, J.Y., Díaz Millán, R., Phan, H.M.: Conditional extragradient algorithms for solving constrained variational inequalities. To appear in Pacific Journal of Optimization (2019) · Zbl 1458.49011 |
| [6] | Brito, AS; da Cruz Neto, JX; Lopes, JO; Oliveira, PR, Interior proximal algorithm for quasiconvex programming problems and variational inequalities with linear constraints, J. Optim. Theory Appl., 154, 1, 217-234 (2012) · Zbl 1273.90238 · doi:10.1007/s10957-012-0002-0 |
| [7] | Boyd, S.; Vandenberghe, L., Convex optimization (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049 |
| [8] | Bui Van, D.; Do Sang, K., Projection algorithms for solving nonmonotone equilibrium problems in Hilbert space, J. Comput. Appl. Math., 302, 106-117 (2016) · Zbl 1334.90125 · doi:10.1016/j.cam.2016.01.054 |
| [9] | Burachik, RS; Dutta, J., Inexact proximal point methods for variational inequality problems, SIAM J. Optim., 20, 5, 2653-2678 (2010) · Zbl 1255.65108 · doi:10.1137/080733437 |
| [10] | Burachik, RS; Iusem, AN, Set-valued mappings and enlargements of monotone operators (2008), Berlin: Springer, Berlin · Zbl 1154.49001 |
| [11] | Burachik, RS; Lopes, JO; da Silva, GJP, An inexact interior point proximal method for the variational inequality problem, Comput. Appl. Math., 28, 1, 15-36 (2009) · Zbl 1169.65063 · doi:10.1590/S0101-82052009000100002 |
| [12] | Burachik, RS; Scheimberg, S., A proximal point method for the variational inequality problem in Banach spaces, SIAM J. Control. Optim., 39, 5, 1633-1649 (2001) · Zbl 0988.90045 · doi:10.1137/S0363012998339745 |
| [13] | Ceng, LC; Lai, TC; Yao, JC, Approximate proximal algorithms for generalized variational inequalities with paramonotonicity and pseudomonotonicity, Computers and Mathematics with Applications, 55, 1262-1269 (2008) · Zbl 1147.49006 · doi:10.1016/j.camwa.2007.06.010 |
| [14] | Censor, Y.; Gibali, A.; Reich, S., Strong convergence of subgradient extragradient methods for the variational inequality problem in Hilbert space, Optim. Methods Softw., 26, 827-845 (2011) · Zbl 1232.58008 · doi:10.1080/10556788.2010.551536 |
| [15] | Díaz Millán, R., Two algorithms for solving systems of inclusion problems, Numer Algorithms, 78, 1111-1127 (2018) · Zbl 1410.93047 · doi:10.1007/s11075-017-0415-9 |
| [16] | Facchinei, F.; Pang, JS, Finite-dimensional variational inequalities and complementarity problems (2003), Berlin: Springer, Berlin · Zbl 1062.90002 |
| [17] | Fang, C.; Chen, S., A subgradient extragradient algorithm for solving multi-valued variational inequality, Appl. Math. Comput., 229, 123-130 (2014) · Zbl 1364.65134 |
| [18] | Fang, C., Chen, S., Zheng, J.: A projection-type method for multivalued variational inequality.Abstract and Applied Analysis. 2013. Article ID 836720 (2013) · Zbl 1437.49019 |
| [19] | Ferris, MC; Pang, JS, Engineering and economic applications of complementarity problems, SIAM Rev., 39, 669-713 (1997) · Zbl 0891.90158 · doi:10.1137/S0036144595285963 |
| [20] | Fu Quan, X.; Nan Jing, H., A projection-proximal point algorithm for solving generalized variational inequalities, J. Optim. Theory Appl., 150, 98-117 (2011) · Zbl 1242.90267 · doi:10.1007/s10957-011-9825-3 |
| [21] | Gondzio, J.; Grothey, A., A new unblocking technique to warmstart interior point methods based on sensitivity analysis, SIAM J. Optim., 19, 3, 1184-1210 (2008) · Zbl 1177.90411 · doi:10.1137/060678129 |
| [22] | Hadjisavvas, N.; Schaible, S., Quasimonotone variational inequalities in Banach spaces, J. Optim. Theory Appl., 90, 1, 95-111 (1996) · Zbl 0904.49005 · doi:10.1007/BF02192248 |
| [23] | Hartman, P.; Stampacchia, G., On some non-linear elliptic differential-functional equations, Acta Math., 115, 271-310 (1966) · Zbl 0142.38102 · doi:10.1007/BF02392210 |
| [24] | Iusem, AN; Svaiter, BF, 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 |
| [25] | Repovs̆, D., Semenov, P.V.: Continuous selections of multivalued mappings, mathematics and its applications book series, Springer (1998) · Zbl 0915.54001 |
| [26] | Strodiot, JJ; Vuong, PT; Van Nguyen, TT, A class of shrinking projection extragradient methods for solving non-monotone equilibrium problems in Hilbert spaces, J. Glob. Optim., 64, 159-178 (2016) · Zbl 1357.90160 · doi:10.1007/s10898-015-0365-5 |
| [27] | Khan, AA; Sama, M., Optimal control of multivalued quasi variational inequalities, Nonlinear Anal., 75, 1419-1428 (2012) · Zbl 1236.49019 · doi:10.1016/j.na.2011.08.005 |
| [28] | Kinderlehrer, D.; Stampacchia, G., An introduction to variational inequalities and their applications (1980), New York: Academic Press, New York · Zbl 0457.35001 |
| [29] | Konnov, IV, Combined relaxation methods for finding equilibrium points and solving related problems, Russian Mathematics (Iz. VUZ), 37, 3, 44-51 (1993) · Zbl 0835.90123 |
| [30] | Konnov, IV, Combine relaxation methods for variational inequalities. Lecture notes in economics and mathematical systems 495 (2001), Berlin: Springer, Berlin · Zbl 0982.49009 |
| [31] | Konnov, IV, A combined relaxation method for variational inequalities with nonlinear constraints, Math. Program., 80, 239-252 (1998) · Zbl 0894.90145 |
| [32] | Konnov, IV, A class of combined iterative methods for solving variational inequalities, J. Optim. Theory Appl., 94, 677-693 (1997) · Zbl 0892.90172 · doi:10.1023/A:1022605117998 |
| [33] | Liu, X., Strict feasibility of pseudo-monotone variational inequality, International Journal of Pure and Applied Mathematics, 78, 3, 323-330 (2012) · Zbl 1268.90047 |
| [34] | Maingé, PE; Gobinddass, ML, Convergence of one-step projected gradient methods for variational inequalities, J. Optim. Theory Appl., 171, 1, 146-168 (2016) · Zbl 06661393 · doi:10.1007/s10957-016-0972-4 |
| [35] | Matsushita, L.; Xu, L., Finite convergence of the proximal point algorithm for variational inequality problems, Set-Valued and Variational Analysis, 21, 297-309 (2013) · Zbl 1321.49016 · doi:10.1007/s11228-012-0225-0 |
| [36] | Minglu, Y.; Yiran, H., A double projection method for solving variational inequalities without monotonicity, Comput. Optim. Appl., 60, 141-150 (2015) · Zbl 1308.90184 · doi:10.1007/s10589-014-9659-7 |
| [37] | Monteiro, RDC; Svaiter, BF, An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods, SIAM J. Optim., 23, 2, 1092-1125 (2013) · Zbl 1298.90071 · doi:10.1137/110833786 |
| [38] | Langenberg, N., An interior proximal method for a class of quasimonotone variational inequalities, J. Optim. Theory Appl., 155, 902-922 (2012) · Zbl 1257.90104 · doi:10.1007/s10957-012-0111-9 |
| [39] | Rockafellar, RT, Local boundedness of nonlinear, Monotone Operators.Michigan Mathematical Journal, 16, 397-407 (1969) · Zbl 0175.45002 · doi:10.1307/mmj/1029000324 |
| [40] | Rockafellar, RT; Wets, RJB, Variational analysis. Grundlehren der mathematischen Wissenschaften 317 (1998), Berlin: Springer, Berlin · Zbl 0888.49001 |
| [41] | Saewan, S.; Kumam, P., Computational of generalized projection method for maximal monotone operators and a countable family of relatively quasi-nonexpansive mappings, Optimization, 64, 12, 2531-2552 (2015) · Zbl 1328.47070 · doi:10.1080/02331934.2013.824444 |
| [42] | Shih, MH; Tan, KK, Browder-Hartmann-Stampacchia variational inequalities for multi-valued monotone operators, Journal of Mathematical Analysis and Applications, 134, 431-440 (1988) · Zbl 0671.47043 · doi:10.1016/0022-247X(88)90033-9 |
| [43] | Solodov, MV; Svaiter, BF, A new projection method for variational inequality problems, SIAM Journal on Control and Optimization, 37, 3, 765-776 (1999) · Zbl 0959.49007 · doi:10.1137/S0363012997317475 |
| [44] | Solodov, MV; Svaiter, BF, Forcing strong convergence of proximal point iterations in a Hilbert space, Math. Program., 87, 189-202 (2000) · Zbl 0971.90062 · doi:10.1007/s101079900113 |
| [45] | Van Hieu, D.; Anh, PK; Muu, LD, Modified hybrid projection methods for finding common solutions to variational inequality problems, Comput. Optim. Appl., 66, 1, 75-96 (2016) · Zbl 1368.65103 · doi:10.1007/s10589-016-9857-6 |
| [46] | Wang, YJ; Xiu, NH; Zhang, JZ, Modified extragradient method for variational inequalities and verification of solution existence, J. Optim. Theory Appl., 119, 1, 167-183 (2003) · Zbl 1045.49017 · doi:10.1023/B:JOTA.0000005047.30026.b8 |
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.
