# American Institute of Mathematical Sciences

December  2013, 6(6): 1457-1471. doi: 10.3934/dcdss.2013.6.1457

## Multigrid methods for some quasi-variational inequalities

 1 Institute of Mathematics of the Romanian Academy, P.O. Box 1-764, RO-014700 Bucharest, Romania

Received  June 2012 Revised  September 2012 Published  April 2013

We introduce four variants of a multigrid method for quasi-variational inequalities composed by a term arising from the minimization of a functional and another one given by an operator. The four variants of the method differ from one to another by the argument of the operator. The method assume that the closed convex set is decomposed as a sum of closed convex level subsets. These methods are first introduced as subspace correction algorithms in a general reflexive Banach space. Under an assumption on the level decomposition of the closed convex set of the problem, we prove that the algorithms are globally convergent if a certain convergence condition is satisfied, and estimate the global convergence rate. These general algorithms become multilevel or multigrid methods if we use finite element spaces associated with the level meshes of the domain and with the domain decompositions on each level. In this case, the methods are multigrid $V$-cycles, but the results hold for other iteration types, the $W$-cycle iterations, for instance. We prove that the assumption we made in the general convergence theory holds for the one-obstacle problems, and write the convergence rate depending on the number of level meshes. The convergence condition in the theorem imposes a upper bound of the number of level meshes we can use in algorithms.
Citation: Lori Badea. Multigrid methods for some quasi-variational inequalities. Discrete and Continuous Dynamical Systems - S, 2013, 6 (6) : 1457-1471. doi: 10.3934/dcdss.2013.6.1457
##### References:
 [1] L. Badea, Schwarz methods for inequalities with contraction operators, J. Comp. Appl. Math., 215 (2008), 196-219. doi: 10.1016/j.cam.2007.04.004. [2] L. Badea, An additive Schwarz method for the constrained minimization of functionals in reflexive Banach spaces, in "Domain Decomposition Methods in Science and Engineering XVII" (eds. U. Langer, et al.), Lect. Notes Comput. Sci. Eng., 60, Springer, Berlin, (2008), 427-434. doi: 10.1007/978-3-540-75199-1_54. [3] L. Badea, Multigrid methods for variational inequalities, preprint series of the Institute of Mathematics of the Romanian Academy, 1 (2010). Available from: http://www.imar.ro/~lbadea/. [4] L. Badea, Multigrid methods with constraint level decomposition for variational inequalities, Ann. Acad. Rom. Sci. Ser. Math. Appl., 3 (2011), 300-331. [5] L. Badea, Multigrid methods with constraint level decomposition for variational inequalities, preprint series of the Institute of Mathematics of the Romanian Academy, 3 (2010). Available from: http://www.imar.ro/~lbadea/. [6] L. Badea and R. Krause, One- and two-level Schwarz methods for variational inequalities of the second kind and their application to frictional contact, Numer. Math., 120 (2012), 573-599. doi: 10.1007/s00211-011-0423-y. [7] L. Badea and R. Krause, One- and two-level multiplicative Schwarz methods for variational and quasi-variational inequalities of the second kind: Part I - general convergence results, INS Preprint, No. 0804, Institute for Numerical Simulation, University of Bonn, (2008). [8] L. Badea, X.-C. Tai and J. Wang, Convergence rate analysis of a multiplicative Schwarz method for variational inequalities, SIAM J. Numer. Anal., 41 (2003), 1052-1073. doi: 10.1137/S0036142901393607. [9] A. Brandt and C. Cryer, Multigrid algorithms for the solution of linear complementary problems arising from free boundary problems, SIAM J. Sci. Stat. Comput., 4 (1983), 655-684. doi: 10.1137/0904046. [10] I. Ekeland and R. Temam, "Analyse Convexe et Problèmes Variationnels," Collection Études Mathématiques, Dunod, Gauthier-Villars, Paris-Brussels-Montreal, Que., 1974. [11] E. Gelman and J. Mandel, On multilevel iterative method for optimization problems, Math. Program., 48 (1990), 1-17. doi: 10.1007/BF01582249. [12] R. Glowinski, J.-L. Lions and R. Trémolières, "Analyse Numérique des Inéquations Variationnelles," Dunod, Paris, 1976. [13] C. Gräser and R. Kornhuber, Multigrid methods for obstacle problems, J. Comput. Math., 27 (2009), 1-44. [14] W. Hackbusch and H.-D. Mittelmann, On multigrid methods for variational inequalities, Numer. Math., 42 (1983), 65-76. doi: 10.1007/BF01400918. [15] R. Hoppe and R. Kornhuber, Adaptive multilevel methods for obstacle problems, SIAM J. Numer. Anal., 31 (1994), 301-323. doi: 10.1137/0731016. [16] R. Kornhuber, Monotone multigrid methods for elliptic variational inequalities. I, Numer. Math., 69 (1994), 167-184. [17] R. Kornhuber, Monotone multigrid methods for elliptic variational inequalities. II, Numer. Math., 72 (1996), 481-499. doi: 10.1007/s002110050178. [18] R. Kornhuber, "Adaptive Monotone Multigrid Methods for Nonlinear Variational Problems," Advances in Numerical Mathematics, B. G. Teubner, Stuttgart, 1997. [19] R. Kornhuber and H. Yserentant, Multilevel methods for elliptic problems on domains not resolved by the coarse grid, in "Domain Decomposition Methods in Scientific and Engineering Computing" (University Park, PA, 1993), Contemporary Mathematics, 180, Amer. Math. Soc., Providence, RI, (1994), 49-60. doi: 10.1090/conm/180/01956. [20] J. Mandel, A multilevel iterative method for symmetric, positive definite linear complementary problems, Appl. Math. Opt., 11 (1984), 77-95. doi: 10.1007/BF01442171. [21] J. Mandel, Étude algébrique d'une méthode multigrille pour quelques problèmes de frontière libre, C. R. Acad. Sci. Paris Sér. I Math., 298 (1984), 469-472. [22] X.-C. Tai, Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities, Numer. Math., 93 (2003), 755-786. doi: 10.1007/s002110200404. [23] X.-C. Tai and J. Xu, Global and uniform convergence of subspace correction methods for some convex optimization problems, Math. Comp., 71 (2002), 105-124. doi: 10.1090/S0025-5718-01-01311-4.

