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

Tai, Xue-Cheng; Tseng, Paul

doi:10.1090/S0025-5718-01-01344-8

Convergence rate analysis of an asynchronous space decomposition method for convex Minimization
HTML articles powered by AMS MathViewer

by Xue-Cheng Tai and Paul Tseng PDF

Math. Comp. 71 (2002), 1105-1135 Request permission

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.

References

Lori Badea and Junping Wang, An additive Schwarz method for variational inequalities, Math. Comp. 69 (2000), no. 232, 1341–1354. MR 1665946, DOI 10.1090/S0025-5718-99-01164-3
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. MR 669639, DOI 10.1090/S0025-5718-1982-0669639-X
Randolph E. Bank and Tony F. Chan, PLTMGC: a multigrid continuation program for parameterized nonlinear elliptic systems, SIAM J. Sci. Statist. Comput. 7 (1986), no. 2, 540–559. MR 833920, DOI 10.1137/0907036
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.
D. P. Bertsekas and J. N. Tsitsiklis, Parallel and distributed computation: Numerical methods, Prentice-Hall, Englewood Cliffs, 1989.
Dimitri P. Bertsekas and John N. Tsitsiklis, Some aspects of parallel and distributed iterative algorithms—a survey, Automatica J. IFAC 27 (1991), no. 1, 3–21. MR 1087139, DOI 10.1016/0005-1098(91)90003-K
J. Bramble and X. Zhang, The analysis of multigrid methods, Handbook of numerical analysis, Vol. VII, 173–415, North-Holland, Amsterdam, 2000.
James H. Bramble, Joseph E. Pasciak, and Alfred H. Schatz, The construction of preconditioners for elliptic problems by substructuring. IV, Math. Comp. 53 (1989), no. 187, 1–24. MR 970699, DOI 10.1090/S0025-5718-1989-0970699-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. MR 1090464, DOI 10.1090/S0025-5718-1991-1090464-8
James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), no. 191, 1–22. MR 1023042, DOI 10.1090/S0025-5718-1990-1023042-6
Achi Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), no. 138, 333–390. MR 431719, DOI 10.1090/S0025-5718-1977-0431719-X
Achi Brandt and Colin W. Cryer, Multigrid algorithms for the solution of linear complementarity problems arising from free boundary problems, SIAM J. Sci. Statist. Comput. 4 (1983), no. 4, 655–684. MR 725660, DOI 10.1137/0904046
James V. Burke and Paul Tseng, A unified analysis of Hoffman’s bound via Fenchel duality, SIAM J. Optim. 6 (1996), no. 2, 265–282. MR 1387325, DOI 10.1137/0806015
Tony F. Chan and Tarek P. Mathew, Domain decomposition algorithms, Acta numerica, 1994, Acta Numer., Cambridge Univ. Press, Cambridge, 1994, pp. 61–143. MR 1288096, DOI 10.1017/S0962492900002427
T. F. Chan and I. Sharapov, Subspace correction multilevel methods for elliptic eigenvalue problems, Numer. Linear Algebra Appl., 1 (1993), 1–7.
D. Chazan and W. Miranker, Chaotic relaxation, Linear Algebra Appl. 2 (1969), 199–222. MR 251888, DOI 10.1016/0024-3795(69)90028-7
Philippe G. Ciarlet, The finite element method for elliptic problems, Studies in Mathematics and its Applications, Vol. 4, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. MR 0520174
M. Dryja and W. Hackbusch, On the nonlinear domain decomposition method, BIT 37 (1997), no. 2, 296–311. MR 1450962, DOI 10.1007/BF02510214
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. MR 1064335
Ivar Ekeland and Roger Temam, Analyse convexe et problèmes variationnels, Collection Études Mathématiques, Dunod, Paris; Gauthier-Villars, Paris-Brussels-Montreal, Que., 1974 (French). MR 0463993
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.
Andreas Frommer, Hartmut Schwandt, and Daniel B. Szyld, Asynchronous weighted additive Schwarz methods, Electron. Trans. Numer. Anal. 5 (1997), no. June, 48–61. MR 1460886
E. Gelman and J. Mandel, On multilevel iterative methods for optimization problems, Math. Programming 48 (1990), no. 1, (Ser. B), 1–17. MR 1049769, DOI 10.1007/BF01582249
Roland Glowinski and Patrick Le Tallec, Augmented Lagrangian and operator-splitting methods in nonlinear mechanics, SIAM Studies in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1989. MR 1060954, DOI 10.1137/1.9781611970838
W. Hackbusch and H.-D. Mittelmann, On multigrid methods for variational inequalities, Numer. Math. 42 (1983), no. 1, 65–76. MR 716474, DOI 10.1007/BF01400918
W. Hackbusch and A. Reusken, Analysis of a damped nonlinear multilevel method, Numer. Math. 55 (1989), no. 2, 225–246. MR 987387, DOI 10.1007/BF01406516
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 1026394, DOI 10.1016/0167-8191(89)90048-3
Ronald H. W. Hoppe, Multigrid solutions to the elastic plastic torsion problem in multiply connected domains, Internat. J. Numer. Methods Engrg. 26 (1988), no. 3, 631–646. MR 932352, DOI 10.1002/nme.1620260308
R. H. W. Hoppe, Two-sided approximations for unilateral variational inequalities by multigrid methods, Optimization 18 (1987), no. 6, 867–881. MR 916215, DOI 10.1080/02331938708843301
R. H. W. Hoppe and R. Kornhuber, Adaptive multilevel methods for obstacle problems, SIAM J. Numer. Anal. 31 (1994), no. 2, 301–323. MR 1276702, DOI 10.1137/0731016
Ralf Kornhuber, Monotone multigrid methods for elliptic variational inequalities. II, Numer. Math. 72 (1996), no. 4, 481–499. MR 1376109, DOI 10.1007/s002110050178
Olga A. Ladyzhenskaya and Nina N. Ural’tseva, Linear and quasilinear elliptic equations, Academic Press, New York-London, 1968. Translated from the Russian by Scripta Technica, Inc; Translation editor: Leon Ehrenpreis. MR 0244627
Patrick Le Tallec, Domain decomposition methods in computational mechanics, Comput. Mech. Adv. 1 (1994), no. 2, 121–220. MR 1263805
Zhi-Quan Luo and Paul Tseng, On the linear convergence of descent methods for convex essentially smooth minimization, SIAM J. Control Optim. 30 (1992), no. 2, 408–425. MR 1149076, DOI 10.1137/0330025
Zhi-Quan Luo and Paul Tseng, Error bounds and convergence analysis of feasible descent methods: a general approach, Ann. Oper. Res. 46/47 (1993), no. 1-4, 157–178. Degeneracy in optimization problems. MR 1260016, DOI 10.1007/BF02096261
Jan Mandel, A multilevel iterative method for symmetric, positive definite linear complementarity problems, Appl. Math. Optim. 11 (1984), no. 1, 77–95. MR 726977, DOI 10.1007/BF01442171
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 1026395, DOI 10.1016/0167-8191(89)90049-5
N. A. Marchenko and V. I. Pavlov, Numerical solution of elliptic problems of order $2m$ by the method of least squares using spline approximation on rectangular grids, Mat. Model. 2 (1990), no. 4, 121–132 (Russian, with English summary). MR 1064470
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, Pitman Res. Notes Math. Ser., vol. 249, Longman Sci. Tech., Harlow, 1991, pp. 166–183. MR 1251562
A. Quarteroni and A. Valli, Domain decomposition methods for partial differential equations, Oxford Science Publications, Oxford, 1999.
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.
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683
T. M. Abasov, The determination of saddle points, Akad. Nauk Azerbaĭdzhan. SSR Dokl. 43 (1987), no. 1, 15–18 (Russian, with English and Azerbaijani summaries). MR 926735
I. Sharapov, Multilevel subspace correction for large scale optimization problems, East-West J. Numer. Math., 9 (2000), 233–252.
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. MR 1410757
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.
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/$\tilde {\;}$tai.
M. Křížek, P. Neittaanmäki, and R. Stenberg (eds.), Finite element methods, Lecture Notes in Pure and Applied Mathematics, vol. 164, Marcel Dekker, Inc., New York, 1994. Fifty years of the Courant element; Papers from the International Conference held at the University of Jyväskylä, Jyväskylä, 1993. MR 1299984, DOI 10.1201/b16924
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. MR 1312410, DOI 10.1090/conm/180/01992
—, 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/$\tilde {\;}$tai.
—, Convergence rate analysis of domain decomposition methods for obstacle problems, East-West J. Numer. Math., 9 (2000), 233–253.
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. MR 1626026, DOI 10.1137/S0036142996297461
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).
M. Tinkham, Introduction to superconductivity, McGraw Hill, New York, 1975.
Paul Tseng, On the rate of convergence of a partially asynchronous gradient projection algorithm, SIAM J. Optim. 1 (1991), no. 4, 603–619. MR 1129424, DOI 10.1137/0801036
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), no. 3, 678–710. MR 1047430, DOI 10.1137/0328040
Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI 10.1137/1034116
Jinchao Xu, A novel two-grid method for semilinear elliptic equations, SIAM J. Sci. Comput. 15 (1994), no. 1, 231–237. MR 1257166, DOI 10.1137/0915016
Jinchao Xu, Two-grid discretization techniques for linear and nonlinear PDEs, SIAM J. Numer. Anal. 33 (1996), no. 5, 1759–1777. MR 1411848, DOI 10.1137/S0036142992232949
Jinping Zeng and Shuzi Zhou, On monotone and geometric convergence of Schwarz methods for two-sided obstacle problems, SIAM J. Numer. Anal. 35 (1998), no. 2, 600–616. MR 1618862, DOI 10.1137/S0036142995288920