Asynchronous gradient algorithms for a class of convex separable network flow problems

1. R.H.Barlow and D.J.Evans, “Synchronous and asynchronous iterative parallel algorithms for linear systems,” Comput. J., vol. 25, pp. 56–60, 1982.

   Google Scholar 

2. G.M.Baudet, “Asynchronous iterative methods for multiprocessors,” J. Assoc. Comput. Mach., vol. 2, pp. 226–244, 1978.

   Google Scholar 

3. D.P.Bertsekas, “Distributed dynamic programming,” IEEE Trans. Auto. Contr., vol. AC-27, pp. 610–616, 1982.

   Google Scholar 

4. D.P.Bertsekas, “Distributed asynchronous computation of fixed points” Mathematical Programming, vol. 27, pp. 107–120, 1983.

   Google Scholar 

5. D.P.Bertsekas and D.A.Castñon, “Parallel asynchronous primal-dual methods for the minimum cost flow problem,” Report LIDS-P-1998, Department of Electrical Engineering and Computer Science, M.I.T., Cambridge, MA, 1990.

   Google Scholar 

6. D.P.Bertsekas and D.A.Castañon, “Parallel synchronous and asynchronous implementation of the auction algorithm,” Parallel Computing, vol. 17, pp. 707–732, 1991.

   Google Scholar 

7. D.P.Bertsekas and D.A.Castañon, J.Eckstein, and S.Zenios, “Parallel computing in network optimization,” Report LIDS-P-2236, Department of Electrical Engineering and Computer Science, M.I.T., Cambridge, MA, 1994, to appear in Handbook on Operation Research and Management Science.

   Google Scholar 

8. D.P.Bertsekas and D.ElBaz, “Distributed asynchronous relaxation methods for convex network flow problems,” SIAM J. on Control and Optimization, vol. 25, pp. 74–85, 1987.

   Google Scholar 

9. D.P.Bertsekas and J.Tsitsiklis, Parallel and Distributed Computation, Numerical Methods, Prentice Hall, Englewood Cliffs, N.J., 1989.

   Google Scholar 

10. D.P.Bertsekas, P.Hossein, and P.Tseng, “Relaxation methods for network flow problems with convex arc costs,” SIAM Journal on Control and Optimization vol. 25, pp. 1219–1243, 1987.

    Google Scholar 

11. Y.Censor and A.Lent, “An iterative row-action method for interval convex programming,” Journal of Optimization Theory and Applications, vol. 34, pp. 321–353, 1981.

    Google Scholar 

12. Y.Censor and J.Segman, “On block-iterative entropy maximization,” Journal of Information and Optimization Sciences, vol. 8, pp. 275–291, 1987.

    Google Scholar 

13. E.Chajakis and S.A.Zenios, “Synchronous and asynchronous implementations of relaxation algorithms for nonlinear network optimization,” Parallel Computing, vol. 17, pp. 873–894, 1991.

    Google Scholar 

14. D.Chazan and W.Miranker, “Chaotic relaxation,” Linear Algebra Appl., vol. 2, pp. 199–222, 1969.

    Google Scholar 

15. R.DeLeone and O.L.Mangasarian, “Asynchronous parallel successive overrelaxation for the symmetric linear complementarity problem,” Mathematical Programming, vol. B42, pp. 117–128, 1971.

    Google Scholar 

16. J.D.P.Donnely, “Periodic chaotic relaxation,” Linear Algebra Appl., vol. 4, pp. 117–128, 1971.

    Google Scholar 

17. D.ElBaz, “M-functions and parallel asynchronous algorithms,” SIAM Journal on Numerical Analysis, vol. 27, pp. 136–140, 1990.

    Google Scholar 

18. D.ElBaz, “Asynchronous implementation of relaxation and gradient algorithms for convex network flow problems,” Parallel Computing, vol. 19, pp. 1019–1028, 1993.

    Google Scholar 

19. D.ElBaz, “Nonlinear systems of equations and parallel asynchronous iterative algorithms,” in Advances in Parallel Computing 9, Parallel Computing: Trends and Application, North Holland, Amsterdam, 1994, G.R.Joubert et al. (Eds.), pp. 89–96.

    Google Scholar 

20. D. El Baz, P. Spiteri, and J.C. Miellou, “Distributed asynchronous iterative methods with oder intervals for a class of nonlinear network flow problems,” LAAS Report 94244, June 1994.

21. M.N.ElTarazi, “Some convergence results for asynchronous algorithms,” Numerisch Mathematik, vol. 39, pp. 325–340, 1982.

    Google Scholar 

22. S.Li and T.Basar, “Asymptotic agreement and convergence of asynchronous stochastic algorithms,” IEEE Trans. Auto. Contr., vol. AC- 32, pp. 612–618, 1987.

    Google Scholar 

23. B.Lubachevsky and D.Mitra, “A chaotic asynchronous algorithm for computing the fixed point of nonnegative matrix of unit spectral radius,” J. Assoc. Comput. Mach., vol. 33, pp. 130–150, 1986.

    Google Scholar 

24. J.C.Miellou, “Algorithmes de relaxation chaotique à retards,” R.A.I.R.O., R-1, pp. 55–82, 1975.

    Google Scholar 

25. J.C.Miellou, “Itérations chaotiques à retards, étude de la convergence dans le cas d'espaces partiellement ordonnés,” C.R.A.S. Paris, vol. 280, pp. 233–236, 1975.

    Google Scholar 

26. J.C. Miellou, “Asynchronous iterations and order intervals,” in Parallel Algorithms and Architectures, M. Cosnard (Ed.), North Holland, 1986, pp. 85–96.

27. J.C.Miellou and P.Spiteri, “Two criteria for the convergence of asynchronous iterations,” in Computers and Computing, P.Chenin, C.diCrescenzo, and F.Robert (Eds.), Wiley-Masson, Paris 1985, pp. 91–95.

    Google Scholar 

28. D.Mitra, “Asynchronous relaxations for the numerical solution of differential equations by parallel processors,” SIAM J. Sci. Stat. Comput., vol. 8, pp. 43–58, 1987.

    Google Scholar 

29. S. Nielsen and S.A. Zenios, “Massively parallel algorithms for singly constrained convex programs,” ORSA Journal on Computing, vol. 4, 1992.

30. R.T.Rockafellar, Convex Analysis, Princeton University Press: Princeton, New Jersey, 1970.

    Google Scholar 

31. R.T.Rockafellar, Network Flows and Monotropic Optimization, John Wiley & Sons: New York, 1984.

    Google Scholar 

32. S.A.Zenios and R.A.Lasken, “Nonlinear network optimization on a massively parallel Connection Machine,” Annals of Operation Research, vol. 14, pp. 147–166, 1988.

    Google Scholar 

Download references