簡易檢索 / 詳目顯示

回結果列表
研究生： 陳慧如
Chen, Hui-Ju
論文名稱： 廣義型分數規劃演算法之整合探討
An Integrated View of Algorithms for the Generalized Fractional Program
指導教授： 許瑞麟
Sheu, Ruey-Lin
學位類別： 碩士
Master
系所名稱： 理學院 - 數學系應用數學碩博士班
Department of Mathematics
論文出版年： 2005
畢業學年度： 93
語文別： 英文
論文頁數： 39
中文關鍵詞： “對偶”演算法 、廣義型分數規劃 、Dinkelbach 型演算法 、區間型演算法
外文關鍵詞： Dinkelbach-type algorithm, interval-type algorithm, generalized fractional program, “dual” algorithm
相關次數： 點閱：109  下載：2 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 　　本篇論文之目的是比較三種廣義型分數規劃的基本演算法，其中包括Dinkelbach 型，區間型，及“對偶”演算法。我們利用相同的幾何概念，即估計不同直線斜率之比值，使得三種演算法的收斂性證明有一致的架構。除此之外，我們發現區間型演算法事實上是一種二分法的變型。而對於“對偶”演算法我們也建立了原本文獻中沒有提到的強對偶性質。

    　The purpose of this paper is to compare three basic algorithms avail-able to the generalized fractional program, including the Dinkelbach-type, the interval-type, and a “dual” algorithm. We unify the convergence proofs
    for the three algorithms by the same geometrical concept which requires to estimate the ratio of slopes of different straight lines. In addition, we found that the interval type algorithm is in fact a version of bisection method. We
    also establish the strong duality properties for the “dual” algorithm which was not shown in the original paper.

    1 Introduction.........................................................................3 2 Dinkelbach-Type Algorithm............................................................5 3 Interval-Type Algorithm.............................................................17 3.1 Determine bar{lambda_{k+1}} from bar{lambda_k}>lambda^* (Case A).............17 3.2 Determine bar{lambda_{k+1}} from bar{lambda_k}<lambda^* (Case B).............19 3.3 bar{lambda_{k+1}} and bar{lambda_k} on Different Sides of lambda^* (Case C)..22 3.4 Interval-Type Algorithm...........................................................23 3.5 Summary and Discussion............................................................24 4“Dual”Algorithm....................................................................25 4.1 The Dual Problem..................................................................25 4.2 Discussion and Comparison of“Dual”Algorithm.....................................29 5 Conclusion and Future Research......................................................37 References............................................................................39

    [1] A.I. Barros, J.B.G. Frenk, S. Schaible, and S. Zhang, ”A new algorithm for generalized fractional programs,” Mathematical Programming 72 (1996) 147-175
    [2] J. Von Neumann, ”A model of general economic equilibrium,” Review of Economic Studies 13 (1945) 1-9
    [3] J.P. Crouzeix, J.A. Ferland and S. Schaible, ”An algorithm for generalized fractional programs,” Journal of Optimization Theory and Applications 47 (1985) 35-49
    [4] J.C. Bernard and J.A. Ferland, ”Convergence of interval-type algorithms for generalized fractional programming,” Mathematical Programming 43 (1989) 349-363
    [5] J.P. Crouzeix and J.A. Ferland, ”Algorithms for generalized fractional programming,”Mathematical Programming 52 (1991) 191-207
    [6] M. Sion, ”On general minimax theorems,” Pacific Journal of Mathematics 8 (1958) 171-176
    [7] R. Tyrrell Rockafellar, Conjugate Duality And Optimization (Philadelphia, Pa. 1974)
    [8] S. Schaible, ”A survey of fractional programming, ” in S. Schaible and W.T. Ziemba, eds., Generalized Concavity in Optimization and Economics (Academic Press, New York, 1981) 417-440
    [9] T. Ibaraki, ”Parametric approaches to fractional programs,” Mathematical Programming 26 (1983) 345-362
    [10] W. Dinkelbach, ”On non-linear fractional programming,” Management Science 13 (1967) 492-498

    下載圖示 校內：立即公開
    校外：2005-09-02公開
    QR CODE