Mathematics of Computation

Global and uniform convergence of subspace correction methods for some convex optimization problems

Author(s): Xue-Cheng Tai; Jinchao Xu.
Journal: Math. Comp. 71 (2002), 105-124.
MSC (2000): Primary 65N22, 65N55, 65K10, 65J15
Posted: May 11, 2001
Retrieve article in: PDF DVI PostScript
This article is available free of charge

This paper gives 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 for solving some nonlinear elliptic boundary value problems.

1.: A. Axelsson and W. Layton.
A two-level method for the discretization of nonlinear boundary value problems.
SIAM J. Numer. Anal., 33:2359-2374, 1996. MR 98c:65181
2.: R. Bank and D. J. Rose.
Analysis of a multilevel iterative method for nonlinear finite element equations.
Math. Comp., 39:453-465, 1982. MR 83j:65105
3.: J. H. Bramble, J. E. Pasciak, J. Wang, and J. Xu.
Convergence estimates for product iterative methods with applications to domain decomposition.
Math. Comp., 57:1-21, 1991. MR 92d:65094
4.: X.-C. Cai and M. Dryja.
Domain decomposition methods for monotone nonlinear elliptic problems.
In D. E. Keyes and Xu, editors, Proceeding of the seventh international conference on domain decomposition methods in Science and scientific computing (Penn. State Univ.), pages 21-28. AMS, Providence, 1994. MR 95j:65157
5.: J. Cea.
Optimisation - théorie et algorithmes.
Dunod, 1971. MR 45:7941
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.: P. G. Ciarlet.
The Finite Element Method for Elliptic Problems.
North-Holland, Amsterdam, 1978. MR 58:25001
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
9.: J. Douglas, T. Dupont, and L. Wahlbin.
The stability in of the -projection into finite element function spaces.
Numer. Math., 23:193-197, 1975. MR 52:4669
10.: M. Dryja and W. Hackbusch.
On the nonlinear domain decomposition method.
BIT, 37:296-311, 1997. MR 97m:65100
11.: M. Dryja and O. B. Widlund.
Towards a unified theory of domain decomposition algorithms for elliptic problems.
In Third International Symposium on Domain Decomposition Methods for Partial Differential Equations (Houston, TX, 1989), pages 3-21. SIAM, Philadelphia, PA, 1990. MR 91m:65294
12.: I. Ekeland and R. Temam.
Convex analysis and variational problems.
North-Holland, Amsterdam, 1976. MR 57:3931b
13.: E. Gelman and J. Mandel.
On multilevel iterative methods for optimization problems.
Math. Programming, 48:1-17, 1990. MR 91b:90180
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. Fr. Autom. Inf. Rech. Oper. Ser. Rouge Anal. Numér. 9: 41-76, 1975. MR 52:9645
15.: M. Griebel and P. Oswald.
On the abstract theory of additive and multiplicative Schwarz algorithms.
Numer. Math., 70:163-180, 1995. MR 96a:65164
16.: W. Hackbusch and A. Reusken.
Analysis of a damped nonlinear multilevel method.
Numer. Math., 55:225-246, 1989. MR 90f:65194
17.: R. Kornhuber.
Adaptive monotone multigrid methods for nonlinear variational problems.
Teubner, Stuttgart, 1997. MR 98e:65054
18.: R. Kornhuber.
Globally convergent multigrid methods for porous medium type equations.
Preprint, 1999.
19.: P. L. Lions.
On the Schwarz alternating method. I.
In First International Symposium on Domain Decomposition Methods for Partial Differential Equations, pages 1-42, Philadelphia, PA, 1988. SIAM. MR 90a:65248
20.: J. Mandel.
Algebric study of a multigrid method for some free boundary problems.
Comptes Rendus Academic of Science Paris, Series I, 298:77-95, 1984. MR 86i:49035
21.: S. F. McCormick.
Multilevel projection methods for partial differential equations, volume 62 of CBMS-NSF regional conference series in applied mathematics.
SIAM, Philadelphia, 1992. MR 93b:65137
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.: A. Reusken.
Convergence of the multilevel full approximation scheme including the V-cycle.
Numer. Math., 53:663-686, 1988. MR 89k:65072
25.: H. Schneider, editor.
Recent advances in matrix theory. The University of Wisconsin press, 1964. MR 29:2265
26.: I. Sharapov.
Multilevel subspace correction for large scale optimization problems.
Technical Report CAM-97-31, University of California at Los Angeles, 1997.
27.: B. F. Smith, P. E. Bjørstad, and W. D. Gropp.
Domain decomposition: Parallel multilevel methods for elliptic partial differential equations.
Cambridge Univ. Press, Cambridge, 1996. MR 98g:65003
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.: X.-C. Tai.
Domain decomposition for linear and nonlinear elliptic problems via function or space decomposition.
In D. Keyes and J. Xu, editors, Domain decomposition methods in scientific and engineering computing (Proc. of the 7th international conference on domain decomposition, Penn. State University, 1993), pages 355-360. American Mathematical Society, 1995. MR 95k:65121
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.: X.-C. Tai and M. Espedal.
Rate of convergence of some space decomposition method for linear and nonlinear elliptic problems.
SIAM J. Numer. Anal., 35:1558-1570, 1998. MR 99k:65101
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.: O. B. Widlund.
Some Schwarz methods for symmetric and nonsymmetric elliptic problems.
In Proceedings of the fifth international sympsium on domain decomposition methods for partial differential equations, Norfolk, May, 1991, Philadelphia, 1992. SIAM. MR 93j:65202
36.: J. Xu.
Theory of Multilevel Methods.
PhD thesis, Cornell University, 1989.
37.: J. Xu.
Iteration methods by space decomposition and subspace correction.
SIAM Rev., 34:581-613, 1992. MR 93k:65029
38.: J. Xu.
A novel two-grid method for semilinear elliptic equations.
SIAM J. Sci. Comp., 15:231-237, 1994. MR 94m:65178
39.: J. Xu.
Two-grid discretization techniques for linear and nonlinear PDEs
SIAM J. Numer. Anal., 27:1759-1777, 1996. MR 97i:65169
40.: J. Zou.
A new fast solver - monotone MG method (MMG).
J. Comp. Math., 5:325-335, 1987. MR 89k:65148

Retrieve articles in Mathematics of Computation with MSC (2000): 65N22, 65N55, 65K10, 65J15

Xue-Cheng Tai
Affiliation: Department of Mathematics, University of Bergen, Johannes Brunsgate 12, 5007, Bergen, Norway
Email: tai@mi.uib.no

Jinchao Xu
Affiliation: Center for Computational Mathematics and Applications and Department of Mathematics, Pennsylvania State University, University Park, Pennsylvania 16802
Email: xu@math.psu.edu

DOI: 10.1090/S0025-5718-01-01311-4
PII: S 0025-5718(01)01311-4
Keywords: Parallel, multigrid, domain decomposition, nonlinear, elliptic equation, space decomposition, convex optimization
Received by editor(s): March 10, 1998
Received by editor(s) in revised form: September 15, 1999 and March 24, 2000
Posted: May 11, 2001
Additional Notes: The work of the first author was partially supported by the Norwegian Research Council Strategic Institute Program within Inverse Problems at RF--Rogaland Research.
The work of the second author was partially supported by NSF DMS-9706949 NSF ACI-9800244, NASA NAG2-1236 through Pennsylvania State University.
Copyright of article: Copyright 2001, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS