在此篇論文中,我們提出求解廣義型分數規劃之通用演算法。典型的Dinkelbach型演算法,例如原Dinkelbach型演算法、``對偶"演算法及區間型演算法,使用特定的疊代參數,且經由複雜的分析而證得收斂性。我們設計的通用演算法在構造上既自然又簡單,算是傳統區間型演算法之強化版本。它不僅可以將所有的典型Dinkelbach型演算法一致化處理,也提供更強的收斂結果;而且收歛速度分析是藉由幾何上之觀察及凸函數之基本性質得來。如此一來,以往的結果因新的見解而更加有力。

In this dissertation, we propose a generic algorithm for solving generalized fractional programming. Classical Dinkelbach-type algorithms such as the original Dinkelbach-type algorithm, the ``dual" algorithm and the interval-type algorithm selected specific iterate parameters and proved the convergence with complicate analysis. Our generic algorithm is a natural and simple refinement of the interval-type algorithm. It not only unifies existing
versions of classical Dinkelbach-type algorithms, but gives a stronger convergence result and convergence rate analysis by way of geometric observations and fundamental properties of convex functions. As a result, the classical results are strengthened with new insights.

[1] Y. Almogy and O. Levin. A Class of Fractional Programming Problems. Operations Research, 19:57–67, 1971.
[2] M. Avriel, W. E. Diewert, S. Schaible, and I. Zang. Generalized Concavity, volume 36 of Mathematical Concepts and Methods in Science and Engineering. Plenum Press, New York, 1988.
[3] Dimitri P. B. Constrained Optimization and Lagrange Multiplier Methods. Athena Scientific, Belmont, 1996.
[4] E. B. Bajalinov. Linear-Fractional Programming: Theory, Methods, Applications and Software. Kluwer Academic Publishers, Dordrecht, 2003.
[5] A. I. Barros. Discrete and Fractional Programming Techniques for Location Models, volume 3 of Combinatorial Optimization. Kluwer Academic Publishers, Dordrecht, 1998.
[6] A. I. Barros, J. B. G. Frenk, and J. Gromicho. Fractional Location Problems. Location Science, 5:47–58, 1997.
[7] A. I. Barros, J. B. G. Frenk, S. Schaible, and S. Zhang. A New Algorithm for Generalized Fractional Programs. Mathematical Programming, 72A(2):147–175, 1996.
[8] A. I. Barros, J. B. G. Frenk, S. Schaible, and S. Zhang. Using Duality to Solve Generalized Fractional Programming Problems. Journal of Global Optimization. An International Journal Dealing with Theoretical and Computational Aspects of Seeking Global Optima and Their Applications in Science, Management and Engineering, 8(2):139–170, 1996.
[9] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. Nonlinear Programming. Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, third edition, 2006. Theory and algorithms.
[10] C. R. Bector, S. Chandra, and M. K. Bector. Generalized Fractional Programming Duality: A Parametric Approach. Journal of Optimization Theory and Applications, 60(2):243–260, 1989.
[11] A. Ben-Tal and M. Teboulle. A Smoothing Technique for Nondifferentiable Optimization Problems. In J. M. Morel, F. Takens, and B. Teissier, editors, Optimization (Varetz, 1988), volume 1405 of Lecture Notes in Mathematics, pages 1–11, Berlin, 1989. Springer.
[12] H. P. Benson. Fractional Programming with Convex Quadratic Forms and Functions. European Journal of Operational Research, 173(2):351–369, 2006.
[13] H. P. Benson. Maximizing the Ratio of Two Convex Functions over a Convex Set. Naval Research Logistics. A Journal Dedicated to Advances in Operations and Logistics Research, 53(4):309–317, 2006.
[14] J. C. Bernard and J. A. Ferland. Convergence of Interval-Type Algorithms for Generalized Fractional Programming. Mathematical Programming, 43A(3):349–363, 1989.
[15] D. P. Bertsekas. Approximation Procedures Based on the Method of Multipliers. Journal of Optimization Theory and Applications, 23(4):487–510, 1977.
[16] J. Borde and J. P. Crouzeix. Convergence of a Dinkelbach-type Algorithm in Generalized Fractional Programming. Zeitschrift f¨ur Operations Research. Serie A. Serie B, 31(1):A31–A54, 1987.
[17] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, 2004.
[18] R. Cambini, L. Carosi, and S. Schaible. Duality in Fractional Programming Problems with Set Constraints. In Generalized Convexity, Generalized Monotonicity and Applications, volume 77 of Nonconvex Optim. Appl., pages 147–159. Springer, New York, 2005.
[19] S. Chandra, B. D. Craven, and B. Mond. Generalized Fractional Programming Duality: A Ratio Game Approach. Australian Mathematical Society. Journal. Series B. Applied Mathematics, 28(2):170–180, 1986.
[20] S. Chandra and V. Kumar. Duality in Fractional Minimax Programming. Australian Mathematical Society. Journal. Series A. Pure Mathematics and Statistics, 58(3):376–386, 1995.
[21] A. Charnes and W. W. Cooper. Programming with Linear Fractional Functionals. Naval Research Logistics Quarterly, 9:181–186, 1962.
[22] A. Charnes and W. W. Cooper. Goal Programming and Multiple Objective Optimizations. I. European Journal of Operational Research, 1(1):39–54, 1977.
[23] H. J. Chen, S. Schaible, and R. L. Sheu. Generic Algorithm for Generalized Fractional Programming. Journal of Optimization Theory and Applications, 141(1):93–105, 2009.
[24] C. S. Colantoni, R. P. Manes, and A. Whinston. Programming, Profit Rates, and Pricing Decisions. The Accounting Review, 44:467–481, 1969.
[25] B. D. Craven. Fractional Programming, volume 4 of Sigma Series in Applied Mathematics. Heldermann Verlag, Berlin, 1988.
[26] B. D. Craven. Fractional Programming—a Survey. Opsearch. The Journal of the Operational Research Society of India, 25(3):165–176, 1988.
[27] J. P. Crouzeix and J. A. Ferland. Algorithms for Generalized Fractional Programming. Mathematical Programming, 52(2, Ser. B):191–207, 1991.
[28] J. P. Crouzeix, J. A. Ferland, and S. Schaible. An Algorithm for Generalized Fractional Programs. Journal of Optimization Theory and Applications, 47(1):35–49, 1985.
[29] J. P. Crouzeix, J. A. Ferland, and S. Schaible. A Note on an Algorithm for Generalized Fractional Programs. Journal of Optimization Theory and Applications, 50(1):183–187, 1986.
[30] V. F. Dem′yanov and V. N. Malozemov. Introduction to Minimax. Halsted Press [John Wiley & Sons], New York-Toronto, Ont., 1974. Translated from the Russian by D. Louvish.
[31] W. Dinkelbach. On Nonlinear Fractional Programming. Management Science. Journal of the Institute of Management Science. Application and Theory Series, 13:492–498, 1967.
[32] S. C. Fang, D. Y. Gao, R. L. Sheu, and W. Xing. Global Optimization for a Class of Fractional Programming Problems. Journal of Global Optimization. An International Journal Dealing with Theoretical and Computational Aspects of Seeking Global Optima and Their Applications in Science, Management and Engineering, 45(3):337–353, 2009.
[33] S. C. Fang, J. R. Rajasekera, and H. S. J. Tsao. Entropy Optimization and Mathematical Programming. International Series in Operations Research & Management Science, 8. Kluwer Academic Publishers, Boston, MA, 1997.
[34] J. A. Ferland and J. Y. Potvin. Generalized Fractional Programming: Algorithms and Numerical Experimentation. European Journal of Operational Research, 20(1):92–101, 1985.
[35] C. A. Floudas and P. M. Pardalos. Recent Advances in Global Optimization. Princeton, Princeton University Press, New Jersey, 1992.
[36] H. Frenk and S. Schaible. Fractional Programming. In C. A. Floudas and P. M. Pardalos, editors, Encyclopedia of Optimization. Vol. II, pages 162–172, Dordrecht, 2001. Kluwer Academic Publishers.
[37] J. B. G. Frenk and S. Schaible. Fractional Programming. In Nicolas Hadjisavvas, S´andor Koml´osi, and Siegfried Schaible, editors, Handbook of Generalized Convexity and Generalized Monotonicity, volume 76 of Nonconvex Optimization and its Applications, pages 335–386, New York, 2005. Springer-Verlag.
[38] T. Ibaraki. Parametric Approaches to Fractional Programs. Mathematical Programming, 26(3):345–362, 1983.
[39] R. Jagannathan and S. Schaible. Duality in Generalized Fractional Programming via Farkas’ Lemma. Journal of Optimization Theory and Applications, 41(3):417–424, 1983.
[40] P. K. Kanchan, A. S. B. Holland, and B. N. Sahney. Transportation Techniques in Linear-Plus-Fractional Programming. Cahiers du Centre d’ ´ Etudes de Recherche Op´erationnelle, 23(2):153–157, 1981.
[41] H. Konno and M. Inori. Bond Portfolio Optimization by Bilinear Fractional Programming. Journal of the Operations Research Society of Japan, 32:143–158, 1989.
[42] H. Konno and H.Watanabe. Bond Portfolio Optimization Problems and Their Application to Index Tracking: A Partial Optimization Approach. Journal of the Operations Research Society of Japan, 39:295–306, 1996.
[43] X. S. Li and S. C. Fang. On the Entropic Regularization Method for Solving Min-Max Problems with Applications. Mathematical Methods of Operations Research, 46(1):119–130, 1997.
[44] J. Y. Lin and R. L. Sheu. Modified Dinkelbach-type Algorithm for Generalized Fractional Programs with Infinitely Many Ratios. Journal of Optimization Theory and Applications, 126(2):323–343, 2005.
[45] D. G. Luenberger and Y. Ye. Linear and Nonlinear Programming. International Series in Operations Research & Management Science, 116. Springer, New York, third edition, 2008.
[46] J. Nocedal and S. J. Wright. Numerical Optimization. Springer Series in Operations Research. Springer-Verlag, New York, 1999.
[47] J. M. Ortega and W. C. Rheinboldt. Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York, 1970.
[48] N. T. H. Phuong and H. Tuy. A Unified Monotonic Approach to Generalized Linear Fractional Programming. Journal of Global Optimization. An International Journal Dealing with Theoretical and Computational Aspects of Seeking Global Optima and Their Applications in Science, Management and Engineering, 26(3):229–259, 2003.
[49] A. W. Roberts and D. E. Varberg. Convex Functions. Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York- London, 1973. Pure and Applied Mathematics, Vol. 57.
[50] R. T. Rockafellar. Convex Analysis. Princeton Mathematical Series, No. 28. Princeton University Press, Princeton, N.J., 1970.
[51] Y. Sawasaki, Y. Kimura, and K. Tanaka. A Two-person Zero-sum Game with Fractional Loss Function. Journal of the Operations Research Society of Japan, 43(1):209–218, 2000. New trends in mathematical programming (Kyoto, 1998).
[52] S. Schaible. Fractional Programming. I. Duality. Management Science. Journal of the Institute of Management Science. Application and Theory Series, 22(8):858–867, 1975/76.
[53] S. Schaible. Fractional Programming II. On Dinkelbach’s Algorithm. Management Science. Journal of the Institute of Management Science. Application and Theory Series, 22(8):868–873, 1975/76.
[54] S. Schaible. Bibliography in Fractional Programming. Zeitschrift f¨ur Operations Research. Serie A. Serie B, 26(7):A211–A241, 1982.
[55] S. Schaible. Fractional Programming. Zeitschrift f¨ur Operations Research. Serie A. Serie B, 27(1):39–54, 1983.
[56] S. Schaible. Multi-ratio Fractional Programming—A Survey. In Optimization, Parallel Processing and Applications (Oberwolfach, 1987 and Karlsruhe, 1987), volume 304 of Lecture Notes in Econom. and Math. Systems, pages 57–66. Springer, Berlin, 1988.
[57] S. Schaible. Fractional Programming. In R. Horst and P. M. Pardalos, editors, Handbook of Global Optimization, pages 495–608, Dordrecht, 1995. Kluwer Academic Publishers.
[58] S. Schaible and T. Ibaraki. Fractional Programming. European Journal of Operational Research, 12(4):325–338, 1983.
[59] S. Schaible and W. T. Ziemba, editors. Generalized Concavity in Optimization and Economics, New York, 1981. Academic Press Inc. [Harcourt Brace Jovanovich Publishers].
[60] C. H. Scott and T. R. Jefferson. Conjugate Duality in Generalized Fractional Programming. Journal of Optimization Theory and Applications, 60(3):475–483, 1989.
[61] R. L. Sheu and J. Y. Lin. Solving Continuous Min-Max Problems by an Iterative Entropic Regularization Method. Journal of Optimization Theory and Applications, 121(3):597–612, 2004.
[62] M. Sion. On General Minimax Theorems. Pacific Journal of Mathematics, 8:171–176, 1958.
[63] M. Sniedovich. Fractional Programming Revisited. European Journal of Operational Research, 33(3):334–341, 1988.
[64] I. M. Stancu-Minasian. Applications of the Fractional Programming. Economic Computation and Economic Cybernetics Studies and Research, 1:69–86, 1980.
[65] I. M. Stancu-Minasian. Fractional Programming, volume 409 of Mathematics and its Applications. Kluwer Academic Publishers Group, Dordrecht, 1997. Theory, methods and applications, Translated from the 1992 Romanian original by Victor Giurgiutiu and revised by the author.
[66] I. M. Stancu-Minasian. A Sixth Bibliography of Fractional Programming. Optimization. A Journal of Mathematical Programming and Operations Research, 55(4):405–428, 2006.
[67] J. von Neumann. A Model of General Economic Equilibrium. Review of Economic Studies, 13:1–9, 1945.