政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/90576
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  全文筆數/總筆數 : 113393/144380 (79%)
造訪人次 : 51239068      線上人數 : 851
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜尋範圍 查詢小技巧：
  • 您可在西文檢索詞彙前後加上"雙引號"，以獲取較精準的檢索結果
  • 若欲以作者姓名搜尋，建議至進階搜尋限定作者欄位，可獲得較完整資料
    •  進階搜尋
    政大機構典藏 > 理學院 > 應用數學系 > 學位論文 >  Item 140.119/90576


    請使用永久網址來引用或連結此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/90576


    題名: 平行疊代法解互補問題
    Parallel Iterative Methods for Complementarity Problem
    作者: 張泰生
    貢獻者: 楊建民
    張泰生
    日期: 1989
    上傳時間: 2016-05-04 14:31:26 (UTC+8)
    摘要: 摘要
    本論文係研究和發展平行疊代法(parallel iterative method)以解決數學規劃(mathematical programming)中之互補問題(complementarity problem)。互補問題源自解決國防軍事、工程、經濟及管理科學等領域之應用，而由於近年來各種超級或平行電腦不斷地創新，使得發展平行演算法，以充分並有效地應用超級或平行電腦來解決大型科學計算的問題日趨重要。
    在本篇論文中，我們分別探討線性互補問題以及非線性互補問題，首先我們發展出一半非同步(semi-asynchronous)法來解線性互補問題，此法之特性在於其能大幅地減低因同步法所造成處理機閒置(idling)之冗額成本(overhead)；同時，也放寬了非同步法對問題所加諸之限制，因而擴大了半非同步法所能應用之範圍。我們也建立了有關該法收斂性(convergence)之理論根據。此外，線性互補問題之探討，實為進一步研究非線性互補問題之基礎。
    其次，我們提出一個整體性之架構，探討平行牛頓法(Newton method)及其各種變形(variations)來解決各種非線性互補問題，比較並研究各種方法的特性、限制及執行效率。
    然後，針對上述各種演算法，我們在教育部電算中心之IBM 3090上發展並模擬各法之平行運算，經由廣泛地測試執行，以獲得具體之數值結果，來檢驗各平行演算法之效率，並比較研究各法之適用性與優劣。最後，我們也提出一些相關之問題，以供未來後續研究之參考。
    參考文獻: 參考文獻:
    [1] M. Aganagic [1978], "Iterative Methods for Linear Complementarity Problems," Technical Report SOL 78-10 Systems Optimization Laboratory, Department of
    Operations Research, Stanford University.
    [2] B. H. Ahn [1981], "Computation of Asymmetric Linear Complementarity Problem by Iterative Method,"Journal of Optimization Theory and Applications 33,pp . 175-185.
    [3] J. Barnes [1965], "An Algorithm for Solving Nonlinear Equations Based on the Secant Method," Computer Journal 8,pp. 66-72.
    [4] G. M. Baudet [1978], "Asynchronous Iterative Methods for Multiprocessors", Journal of the Association for Computing Machinery 22, pp. 226-244.
    [5] D. P. Bertsekas [1983], "Distributed Asynchronous Computation of Fixed Point", Mathematical Programming 27, pp. 107-120.
    [6] R. P. Brent [1973],"Some Efficient Algorithms for Solving Systems of Nonlinear Equations," SIAM Journal On Numerical Analysis 10, PP. 327-344.
    [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).
    [8] Y. C. Cheng [1984], "On the Gradient-Projection Method for Solving the Nonsymmetric Linear Complementarity Problem" , Journal of Optimization Theory and
    Applications 43, pp. 527-541.
    [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.
    [10] C. W. Cryer [1971], "The Solution of a Quadratic Programming Problem Using Systematic Overrelaxation,"SIAM Control 9, pp. 385-392.
    [11] G. B. Dantzig [1963], Linear Programming and Extensions,Princeton University Press, Princeton, New Jersey.
    [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.
    [13] R. S. Dembo. S. C. Eisenstat and T. Steihaug [1982],"Inexact Newton Methods," SIAM Journal on Numerical Analysis 19, pp. 400-408.
    [14] B. C. Eaves [1971], "On Quadratic Programming",Management Science 17, PP. 698-711.
    [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.
    [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.
    [17] S. P. Han and o. L. Mangasarian [1983], "A Dual Differentiable Exact Penalty Function," Mathematical Programming 25, pp. 293-306.
    [18] C. Hildreth [1957], A Quadratic Programming Procedure,Naval Research Logistics Quarterly 4, PP. 79-85,Erratum, ibid, p.361.
    [19] R. W. Hockney [1985], "MIMD Computing in the USA -1984", Parallel Computing 2, pp. 119-136.
    [20] N. H. Josephy [1979a], "Newton`s Method for Generalized Equations," Technical Summary Report No. 1965,Mathematics Research Center, University of Wisconsin
    (Madison, Wisconsin).
    [21] N. H. Josephy [1979b], "Quasi -Newton Methods for Generalized Equations," Technical Summary Report No. 1966, Mathematics Research Center, University of
    Wisconsin (Madison, Wisconsin).
    [22] N. Karmarkar [1984], "A New Polynomial-Time Algorithm for Linear Programming," Combinatorica 4, pp. 375-395.
    [23] H. T. Kung [1976], "Synchronized and Asynchronous Parallel Algorithms for Multiprocessors", in J. F. Traub ed., Algorithms and Complexity: New Directions
    and Recent Results (Academic Press) pp. 153-200.
    [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.
    [25] O. L. Mangasarian [1977], "Solution of Symmetric Linear Complementarity Problems by Iterative Methods", Journal of Optimization Theory and Applications 22, pp.465-485.
    [26] O. L. Mangasarian [1981], "Iterative Solution of Linear Programs," SIAM Journal on Numerical Analysis 18, pp. 606-614.
    [27] O. L. Mangasarian [1984a], "Normal Solutions of Linear Programs," Mathematical Programming Study 22, pp. 206-216.
    [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.
    [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
    Wisconsin (Madison, Wisconsin).
    [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).
    [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.
    [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.
    [33] J. M. Ortega and W. C. Rheinboldt [1970], Iterative Solution of Nonlinear Equations in Several Variables, Academic Press.
    [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.
    [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.
    [36] J. S. Pang [1984a], "Necessary and Sufficient Conditions for the Convergence of Iterative Methods for the Linear Complementarity Problem". Journal of Optimization
    Theory and Applications 42. PP. 1-18.
    [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.
    [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.
    [39] J. S. Pang [1986b], "Inexact Newton Methods for the Nonlinear Complementarity Problem", Mathematical Programming 36,pp. 54-71.
    [40] J. S. Pang [1987], "A Posteriori Error Bounds for the Linearly-Constrained Variational Inequality Problem, "Mathematices of Operations Research. to appear,
    [41] J. S. Pang and D. Chan [1982], "Iterative Methods for Variational and Complementarity Problems," Mathematical Programming 24, pp. 284-313.
    [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).
    [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).
    [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).
    [45] E. Polak [1974], "A Globally Converging Secant Method with Applications to Boundary Value Problems," SIAM Journal on Numerical Analysis 11, pp. 529-537.
    [46] R. T. Rockafellar [1976a], "Monotone Operators and the Proximal Point Algorithm," SIAM Journal on Control and Optimization 14, PP. 877-898.
    [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.
    [48] F. Robert [1969], "Blocs-H-Matrices et Convergence des Methodes Iterative Classiques par Blocs", Linear Algebra and its Applications 2, PP. 223-265.
    [49] S. M. Robinson [1980],"Strongly Regular Generalized Equations," Mathematics of Operations Research 5,pp. 43-62.
    [50] V. E. Shamanskii [1967], "On a Modification of Newton`s Method," Ukrain, Mat. Z. 19, PP. 133-138.
    [51] T. H. Shiau [1984], "An Iterative Scheme for Linear Complementarity Problems," Technical Report #2737,Mathematices Research Center, University of Wisconsin-Madison.
    [52]J. Traub [1964], Iterative Methods for the Solution of Equations, Prentice Hall, Englewood Cliffs, New Jersey.
    [53] P. Wolfe [1959], "The Secant Method for Simultaneous Nonlinear Equations," Communications of the ACM 2,PP. 12-14.
    [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.
    [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.
    [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
    顯示於類別:[應用數學系] 學位論文

    文件中的檔案:

    檔案 大小格式瀏覽次數
    index.html0KbHTML2486檢視/開啟


    在政大典藏中所有的資料項目都受到原著作權保護.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 回饋