show all references

##### References:
 [1] L. Badea, Schwarz methods for inequalities with contraction operators, J. Comp. Appl. Math., 215 (2008), 196-219. doi: 10.1016/j.cam.2007.04.004. [2] L. Badea, An additive Schwarz method for the constrained minimization of functionals in reflexive Banach spaces, in "Domain Decomposition Methods in Science and Engineering XVII" (eds. U. Langer, et al.), Lect. Notes Comput. Sci. Eng., 60, Springer, Berlin, (2008), 427-434. doi: 10.1007/978-3-540-75199-1_54. [3] L. Badea, Multigrid methods for variational inequalities, preprint series of the Institute of Mathematics of the Romanian Academy, 1 (2010). Available from: http://www.imar.ro/~lbadea/. [4] L. Badea, Multigrid methods with constraint level decomposition for variational inequalities, Ann. Acad. Rom. Sci. Ser. Math. Appl., 3 (2011), 300-331. [5] L. Badea, Multigrid methods with constraint level decomposition for variational inequalities, preprint series of the Institute of Mathematics of the Romanian Academy, 3 (2010). Available from: http://www.imar.ro/~lbadea/. [6] L. Badea and R. Krause, One- and two-level Schwarz methods for variational inequalities of the second kind and their application to frictional contact, Numer. Math., 120 (2012), 573-599. doi: 10.1007/s00211-011-0423-y. [7] L. Badea and R. Krause, One- and two-level multiplicative Schwarz methods for variational and quasi-variational inequalities of the second kind: Part I - general convergence results, INS Preprint, No. 0804, Institute for Numerical Simulation, University of Bonn, (2008). [8] L. Badea, X.-C. Tai and J. Wang, Convergence rate analysis of a multiplicative Schwarz method for variational inequalities, SIAM J. Numer. Anal., 41 (2003), 1052-1073. doi: 10.1137/S0036142901393607. [9] A. Brandt and C. Cryer, Multigrid algorithms for the solution of linear complementary problems arising from free boundary problems, SIAM J. Sci. Stat. Comput., 4 (1983), 655-684. doi: 10.1137/0904046. [10] I. Ekeland and R. Temam, "Analyse Convexe et Problèmes Variationnels," Collection Études Mathématiques, Dunod, Gauthier-Villars, Paris-Brussels-Montreal, Que., 1974. [11] E. Gelman and J. Mandel, On multilevel iterative method for optimization problems, Math. Program., 48 (1990), 1-17. doi: 10.1007/BF01582249. [12] R. Glowinski, J.-L. Lions and R. Trémolières, "Analyse Numérique des Inéquations Variationnelles," Dunod, Paris, 1976. [13] C. Gräser and R. Kornhuber, Multigrid methods for obstacle problems, J. Comput. Math., 27 (2009), 1-44. [14] W. Hackbusch and H.-D. Mittelmann, On multigrid methods for variational inequalities, Numer. Math., 42 (1983), 65-76. doi: 10.1007/BF01400918. [15] R. Hoppe and R. Kornhuber, Adaptive multilevel methods for obstacle problems, SIAM J. Numer. Anal., 31 (1994), 301-323. doi: 10.1137/0731016. [16] R. Kornhuber, Monotone multigrid methods for elliptic variational inequalities. I, Numer. Math., 69 (1994), 167-184. [17] R. Kornhuber, Monotone multigrid methods for elliptic variational inequalities. II, Numer. Math., 72 (1996), 481-499. doi: 10.1007/s002110050178. [18] R. Kornhuber, "Adaptive Monotone Multigrid Methods for Nonlinear Variational Problems," Advances in Numerical Mathematics, B. G. Teubner, Stuttgart, 1997. [19] R. Kornhuber and H. Yserentant, Multilevel methods for elliptic problems on domains not resolved by the coarse grid, in "Domain Decomposition Methods in Scientific and Engineering Computing" (University Park, PA, 1993), Contemporary Mathematics, 180, Amer. Math. Soc., Providence, RI, (1994), 49-60. doi: 10.1090/conm/180/01956. [20] J. Mandel, A multilevel iterative method for symmetric, positive definite linear complementary problems, Appl. Math. Opt., 11 (1984), 77-95. doi: 10.1007/BF01442171. [21] J. Mandel, Étude algébrique d'une méthode multigrille pour quelques problèmes de frontière libre, C. R. Acad. Sci. Paris Sér. I Math., 298 (1984), 469-472. [22] X.-C. Tai, Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities, Numer. Math., 93 (2003), 755-786. doi: 10.1007/s002110200404. [23] X.-C. Tai and J. Xu, Global and uniform convergence of subspace correction methods for some convex optimization problems, Math. Comp., 71 (2002), 105-124. doi: 10.1090/S0025-5718-01-01311-4.
 [1] Daijun Jiang, Hui Feng, Jun Zou. Overlapping domain decomposition methods for linear inverse problems. Inverse Problems and Imaging, 2015, 9 (1) : 163-188. doi: 10.3934/ipi.2015.9.163 [2] O. Chadli, Z. Chbani, H. Riahi. Recession methods for equilibrium problems and applications to variational and hemivariational inequalities. Discrete and Continuous Dynamical Systems, 1999, 5 (1) : 185-196. doi: 10.3934/dcds.1999.5.185 [3] Yusuke Murase, Atsushi Kadoya, Nobuyuki Kenmochi. Optimal control problems for quasi-variational inequalities and its numerical approximation. Conference Publications, 2011, 2011 (Special) : 1101-1110. doi: 10.3934/proc.2011.2011.1101 [4] Yusuke Murase, Risei Kano, Nobuyuki Kenmochi. Elliptic Quasi-variational inequalities and applications. Conference Publications, 2009, 2009 (Special) : 583-591. doi: 10.3934/proc.2009.2009.583 [5] Jana Kopfová. Nonlinear semigroup methods in problems with hysteresis. Conference Publications, 2007, 2007 (Special) : 580-589. doi: 10.3934/proc.2007.2007.580 [6] Zalman Balanov, Carlos García-Azpeitia, Wieslaw Krawcewicz. On variational and topological methods in nonlinear difference equations. Communications on Pure and Applied Analysis, 2018, 17 (6) : 2813-2844. doi: 10.3934/cpaa.2018133 [7] Lori Badea, Marius Cocou. Approximation results and subspace correction algorithms for implicit variational inequalities. Discrete and Continuous Dynamical Systems - S, 2013, 6 (6) : 1507-1524. doi: 10.3934/dcdss.2013.6.1507 [8] Yurii Nesterov, Laura Scrimali. Solving strongly monotone variational and quasi-variational inequalities. Discrete and Continuous Dynamical Systems, 2011, 31 (4) : 1383-1396. doi: 10.3934/dcds.2011.31.1383 [9] Lukas Einkemmer, Alexander Ostermann. A comparison of boundary correction methods for Strang splitting. Discrete and Continuous Dynamical Systems - B, 2018, 23 (7) : 2641-2660. doi: 10.3934/dcdsb.2018081 [10] Jie Sun. On methods for solving nonlinear semidefinite optimization problems. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 1-14. doi: 10.3934/naco.2011.1.1 [11] Laura Scrimali. Mixed behavior network equilibria and quasi-variational inequalities. Journal of Industrial and Management Optimization, 2009, 5 (2) : 363-379. doi: 10.3934/jimo.2009.5.363 [12] Jean Dolbeault, An Zhang. Parabolic methods for ultraspherical interpolation inequalities. Discrete and Continuous Dynamical Systems, 2022  doi: 10.3934/dcds.2022080 [13] Edson Pindza, Francis Youbi, Eben Maré, Matt Davison. Barycentric spectral domain decomposition methods for valuing a class of infinite activity Lévy models. Discrete and Continuous Dynamical Systems - S, 2019, 12 (3) : 625-643. doi: 10.3934/dcdss.2019040 [14] Dang Van Hieu, Le Dung Muu, Pham Kim Quy. New iterative regularization methods for solving split variational inclusion problems. Journal of Industrial and Management Optimization, 2023, 19 (1) : 300-320. doi: 10.3934/jimo.2021185 [15] Michael Herty, Giuseppe Visconti. Kinetic methods for inverse problems. Kinetic and Related Models, 2019, 12 (5) : 1109-1130. doi: 10.3934/krm.2019042 [16] Nobuyuki Kenmochi. Parabolic quasi-variational diffusion problems with gradient constraints. Discrete and Continuous Dynamical Systems - S, 2013, 6 (2) : 423-438. doi: 10.3934/dcdss.2013.6.423 [17] Masao Fukushima. A class of gap functions for quasi-variational inequality problems. Journal of Industrial and Management Optimization, 2007, 3 (2) : 165-171. doi: 10.3934/jimo.2007.3.165 [18] Abdeslem Hafid Bentbib, Smahane El-Halouy, El Mostafa Sadek. Extended Krylov subspace methods for solving Sylvester and Stein tensor equations. Discrete and Continuous Dynamical Systems - S, 2022, 15 (1) : 41-56. doi: 10.3934/dcdss.2021026 [19] Hassan Mohammad, Mohammed Yusuf Waziri, Sandra Augusta Santos. A brief survey of methods for solving nonlinear least-squares problems. Numerical Algebra, Control and Optimization, 2019, 9 (1) : 1-13. doi: 10.3934/naco.2019001 [20] Xing-Bin Pan. Variational and operator methods for Maxwell-Stokes system. Discrete and Continuous Dynamical Systems, 2020, 40 (6) : 3909-3955. doi: 10.3934/dcds.2020036

2021 Impact Factor: 1.865