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.

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

[3]

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

[4]

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

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

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

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

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

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

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

[20]

J. Mandel, A multilevel iterative method for symmetric, positive definite linear complementary problems,, Appl. Math. Opt., 11 (1984), 77. 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.

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

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

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.

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

[3]

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

[4]

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

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

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

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

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

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

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

[20]

J. Mandel, A multilevel iterative method for symmetric, positive definite linear complementary problems,, Appl. Math. Opt., 11 (1984), 77. 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.

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

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

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

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Assyr Abdulle. Multiscale methods for advection-diffusion problems. Conference Publications, 2005, 2005 (Special) : 11-21. doi: 10.3934/proc.2005.2005.11

[19]

Alexander Mielke. Weak-convergence methods for Hamiltonian multiscale problems. Discrete & Continuous Dynamical Systems - A, 2008, 20 (1) : 53-79. doi: 10.3934/dcds.2008.20.53

[20]

José A. Cañizo, Alexis Molino. Improved energy methods for nonlocal diffusion problems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (3) : 1405-1425. doi: 10.3934/dcds.2018057

2018 Impact Factor: 0.545

Metrics

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

Other articles
by authors

[Back to Top]