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 & 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.  doi: 10.1016/j.cam.2007.04.004.  Google Scholar

[2]

L. Badea, An additive Schwarz method for the constrained minimization of functionals in reflexive Banach spaces,, in, 60 (2008), 427.  doi: 10.1007/978-3-540-75199-1_54.  Google Scholar

[3]

L. Badea, Multigrid methods for variational inequalities,, preprint series of the Institute of Mathematics of the Romanian Academy, 1 (2010).   Google Scholar

[4]

L. Badea, Multigrid methods with constraint level decomposition for variational inequalities,, Ann. Acad. Rom. Sci. Ser. Math. Appl., 3 (2011), 300.   Google Scholar

[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).   Google Scholar

[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.  doi: 10.1007/s00211-011-0423-y.  Google Scholar

[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, (2008).   Google Scholar

[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.  doi: 10.1137/S0036142901393607.  Google Scholar

[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.  doi: 10.1137/0904046.  Google Scholar

[10]

I. Ekeland and R. Temam, "Analyse Convexe et Problèmes Variationnels,", Collection Études Mathématiques, (1974).   Google Scholar

[11]

E. Gelman and J. Mandel, On multilevel iterative method for optimization problems,, Math. Program., 48 (1990), 1.  doi: 10.1007/BF01582249.  Google Scholar

[12]

R. Glowinski, J.-L. Lions and R. Trémolières, "Analyse Numérique des Inéquations Variationnelles,", Dunod, (1976).   Google Scholar

[13]

C. Gräser and R. Kornhuber, Multigrid methods for obstacle problems,, J. Comput. Math., 27 (2009), 1.   Google Scholar

[14]

W. Hackbusch and H.-D. Mittelmann, On multigrid methods for variational inequalities,, Numer. Math., 42 (1983), 65.  doi: 10.1007/BF01400918.  Google Scholar

[15]

R. Hoppe and R. Kornhuber, Adaptive multilevel methods for obstacle problems,, SIAM J. Numer. Anal., 31 (1994), 301.  doi: 10.1137/0731016.  Google Scholar

[16]

R. Kornhuber, Monotone multigrid methods for elliptic variational inequalities. I,, Numer. Math., 69 (1994), 167.   Google Scholar

[17]

R. Kornhuber, Monotone multigrid methods for elliptic variational inequalities. II,, Numer. Math., 72 (1996), 481.  doi: 10.1007/s002110050178.  Google Scholar

[18]

R. Kornhuber, "Adaptive Monotone Multigrid Methods for Nonlinear Variational Problems,", Advances in Numerical Mathematics, (1997).   Google Scholar

[19]

R. Kornhuber and H. Yserentant, Multilevel methods for elliptic problems on domains not resolved by the coarse grid,, in, 180 (1994), 49.  doi: 10.1090/conm/180/01956.  Google Scholar

[20]

J. Mandel, A multilevel iterative method for symmetric, positive definite linear complementary problems,, Appl. Math. Opt., 11 (1984), 77.  doi: 10.1007/BF01442171.  Google Scholar

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

[22]

X.-C. Tai, Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities,, Numer. Math., 93 (2003), 755.  doi: 10.1007/s002110200404.  Google Scholar

[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.  doi: 10.1090/S0025-5718-01-01311-4.  Google Scholar

show all references

References:
[1]

L. Badea, Schwarz methods for inequalities with contraction operators,, J. Comp. Appl. Math., 215 (2008), 196.  doi: 10.1016/j.cam.2007.04.004.  Google Scholar

[2]

L. Badea, An additive Schwarz method for the constrained minimization of functionals in reflexive Banach spaces,, in, 60 (2008), 427.  doi: 10.1007/978-3-540-75199-1_54.  Google Scholar

[3]

L. Badea, Multigrid methods for variational inequalities,, preprint series of the Institute of Mathematics of the Romanian Academy, 1 (2010).   Google Scholar

[4]

L. Badea, Multigrid methods with constraint level decomposition for variational inequalities,, Ann. Acad. Rom. Sci. Ser. Math. Appl., 3 (2011), 300.   Google Scholar

[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).   Google Scholar

[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.  doi: 10.1007/s00211-011-0423-y.  Google Scholar

[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, (2008).   Google Scholar

[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.  doi: 10.1137/S0036142901393607.  Google Scholar

[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.  doi: 10.1137/0904046.  Google Scholar

[10]

I. Ekeland and R. Temam, "Analyse Convexe et Problèmes Variationnels,", Collection Études Mathématiques, (1974).   Google Scholar

[11]

E. Gelman and J. Mandel, On multilevel iterative method for optimization problems,, Math. Program., 48 (1990), 1.  doi: 10.1007/BF01582249.  Google Scholar

[12]

R. Glowinski, J.-L. Lions and R. Trémolières, "Analyse Numérique des Inéquations Variationnelles,", Dunod, (1976).   Google Scholar

[13]

C. Gräser and R. Kornhuber, Multigrid methods for obstacle problems,, J. Comput. Math., 27 (2009), 1.   Google Scholar

[14]

W. Hackbusch and H.-D. Mittelmann, On multigrid methods for variational inequalities,, Numer. Math., 42 (1983), 65.  doi: 10.1007/BF01400918.  Google Scholar

[15]

R. Hoppe and R. Kornhuber, Adaptive multilevel methods for obstacle problems,, SIAM J. Numer. Anal., 31 (1994), 301.  doi: 10.1137/0731016.  Google Scholar

[16]

R. Kornhuber, Monotone multigrid methods for elliptic variational inequalities. I,, Numer. Math., 69 (1994), 167.   Google Scholar

[17]

R. Kornhuber, Monotone multigrid methods for elliptic variational inequalities. II,, Numer. Math., 72 (1996), 481.  doi: 10.1007/s002110050178.  Google Scholar

[18]

R. Kornhuber, "Adaptive Monotone Multigrid Methods for Nonlinear Variational Problems,", Advances in Numerical Mathematics, (1997).   Google Scholar

[19]

R. Kornhuber and H. Yserentant, Multilevel methods for elliptic problems on domains not resolved by the coarse grid,, in, 180 (1994), 49.  doi: 10.1090/conm/180/01956.  Google Scholar

[20]

J. Mandel, A multilevel iterative method for symmetric, positive definite linear complementary problems,, Appl. Math. Opt., 11 (1984), 77.  doi: 10.1007/BF01442171.  Google Scholar

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

[22]

X.-C. Tai, Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities,, Numer. Math., 93 (2003), 755.  doi: 10.1007/s002110200404.  Google Scholar

[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.  doi: 10.1090/S0025-5718-01-01311-4.  Google Scholar

[1]

Daijun Jiang, Hui Feng, Jun Zou. Overlapping domain decomposition methods for linear inverse problems. Inverse Problems & 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 & Continuous Dynamical Systems - A, 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]

Jana Kopfová. Nonlinear semigroup methods in problems with hysteresis. Conference Publications, 2007, 2007 (Special) : 580-589. doi: 10.3934/proc.2007.2007.580

[5]

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

[6]

Zalman Balanov, Carlos García-Azpeitia, Wieslaw Krawcewicz. On variational and topological methods in nonlinear difference equations. Communications on Pure & 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 & Continuous Dynamical Systems - S, 2013, 6 (6) : 1507-1524. doi: 10.3934/dcdss.2013.6.1507

[8]

Lukas Einkemmer, Alexander Ostermann. A comparison of boundary correction methods for Strang splitting. Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : 2641-2660. doi: 10.3934/dcdsb.2018081

[9]

Yurii Nesterov, Laura Scrimali. Solving strongly monotone variational and quasi-variational inequalities. Discrete & Continuous Dynamical Systems - A, 2011, 31 (4) : 1383-1396. doi: 10.3934/dcds.2011.31.1383

[10]

Jie Sun. On methods for solving nonlinear semidefinite optimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 1-14. doi: 10.3934/naco.2011.1.1

[11]

Michael Herty, Giuseppe Visconti. Kinetic methods for inverse problems. Kinetic & Related Models, 2019, 12 (5) : 1109-1130. doi: 10.3934/krm.2019042

[12]

Edson Pindza, Francis Youbi, Eben Maré, Matt Davison. Barycentric spectral domain decomposition methods for valuing a class of infinite activity Lévy models. Discrete & Continuous Dynamical Systems - S, 2019, 12 (3) : 625-643. doi: 10.3934/dcdss.2019040

[13]

Laura Scrimali. Mixed behavior network equilibria and quasi-variational inequalities. Journal of Industrial & Management Optimization, 2009, 5 (2) : 363-379. doi: 10.3934/jimo.2009.5.363

[14]

Hassan Mohammad, Mohammed Yusuf Waziri, Sandra Augusta Santos. A brief survey of methods for solving nonlinear least-squares problems. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 1-13. doi: 10.3934/naco.2019001

[15]

Masao Fukushima. A class of gap functions for quasi-variational inequality problems. Journal of Industrial & Management Optimization, 2007, 3 (2) : 165-171. doi: 10.3934/jimo.2007.3.165

[16]

Nobuyuki Kenmochi. Parabolic quasi-variational diffusion problems with gradient constraints. Discrete & Continuous Dynamical Systems - S, 2013, 6 (2) : 423-438. doi: 10.3934/dcdss.2013.6.423

[17]

Xing-Bin Pan. Variational and operator methods for Maxwell-Stokes system. Discrete & Continuous Dynamical Systems - A, 2019, 0 (0) : 0-0. doi: 10.3934/dcds.2020036

[18]

Haisen Zhang. Clarke directional derivatives of regularized gap functions for nonsmooth quasi-variational inequalities. Mathematical Control & Related Fields, 2014, 4 (3) : 365-379. doi: 10.3934/mcrf.2014.4.365

[19]

Samir Adly, Tahar Haddad. On evolution quasi-variational inequalities and implicit state-dependent sweeping processes. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020105

[20]

Zaihui Gan. Cross-constrained variational methods for the nonlinear Klein-Gordon equations with an inverse square potential. Communications on Pure & Applied Analysis, 2009, 8 (5) : 1541-1554. doi: 10.3934/cpaa.2009.8.1541

2018 Impact Factor: 0.545

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]