×

zbMATH — the first resource for mathematics

Global and uniform convergence of subspace correction methods for some convex optimization problems. (English) Zbl 0985.65065
This paper provides some global and uniform convergence estimates for a class of subspace correction (based on space decomposition) iterative methods applied to some unconstrained convex optimization problems. Some multigrid and domain decomposition methods are also discussed as special examples of solving some nonlinear elliptic boundary value problems.

MSC:
65K05 Numerical mathematical programming methods
90C25 Convex programming
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
35J65 Nonlinear boundary value problems for linear elliptic equations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] O. Axelsson and W. Layton, A two-level discretization of nonlinear boundary value problems, SIAM J. Numer. Anal. 33 (1996), no. 6, 2359 – 2374. · Zbl 0866.65077 · doi:10.1137/S0036142993247104 · doi.org
[2] Randolph E. Bank and Donald J. Rose, Analysis of a multilevel iterative method for nonlinear finite element equations, Math. Comp. 39 (1982), no. 160, 453 – 465. · Zbl 0496.65060
[3] James H. Bramble, Joseph E. Pasciak, Jun Ping Wang, and Jinchao Xu, Convergence estimates for product iterative methods with applications to domain decomposition, Math. Comp. 57 (1991), no. 195, 1 – 21. · Zbl 0754.65085
[4] Xiao-Chuan Cai and Maksymilian Dryja, Domain decomposition methods for monotone nonlinear elliptic problems, Domain decomposition methods in scientific and engineering computing (University Park, PA, 1993) Contemp. Math., vol. 180, Amer. Math. Soc., Providence, RI, 1994, pp. 21 – 27. · Zbl 0817.65127 · doi:10.1090/conm/180/01953 · doi.org
[5] Jean Céa, Optimisation: Théorie et algorithmes, Dunod, Paris, 1971 (French). Méthodes Mathématiques de l’Informatique, 2.
[6] T. F. Chan and I. Sharapov. Subspace correction multilevel methods for elliptic eigenvalue problems. In P. Bjørstad, M. Espedal, and D. Keyes, editors, Domain decomposition methods in science and engineering, 9th international conference, Bergen, Norway., pages 311-317. DDM.org, 1998. Available online at http://www.ddm.org/DD9/.
[7] Philippe G. Ciarlet, The finite element method for elliptic problems, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. Studies in Mathematics and its Applications, Vol. 4. · Zbl 0383.65058
[8] P. Deuflhard and M. Weiser. Global inexact Newton multilevel FEM for nonlinear elliptic problems. In W. Hackbusch and G. Wittum, editors, Multigrid methods V, Lecture Notes in Computational Science and Engineering, Stuttgart, 1996, Springer. CMP 2000:06 · Zbl 0926.65135
[9] Jim Douglas Jr., Todd Dupont, and Lars Wahlbin, The stability in \?^\? of the \?²-projection into finite element function spaces, Numer. Math. 23 (1974/75), 193 – 197. · Zbl 0297.41022 · doi:10.1007/BF01400302 · doi.org
[10] M. Dryja and W. Hackbusch, On the nonlinear domain decomposition method, BIT 37 (1997), no. 2, 296 – 311. · Zbl 0891.65126 · doi:10.1007/BF02510214 · doi.org
[11] Maksymilian Dryja and Olof B. Widlund, Towards a unified theory of domain decomposition algorithms for elliptic problems, Third International Symposium on Domain Decomposition Methods for Partial Differential Equations (Houston, TX, 1989) SIAM, Philadelphia, PA, 1990, pp. 3 – 21. · Zbl 0772.65021
[12] Ivar Ekeland and Roger Temam, Analyse convexe et problèmes variationnels, Dunod; Gauthier-Villars, Paris-Brussels-Montreal, Que., 1974 (French). Collection Études Mathématiques. Ivar Ekeland and Roger Temam, Convex analysis and variational problems, North-Holland Publishing Co., Amsterdam-Oxford; American Elsevier Publishing Co., Inc., New York, 1976. Translated from the French; Studies in Mathematics and its Applications, Vol. 1.
[13] E. Gelman and J. Mandel, On multilevel iterative methods for optimization problems, Math. Programming 48 (1990), no. 1, (Ser. B), 1 – 17. · Zbl 0738.90059 · doi:10.1007/BF01582249 · doi.org
[14] R. Glowinski and A. Marrocco, Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité, d’une classe de problèmes de Dirichlet non linéaires, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge Anal. Numér. 9 (1975), no. R-2, 41 – 76 (French, with Loose English summary). · Zbl 0368.65053
[15] M. Griebel and P. Oswald, On the abstract theory of additive and multiplicative Schwarz algorithms, Numer. Math. 70 (1995), no. 2, 163 – 180. · Zbl 0826.65098 · doi:10.1007/s002110050115 · doi.org
[16] W. Hackbusch and A. Reusken, Analysis of a damped nonlinear multilevel method, Numer. Math. 55 (1989), no. 2, 225 – 246. · Zbl 0673.65031 · doi:10.1007/BF01406516 · doi.org
[17] Ralf Kornhuber, Adaptive monotone multigrid methods for nonlinear variational problems, Advances in Numerical Mathematics, B. G. Teubner, Stuttgart, 1997. · Zbl 0879.65041
[18] R. Kornhuber. Globally convergent multigrid methods for porous medium type equations. Preprint, 1999.
[19] P.-L. Lions, On the Schwarz alternating method. I, First International Symposium on Domain Decomposition Methods for Partial Differential Equations (Paris, 1987) SIAM, Philadelphia, PA, 1988, pp. 1 – 42. · Zbl 0658.65090
[20] Jan 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), no. 18, 469 – 472 (French, with English summary). · Zbl 0543.65044
[21] Stephen F. McCormick, Multilevel projection methods for partial differential equations, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 62, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. · Zbl 0781.65098
[22] S. Oualibouch and N. el Mansouri. Proximal domain decomposition algorithms and applications to elliptic problems. In R. Glowinski, J. Periaux, Z-C. Shi, and O. Widlund, editors, Domain decomposition methods in sciences and engineering, 8th international conference, Beijing , China, pages 91-98. Wiley, 1997.
[23] R. Rannacher. On the convergence of the Newton-Raphson method for strongly nonlinear finite element equations. In P. Wriggers and W. Wagner, editors, Nonlinear computational mechanics, pages 11-30. Springer-Verlag, 1991.
[24] Arnold Reusken, Convergence of the multilevel full approximation scheme including the \?-cycle, Numer. Math. 53 (1988), no. 6, 663 – 686. · Zbl 0636.65107 · doi:10.1007/BF01397135 · doi.org
[25] Recent advances in matrix theory, Proceedings of an Advanced Seminar Conducted by the Mathematics Research Center, United States Army, at the University of Wisconsin, Madison, October 1 4-16, vol. 1963, The University of Wisconsin Press, Madison, Wis., 1964.
[26] I. Sharapov. Multilevel subspace correction for large scale optimization problems. Technical Report CAM-97-31, University of California at Los Angeles, 1997.
[27] Barry F. Smith, Petter E. Bjørstad, and William D. Gropp, Domain decomposition, Cambridge University Press, Cambridge, 1996. Parallel multilevel methods for elliptic partial differential equations. · Zbl 0857.65126
[28] X.-C. Tai. Parallel function decomposition and space decomposition methods with applications to optimisation, splitting and domain decomposition. Report No. 231-1992, Institut für Mathematik, TechnischeUniversität Graz, 1992. Available online at http://www.mi.uib.no/ tai.
[29] X.-C. Tai. Parallel function and space decomposition methods. In P. Neittaanmäki, editor, Finite element methods, fifty years of the Courant element, Lecture notes in pure and applied mathematics, volume 164, pages 421-432. Marcel Dekker inc., 1994. Available online at http://www.mi.uib.no/ tai. CMP 95:03
[30] Xue Cheng Tai, Domain decomposition for linear and nonlinear elliptic problems via function or space decomposition, Domain decomposition methods in scientific and engineering computing (University Park, PA, 1993) Contemp. Math., vol. 180, Amer. Math. Soc., Providence, RI, 1994, pp. 355 – 360. · Zbl 0817.65121 · doi:10.1090/conm/180/01992 · doi.org
[31] X.-C. Tai. Parallel function and space decomposition methods - Part I. function decomposition. Beijing Mathematics, 1, part 2:104-134, 1995. Available online at http://www.mi.uib.no/ tai.
[32] X.-C. Tai. Parallel function decomposition and space decomposition methods: Part II. space decomposition. Beijing Mathematics, 1, part 2:135-152, 1995. Available online at http://www.mi.uib.no/ tai.
[33] Xue-Cheng Tai and Magne Espedal, Rate of convergence of some space decomposition methods for linear and nonlinear problems, SIAM J. Numer. Anal. 35 (1998), no. 4, 1558 – 1570. · Zbl 0915.65063 · doi:10.1137/S0036142996297461 · doi.org
[34] X.-C. Tai and J. Xu. Global convergence of subspace correction methods for convex optimization problems. Report no. 114, Department of Mathematics, University of Bergen, Norway, 1998. Available online at http://www.mi.uib.no/ tai.
[35] Olof B. Widlund, Some Schwarz methods for symmetric and nonsymmetric elliptic problems, Fifth International Symposium on Domain Decomposition Methods for Partial Differential Equations (Norfolk, VA, 1991) SIAM, Philadelphia, PA, 1992, pp. 19 – 36. · Zbl 0772.65025
[36] J. Xu. Theory of Multilevel Methods. PhD thesis, Cornell University, 1989.
[37] Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581 – 613. · Zbl 0788.65037 · doi:10.1137/1034116 · doi.org
[38] Jinchao Xu, A novel two-grid method for semilinear elliptic equations, SIAM J. Sci. Comput. 15 (1994), no. 1, 231 – 237. · Zbl 0795.65077 · doi:10.1137/0915016 · doi.org
[39] Jinchao Xu, Two-grid discretization techniques for linear and nonlinear PDEs, SIAM J. Numer. Anal. 33 (1996), no. 5, 1759 – 1777. · Zbl 0860.65119 · doi:10.1137/S0036142992232949 · doi.org
[40] Jun Zou, A new fast solver — monotone MG method (MMG), J. Comput. Math. 5 (1987), no. 4, 325 – 335. · Zbl 0648.65069
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.