Convergence rate analysis of an asynchronous space decomposition method for convex minimization

Authors:
Xue-Cheng Tai and Paul Tseng

Journal:
Math. Comp. **71** (2002), 1105-1135

MSC (2000):
Primary 65J10, 65M55, 65Y05; Secondary 65K10, 65N55

DOI:
https://doi.org/10.1090/S0025-5718-01-01344-8

Published electronically:
November 14, 2001

MathSciNet review:
1898747

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We analyze the convergence rate of an asynchronous space decomposition method for constrained convex minimization in a reflexive Banach space. This method includes as special cases parallel domain decomposition methods and multigrid methods for solving elliptic partial differential equations. In particular, the method generalizes the additive Schwarz domain decomposition methods to allow for asynchronous updates. It also generalizes the BPX multigrid method to allow for use as solvers instead of as preconditioners, possibly with asynchronous updates, and is applicable to nonlinear problems. Applications to an overlapping domain decomposition for obstacle problems are also studied. The method of this work is also closely related to relaxation methods for nonlinear network flow. Accordingly, we specialize our convergence rate results to the above methods. The asynchronous method is implementable in a multiprocessor system, allowing for communication and computation delays among the processors.

**1.**L. Badea and J. Wang,*An additive Schwarz method for variational inequalities*, Math. Comp.**69**(2000), 1341-1354. MR**2001a:65075****2.**R. Bank,*Analysis of a multilevel iterative method for nonlinear finite element equations*, Math. Comp.**39**(1982), 453-465. MR**83j:65105****3.**R. Bank and T. F. Chan, PLTMGC: a multigrid continuation program for parametrized nonlinear systems, SIAM T. Sci. Statist. Comput.,**7**(1986), 540-559. MR**87d:65125****4.**D. P. Bertsekas, D. Castañon, J. Eckstein, and S. A. Zenios,*Parallel computing in network optimization*, Handbooks in Operations Research and Management Science 7: Network Models (Amsterdam) (M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, eds.), Elsevier Scientific, 1995, pp. 331-399. CMP**97:04****5.**D. P. Bertsekas and J. N. Tsitsiklis,*Parallel and distributed computation: Numerical methods*, Prentice-Hall, Englewood Cliffs, 1989.**6.**-,*Some aspects of parallel and distributed iterative algorithms--a survey*, Automatica**27**(1991), 3-21. MR**91m:65137****7.**J. Bramble and X. Zhang,*The analysis of multigrid methods*, Handbook of numerical analysis, Vol. VII, 173-415, North-Holland, Amsterdam, 2000. CMP**2001:08****8.**J. H. Bramble, J. E. Pasciak, and A. H. Schatz,*The construction of preconditioners for elliptic problems by substructuring. IV*, Math. Comp.**53**(1989), 1-24.MR**89m:65098****9.**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**(1991), 1-21. MR**92d:65094****10.**J. H. Bramble, J. E. Pasciak, and J. Xu,*Parallel multilevel preconditioners*, Math. Comp.**55**(1990), 1-22. MR**90k:65170****11.**A. Brandt,*Multilevel adaptive solutions to boundary value problems*, Math. Comp.**31**(1977), 333-390. MR**55:4714****12.**A. Brandt and C. W. Cryer,*Multigrid algorithms for the solution of linear complementary problems arising from free boundary problems*, SIAM J. Sci. Comput.**4**(1983), 655-684. MR**85h:65261****13.**J. V. Burke and P. Tseng,*A unified analysis of Hoffman's bound via Fenchel duality*, SIAM J. Optim.**6**(1996), 265-282. MR**97c:90120****14.**T. F. Chan and T. P. Mathew,*Domain decomposition algorithms*, Acta Numerica (1994), 61-143. MR**95f:65214****15.**T. F. Chan and I. Sharapov,*Subspace correction multilevel methods for elliptic eigenvalue problems*, Numer. Linear Algebra Appl.,**1**(1993), 1-7.**16.**D. Chazan and W. L. Miranker,*Chaotic relaxation*, Lin. Algeb. Appl.**2**(1969), 199-222. MR**40:5114****17.**P. G. Ciarlet,*The finite element method for elliptic problems*, North-Holland, Amsterdam, 1978. MR**58:25001****18.**M. Dryja and W. Hackbusch,*On the nonlinear domain decomposition method*, BIT**37**(1997), 296-311. MR**97m:65100****19.**M. Dryja and O. B. Widlund,*Towards a unified theory of domain decomposition algorithms for elliptic problems*, Third international symposium on domain decomposition methods for partial differential equations (Philadelphia, PA) (T. Chan, R. Glowinski, J. Periaux, and O. B. Widlund, eds.), SIAM, 1990. MR**91m:65294****20.**I. Ekeland and R. Temam,*Convex analysis and variational problems*, North-Holland, Amsterdam, 1976. MR**57:3931b****21.**B. H. Elton,*An asynchronous domain decomposition method for the two-dimensional Poisson equation*, Parallel processing for scientific computing, Vol. I, II (Norfolk, VA, 1993), SIAM, Philadelphia, PA, 1993, pp. 691-695. CMP**93:10****22.**A. Frommer, H. Schwandt, and D. B. Szyld,*Asychronous weighted additive Schwarz methods*, Electronic Trans. Numer. Anal.**5**(1997), 48-61. MR**98c:65046****23.**E. Gelman and J. Mandel,*On multilevel iterative methods for optimization problems*, Math. Programming**48**(1990), 1-17. MR**91b:90180****24.**R. Glowinski and P. Le Tallec,*Augmented Lagrangian and operator-splitting methods in nonlinear mechanics*, SIAM, Philadelphia, 1989. MR**91f:73038****25.**W. Hackbusch and H. D. Mittelmann,*On multigrid methods for variational inequalities*, Numer. Math.**42**(1983), 65-76. MR**84k:49010****26.**W. Hackbusch and A. Reusken,*Analysis of a damped nonlinear multilevel method*, Numer. Math.**55**(1989), 225-246. MR**90f:65194****27.**L. Hart and S. McCormick,*Asynchronous multilevel adaptive methods for solving partial differential equations on multiprocessors: basic ideas*, Parallel Comput.**12**(1989), no. 2, 131-144. MR**90m:65250****28.**R. H. Hoppe,*Multigrid solutions to the elastic plastic torsion problem in multiply connected domains*, Int. J. Numer. Methods Engin.**26**(1988), 631-646. MR**89a:73001****29.**R. H. W. Hoppe,*Two-sided approximations for unilateral variational inequalities by multigrid methods*, Optimization**16**(1987), 867-881. MR**88m:49004****30.**R. H. W. Hoppe and R. Kornhuber,*Adaptive multilevel methods for obstacle problems*, SIAM J. Numer. Anal.**31**(1994), 301-323. MR**95c:65181****31.**R. Kornhuber,*Monotone multigrid iterations for elliptic variational inequalities, II*, Numer. Math.**72**(1996), 481-499. MR**96k:65081****32.**O. A. Ladyzhenskaya and N. N. Uraltseva,*Linear and quasilinear elliptic equations*, Academic Press, 1968. MR**39:5941****33.**P. Le Tallec,*Domain decomposition methods in computational mechanics*, Comput. Mechan. Adv.**1**(1994), 121-220. MR**95b:65147****34.**Z.-Q. Luo and P. Tseng,*On the linear convergence of descent methods for convex essentially smooth minimization*, SIAM J. Control Optim.**30**(1992), 408-425. MR**93a:90064****35.**-,*Error bounds and convergence analysis of feasible descent methods: A general approach*, Ann. Oper. Res.**46**(1993), 157-178. MR**95a:90138****36.**J. Mandel,*A multilevel iterative method for symmetric, positive definite linear complementary problems*, Appl. Math. Optim.**11**(1984), 77-95.MR**85b:90082****37.**S. McCormick and D. Quinlan,*Asynchronous multilevel adaptive methods for solving partial differential equations on multiprocessors: performance results*, Parallel Comput.**12**(1989), no. 2, 145-156. MR**90m:65251****38.**S. F. McCormick,*Multilevel adaptive methods for partial differential equations*, Frontiers in Applied Mathematics, vol. 6, SIAM, Philadelphia, 1989.MR**91h:65200****39.**J.-C. Miellou, L. Giraud, A. Laouar, and P. Spiteri,*Subdomain decomposition methods with overlapping and asynchronous iterations*, Progress in partial differential equations: the Metz surveys, Longman Sci. Tech., Harlow, 1991, pp. 166-183. MR**94h:65125****40.**A. Quarteroni and A. Valli,*Domain decomposition methods for partial differential equations*, Oxford Science Publications, Oxford, 1999.**41.**R. Rannacher,*On the convergence of the Newton-Raphson method for strongly nonlinear finite element equations*, Nonlinear computational mechanics (P. Wriggers and W. Wagner, eds.), Springer-Verlag, 1991.**42.**R. T. Rockafellar,*Convex analysis*, Princeton University Press, Princeton, 1970. MR**43:445****43.**-,*Network flows and monotropic optimization*, Wiley-Interscience, New York, 1984.MR**89d:90156****44.**I. Sharapov,*Multilevel subspace correction for large scale optimization problems*, East-West J. Numer. Math.,**9**(2000), 233-252.**45.**B. F. Smith, P. E. Bjørstad, and W. D. Gropp,*Domain decomposition: Parallel multilevel algorithms for elliptic partial differential equations*, Cambridge University Press, Cambridge, 1996. MR**98g:65003****46.**A. K. Stagg and G. F. Carey,*Asynchronous nonlinear iteration and domain decomposition*, Parallel processing for scientific computing (Houston, TX, 1991), SIAM, Philadelphia, PA, 1992, pp. 281-286. CMP**93:05****47.**X.-C. Tai,*Parallel function decomposition and space decomposition methods with applications to optimisation, splitting and domain decomposition*, Preprint No. 231-1992, Institut für Mathematik, TechnischeUniversität Graz (1992), See also http://www.mi.uib.no/ tai.**48.**-,*Parallel function and space decomposition methods*, Finite element methods, fifty years of the Courant element, Lecture notes in pure and applied mathematics (P. Neittaanmäki, ed.), vol. 164, Marcel Dekker inc., 1994, pp. 421-432. See also http://www.mi.uib.no/ tai. MR**95d:65008****49.**-,*Domain decomposition for linear and nonlinear elliptic problems via function or space decomposition*, Domain decomposition methods in scientific and engineering computing (Proc. of the 7th international conference on domain decomposition, Penn. State University, 1993) (D. Keyes and J. Xu, eds.), Contemp. Math. 180, American Mathematical Society, 1994, pp. 355-360. MR**95k:65121****50.**-,*Parallel function decomposition and space decomposition methods: Part II. Space decomposition*, Beijing Mathematics**1, part 2**(1995), 135-152, See also http://www.mi.uib.no/ tai.**51.**-,*Convergence rate analysis of domain decomposition methods for obstacle problems*, East-West J. Numer. Math.,**9**(2000), 233-253.**52.**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**(1998), 1558-1570. MR**99k:65101****53.**X-C. Tai and J.-C. Xu,*Global and uniform convergence of subspace correction methods for some convex optimization problems*, Math. Comp., posted on May 11, 2001, PII S0025-5718(01)01311-4 (to appear in print).**54.**M. Tinkham,*Introduction to superconductivity*, McGraw Hill, New York, 1975.**55.**P. Tseng,*On the rate of convergence of a partially asynchronous gradient projection algorithm*, SIAM J. Optim.**1**(1991), 603-619. MR**92k:90096****56.**P. Tseng, D. P. Bertsekas, and J. N. Tsitsiklis,*Partially asynchronous, parallel algorithms for network flow and other problems*, SIAM J. Control Optim.**28**(1990), 678-710. MR**91e:65075****57.**J.-C. Xu,*Iterative methods by space decomposition and subspace correction*, SIAM Rev.**34**(1992), 581-613. MR**93k:65029****58.**-,*A novel two-grid method for semilinear elliptic equations*, SIAM J. Sci. Comp.**15**(1994), 231-237. MR**94m:65178****59.**-,*Two-grid discretization techniques for linear and nonlinear PDEs*, SIAM J. Numer. Anal.**27**(1996), 1759-1777. MR**97i:65169****60.**J. Zeng and S. Zhou,*On monotone and geometric convergence of Schwarz methods for two-sided obstacle problems*, SIAM J. Numer. Anal.**35**(1998), 600-616. MR**99d:65199**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65J10,
65M55,
65Y05,
65K10,
65N55

Retrieve articles in all journals with MSC (2000): 65J10, 65M55, 65Y05, 65K10, 65N55

Additional Information

**Xue-Cheng Tai**

Affiliation:
Department of Mathematics, University of Bergen, Johannes Brunsgate 12, 5007, Bergen, Norway

Email:
Xue-Cheng.Tai@mi.uib.no

**Paul Tseng**

Affiliation:
Department of Mathematics, Box 354350, University of Washington, Seattle, Washington 98195

Email:
tseng@math.washington.edu

DOI:
https://doi.org/10.1090/S0025-5718-01-01344-8

Keywords:
Convex minimization,
space decomposition,
asynchronous computation,
convergence rate,
domain decomposition,
multigrid,
obstacle problem

Received by editor(s):
September 27, 2000

Published electronically:
November 14, 2001

Additional Notes:
The work of the first author was supported by the Norwegian Research Council Strategic Institute Program within Inverse Problems at RF-Rogaland Research, and by Project SEP-115837/431 at Mathematics Institute, University of Bergen.

The work of the second author was supported by the National Science Foundation, Grant No. CCR-9311621.

Article copyright:
© Copyright 2001
American Mathematical Society