×

Global optimization of fractional programs. (English) Zbl 0748.90068

Dinkelbach’s classical parametric algorithm in fractional programming is modified. A sequence of lower and upper bounds of the optimal value of the ratio is constructed and shown to be superlinearly convergent to the optimal value. Additional results are obtained for linear and quadratic fractional programs.

MSC:

90C32 Fractional programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Avriel, M., W. E.Diewert, S.Schaible, and I.Zang (1988), Generalized Concavity, New York: Plenum Press. · Zbl 0679.90029
[2] Dinkelbach, W. (1967), On Nonlinear Fractional Programming, Management Science 13(7): 492-498. · Zbl 0152.18402 · doi:10.1287/mnsc.13.7.492
[3] Grunspan, M. (1971), Fractional Programming: A Survey, Technical Report 50, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL.
[4] Ibaraki, T. (1983), Parametric Approaches to Fractional Programs, Mathematical Programming 26: 345-362. · Zbl 0506.90078 · doi:10.1007/BF02591871
[5] Isbell, J. R. and W. H.Marlow (1956), Attrition Games, Naval Research Logistics Quarterly 3: 71-93. · Zbl 0122.15405 · doi:10.1002/nav.3800030108
[6] Pardalos, P. M. (1986), An Algorithm for a Class of Nonlinear Fractional Problems Using Ranking of the Vertices, BIT 26: 392-395. · Zbl 0683.65048 · doi:10.1007/BF01933719
[7] Phillips, A. T. and J. B.Rosen (1990a), Guaranteed ?-Approximate Solution for Indefinite Quadratic Global Minimization, Naval Research Logistics 37: 499-514. · Zbl 0708.90063 · doi:10.1002/1520-6750(199008)37:4<499::AID-NAV3220370405>3.0.CO;2-9
[8] Phillips, A. T. and J. B.Rosen (1990b), A Parallel Algorithm for Partially Separable Non-convex Global Minimization, Annals of Operations Research 25: 101-118. · Zbl 0723.90063 · doi:10.1007/BF02283689
[9] Schaible, S. (1973), Fractional Programming: Transformations, Duality, and Algorithmic Aspects, Technical Report 73-9, Department of Operations Research, Stanford University, Stanford, CA. · Zbl 0307.26010
[10] Schaible, S. (1976a), Fractional Programming I, Duality, Management Science 22(8): 858-867. · Zbl 0338.90050 · doi:10.1287/mnsc.22.8.858
[11] Schaible, S. (1976b), Fractional Programming II, On Dinkelbach’s Algorithm, Management Science 22(8); 868-873. · Zbl 0346.90052 · doi:10.1287/mnsc.22.8.868
[12] Schaible, S. (1981), Fractional Programming: Applications and Algorithms, European Journal of Operational Research 7: 111-120. · Zbl 0452.90079 · doi:10.1016/0377-2217(81)90272-1
[13] Schaible, S. and T.Ibaraki (1983), Fractional Programming, European Journal of Operational Research 12: 325-338. · Zbl 0529.90088 · doi:10.1016/0377-2217(83)90153-4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.