Please use this identifier to cite or link to this item:
https://ah.lib.nccu.edu.tw/handle/140.119/90576| 題名: | 平行疊代法解互補問題 Parallel Iterative Methods for Complementarity Problem |
作者: | 張泰生 | 貢獻者: | 楊建民 張泰生 |
日期: | 1989 | 上傳時間: | 4-May-2016 | 摘要: | 摘要\r\n本論文係研究和發展平行疊代法(parallel iterative method)以解決數學規劃(mathematical programming)中之互補問題(complementarity problem)。互補問題源自解決國防軍事、工程、經濟及管理科學等領域之應用，而由於近年來各種超級或平行電腦不斷地創新，使得發展平行演算法，以充分並有效地應用超級或平行電腦來解決大型科學計算的問題日趨重要。\r\n在本篇論文中，我們分別探討線性互補問題以及非線性互補問題，首先我們發展出一半非同步(semi-asynchronous)法來解線性互補問題，此法之特性在於其能大幅地減低因同步法所造成處理機閒置(idling)之冗額成本(overhead)；同時，也放寬了非同步法對問題所加諸之限制，因而擴大了半非同步法所能應用之範圍。我們也建立了有關該法收斂性(convergence)之理論根據。此外，線性互補問題之探討，實為進一步研究非線性互補問題之基礎。\r\n其次，我們提出一個整體性之架構，探討平行牛頓法(Newton method)及其各種變形(variations)來解決各種非線性互補問題，比較並研究各種方法的特性、限制及執行效率。\r\n然後，針對上述各種演算法，我們在教育部電算中心之IBM 3090上發展並模擬各法之平行運算，經由廣泛地測試執行，以獲得具體之數值結果，來檢驗各平行演算法之效率，並比較研究各法之適用性與優劣。最後，我們也提出一些相關之問題，以供未來後續研究之參考。 | 參考文獻: | 參考文獻:\r\n[1] M. Aganagic [1978], \"Iterative Methods for Linear Complementarity Problems,\" Technical Report SOL 78-10 Systems Optimization Laboratory, Department of\r\nOperations Research, Stanford University.\r\n[2] B. H. Ahn [1981], \"Computation of Asymmetric Linear Complementarity Problem by Iterative Method,\"Journal of Optimization Theory and Applications 33,pp . 175-185.\r\n[3] J. Barnes [1965], \"An Algorithm for Solving Nonlinear Equations Based on the Secant Method,\" Computer Journal 8,pp. 66-72.\r\n[4] G. M. Baudet [1978], \"Asynchronous Iterative Methods for Multiprocessors\", Journal of the Association for Computing Machinery 22, pp. 226-244.\r\n[5] D. P. Bertsekas [1983], \"Distributed Asynchronous Computation of Fixed Point\", Mathematical Programming 27, pp. 107-120.\r\n[6] R. P. Brent [1973],\"Some Efficient Algorithms for Solving Systems of Nonlinear Equations,\" SIAM Journal On Numerical Analysis 10, PP. 327-344.\r\n[7] Y. C. Cheng [1981], \"Iterative Methods for Solving Linear Complementarity and Linear Programming Problems\",Ph.D. dissertation, Department of Computer Science, University of Wisconsin (Madison Wisconsin).\r\n[8] Y. C. Cheng [1984], \"On the Gradient-Projection Method for Solving the Nonsymmetric Linear Complementarity Problem\" , Journal of Optimization Theory and\r\nApplications 43, pp. 527-541.\r\n[9] R. W. Cottle, G. H. Golub and R. S. Sacher [1978],\"On the Solution of Large Structured Linear Complementarity Problems: The Block Partitioned Case\" ,Applied Mathematics and Optimization 4. pp. 347-363.\r\n[10] C. W. Cryer [1971], \"The Solution of a Quadratic Programming Problem Using Systematic Overrelaxation,\"SIAM Control 9, pp. 385-392.\r\n[11] G. B. Dantzig [1963], Linear Programming and Extensions,Princeton University Press, Princeton, New Jersey.\r\n[12] G. B. Dantzig, M. A. H. Dempster and M. J. Kallio (Eds.) [1981], Large-Scale Linear Programming. Vol. 1,Proceedings of a IIASA workshop 2-6 June 1980,International Institute for Applied Systems Analysis,Laxenburg,Austria.\r\n[13] R. S. Dembo. S. C. Eisenstat and T. Steihaug [1982],\"Inexact Newton Methods,\" SIAM Journal on Numerical Analysis 19, pp. 400-408.\r\n[14] B. C. Eaves [1971], \"On Quadratic Programming\",Management Science 17, PP. 698-711.\r\n[15] B. C. Eaves [1983], \"Where Solving for Stationary Points by LCP`s IS Mixing Newton Iterates,\"B. C. Eaves. F. J. Gould. H. O. Peitgen and M. J. Todd(eds.) Homotopy Methods and Global Convergence,(Plenum Press. New York) PP. 63-78.\r\n[16] T. L. Friesz et. al. [1983], \"A Nonlinear Complementarity Formulation and Solution Procedure for The General Derived Demand Network Equilibrium Problem\" Journal of Regional Science, V.23, No.3, PP. 337-359.\r\n[17] S. P. Han and o. L. Mangasarian [1983], \"A Dual Differentiable Exact Penalty Function,\" Mathematical Programming 25, pp. 293-306.\r\n[18] C. Hildreth [1957], A Quadratic Programming Procedure,Naval Research Logistics Quarterly 4, PP. 79-85,Erratum, ibid, p.361.\r\n[19] R. W. Hockney [1985], \"MIMD Computing in the USA -1984\", Parallel Computing 2, pp. 119-136.\r\n[20] N. H. Josephy [1979a], \"Newton`s Method for Generalized Equations,\" Technical Summary Report No. 1965,Mathematics Research Center, University of Wisconsin\r\n(Madison, Wisconsin).\r\n[21] N. H. Josephy [1979b], \"Quasi -Newton Methods for Generalized Equations,\" Technical Summary Report No. 1966, Mathematics Research Center, University of\r\nWisconsin (Madison, Wisconsin).\r\n[22] N. Karmarkar [1984], \"A New Polynomial-Time Algorithm for Linear Programming,\" Combinatorica 4, pp. 375-395.\r\n[23] H. T. Kung [1976], \"Synchronized and Asynchronous Parallel Algorithms for Multiprocessors\", in J. F. Traub ed., Algorithms and Complexity: New Directions\r\nand Recent Results (Academic Press) pp. 153-200.\r\n[24] Y. Y. Lin and J. S. Pang [1987], \"Iterative Methods for Large Convex Quadratic Programs: A Survey\", SIAM Journal on Control and Optimization 25,pp. 383-411.\r\n[25] O. L. Mangasarian [1977], \"Solution of Symmetric Linear Complementarity Problems by Iterative Methods\", Journal of Optimization Theory and Applications 22, pp.465-485.\r\n[26] O. L. Mangasarian [1981], \"Iterative Solution of Linear Programs,\" SIAM Journal on Numerical Analysis 18, pp. 606-614.\r\n[27] O. L. Mangasarian [1984a], \"Normal Solutions of Linear Programs,\" Mathematical Programming Study 22, pp. 206-216.\r\n[28] O. L. Mangasarian [1984b], \"Sparsity Preserving SOR Algorithms for Separable Quadratic and Linear Programming Problem,\" Computers and Operations Research, Vol. 11,pp. 105:-112.\r\n[29] O. L. Mangasarian and R. De Leone [1986a], \"Parallel Successive Overrelaxation Methods for Symmetric Linear Complementarity Problems and Linear Programs\",Mathematics Research Center Report #2947, University of\r\nWisconsin (Madison, Wisconsin).\r\n[30] O. L. Mangasarian and R. De Leone [1986b],\"Paralle1 Gradient Projection Successive overrelaxation for Symmetric Linear Complementarity Problems and Linear Programs\", Technical Report #659, Department of Computer Sciences, University of Wisconsin (Madison,Wisconsin).\r\n[31] H. Mukai [1979], \"Parallel Algorithms for Solving Systems of Nonlinear Equations\", Proceedings of the 17th Annual Allerton Conference on Communications,Control and Computations pp. 37-46.\r\n[32] D. P. O`Leary and R. E. White [1985], \"Multi-splittings of Matrices and Parallel Solution of Linear Systems\",SIAM Journal on Algebraic and Discrete Mathematics 6,pp. 630-640.\r\n[33] J. M. Ortega and W. C. Rheinboldt [1970], Iterative Solution of Nonlinear Equations in Several Variables, Academic Press.\r\n[34] J. M. Ortega and R. G. Voigt [1985], \"Solution of Partial Differerntial Equations on Vector and Parallel Computers\" , SIAM Review Vol 27, No.2, PP. 149-213.\r\n[35] J. S. Pang [1982], \"On the Convergence of a Basic Iterative Method for the Implicit Complementarity Problem\", Journal of Optimization Theory and Applications 37. pp. 149-162.\r\n[36] J. S. Pang [1984a], \"Necessary and Sufficient Conditions for the Convergence of Iterative Methods for the Linear Complementarity Problem\". Journal of Optimization\r\nTheory and Applications 42. PP. 1-18.\r\n[37] J. S. Pang [1984b], \"Solution of the General Multicommodity Spatial Equilibrium Porblem by Variational and Complementarity Methods\". Journal of Regional Science, V. 24, No.3,pp. 403-414.\r\n[38] J. S. Pang [1986a], \"More Results on the Convergence of Iterative Methods for the Symmetric Linear Complementarity Problem\", Journal of Optimization Theory and Applications 49, pp. 107-134.\r\n[39] J. S. Pang [1986b], \"Inexact Newton Methods for the Nonlinear Complementarity Problem\", Mathematical Programming 36,pp. 54-71.\r\n[40] J. S. Pang [1987], \"A Posteriori Error Bounds for the Linearly-Constrained Variational Inequality Problem, \"Mathematices of Operations Research. to appear,\r\n[41] J. S. Pang and D. Chan [1982], \"Iterative Methods for Variational and Complementarity Problems,\" Mathematical Programming 24, pp. 284-313.\r\n[42] J. S. Pang and J. M. Yang [1987a], \"Two-stage Paralle1 Iterative Methods for the Symmetric Linear Complementarity Problem,\" to appear in Annals of Operations Research: Parallel Optimization on Novel Computer Architectures (1988).\r\n[43] \"J. S. Pang and J. M. Yang [1987b], \"Paralle1 Newton Methods for the Nonlinear Complementarity Problem\",Mathematical Programming Study: Proceedings of Symposium on Parallel Optimization. Madison,Wisconsin (1987).\r\n[44] J. S. Pang and J. M. Yang [1987c], \"Computationa1 Experience with Solving Linear Programs by Iterative Methods on CRAY Supercomputers\", Proceedings of the Third Science and Engineering Symposium. Minneapolis,Minnesota (1987).\r\n[45] E. Polak [1974], \"A Globally Converging Secant Method with Applications to Boundary Value Problems,\" SIAM Journal on Numerical Analysis 11, pp. 529-537.\r\n[46] R. T. Rockafellar [1976a], \"Monotone Operators and the Proximal Point Algorithm,\" SIAM Journal on Control and Optimization 14, PP. 877-898.\r\n[47] R. T. Rockafellar [1976b], \"Augmented Lagrangians and Application of the Proximal Point Algorithm in Convex Programming,\" Mathematics of Operations Research 1,pp. 97-116.\r\n[48] F. Robert [1969], \"Blocs-H-Matrices et Convergence des Methodes Iterative Classiques par Blocs\", Linear Algebra and its Applications 2, PP. 223-265.\r\n[49] S. M. Robinson [1980],\"Strongly Regular Generalized Equations,\" Mathematics of Operations Research 5,pp. 43-62.\r\n[50] V. E. Shamanskii [1967], \"On a Modification of Newton`s Method,\" Ukrain, Mat. Z. 19, PP. 133-138.\r\n[51] T. H. Shiau [1984], \"An Iterative Scheme for Linear Complementarity Problems,\" Technical Report #2737,Mathematices Research Center, University of Wisconsin-Madison.\r\n[52]J. Traub [1964], Iterative Methods for the Solution of Equations, Prentice Hall, Englewood Cliffs, New Jersey.\r\n[53] P. Wolfe [1959], \"The Secant Method for Simultaneous Nonlinear Equations,\" Communications of the ACM 2,PP. 12-14.\r\n[54J J. M. Yang [1987], \"Parallel Iterative Methods for Complementarity and Linear Programming Problems\" Ph.D. dissertation, School of Management Science,University of Texas at Dallas.\r\n[55] S. A. Zenios and J. M. Mulvey [1986], \"Nonlinear Network Programming on Vector Supercomputers: A Study on the CRAY X-MP\", Operations Research 34, pp. 667-682.\r\n[56] S. A. Zenios and R. R. Meyer (Eds.) [1987], Annals of Operations Research: Parallel Optimization on Novel Computer Architectures, forthcoming. | 描述: | 碩士 國立政治大學 應用數學系 |
資料來源: | http://thesis.lib.nccu.edu.tw/record/#B2002005820 | 資料類型: | thesis |
| Appears in Collections: | 學位論文 |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| index.html | 115 B | HTML2 | View/Open |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.