Skip to main content
SpringerLink
Log in

Solving Sum of Ratios Fractional Programs via Concave Minimization

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

This article presents an algorithm for globally solving a sum of ratios fractional programming problem. To solve this problem, the algorithm globally solves an equivalent concave minimization problem via a branch-and-bound search. The main work of the algorithm involves solving a sequence of convex programming problems that differ only in their objective function coefficients. Therefore, to solve efficiently these convex programming problems, an optimal solution to one problem can potentially be used to good advantage as a starting solution to the next problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Almogy, Y., Levin, O.: Parametric analysis of a multistage stochastic shipping problem. In: Proceedings of the 5th IFORS Conference, pp. 359–370 (1964)

  2. Colantoni, C.S., Manes, R.P., Whinston, A.: Programming, profit rates, and pricing decisions. Account. Rev. 44, 467–481 (1969)

    Google Scholar 

  3. Konno, H., Inori, M.: Bond portfolio optimization by bilinear fractional programming. J. Oper. Res. Soc. Jpn. 32, 143–158 (1989)

    MATH  MathSciNet  Google Scholar 

  4. Konno, H., Watanabe, H.: Bond portfolio optimization problems and their application to index tracking: a partial optimization approach. J. Oper. Res. Soc. Jpn. 39, 295–306 (1996)

    MATH  MathSciNet  Google Scholar 

  5. Rao, M.R.: Cluster analysis and mathematical programming. J. Am. Stat. Assoc. 66, 622–626 (1971)

    Article  MATH  Google Scholar 

  6. Schaible, S.: Fractional programming. In: Horst, R., Pardalos, P.M. (eds.) Handbook of Global Optimization. Kluwer Academic, Dordrecht (1995)

    Google Scholar 

  7. Schaible, S.: Fractional programming with sums of ratios. In: Castagnoli, E., Giorgi, G. (eds.) Scalar and Vector Optimization in Economic and Financial Problems, Proceedings of the Workshop in Milan, 1995. Elioprint, Milan (1996)

    Google Scholar 

  8. Schaible, S.: A note on the sum of a linear and linear fractional function. Naval Res. Logist. Q. 24, 691–693 (1977)

    Article  MATH  Google Scholar 

  9. Cambini, A., Martein, L., Schaible, S.: On maximizing a sum of ratios. J. Inf. Optim. Sci. 10, 65–79 (1989)

    MATH  MathSciNet  Google Scholar 

  10. Konno, H., Yajima, Y., Matsui, T.: Parametric simplex algorithms for solving a special class of nonconvex minimization problems. J. Glob. Optim. 1, 65–81 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  11. Falk, J.E., Palocsay, S.W.: Image space analysis of generalized fractional programs. J. Glob. Optim. 4, 63–88 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  12. Konno, H., Fukaishi, K.: A branch-and-bound algorithm for solving low-rank linear multiplicative and fractional programming problems. J. Glob. Optim. 18, 283–299 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  13. Konno, H., Yamashita, H.: Minimizing sums and products of linear fractional functions over a polytope. Naval Res. Logist. 46, 583–596 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  14. Kuno, T.: A branch-and-bound algorithm for maximizing the sum of several linear ratios. J. Glob. Optim. 22, 155–174 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  15. Konno, H., Kuno, T., Yajima, Y.: Global minimization of a generalized convex multiplicative function. J. Glob. Optim. 4, 47–62 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  16. Dur, M., Horst, R., Thoai, N.V.: Solving sum-of-ratios fractional programs using efficient points. Optimization 49, 447–466 (2001)

    Article  MathSciNet  Google Scholar 

  17. Freund, R.W., Jarre, F.: Solving the sum-of-ratios problem by an interior-point method. J. Glob. Optim. 19, 83–102 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  18. Benson, H.P.: Global optimization of nonlinear sums of ratios. J. Math. Anal. Appl. 263, 301–315 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  19. Benson, H.P.: Using concave envelopes to globally solve the nonlinear sum of ratios problem. J. Glob. Optim. 22, 343–364 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  20. Benson, H.P.: On the global optimization of sums of linear fractional functions over a convex set. J. Optim. Theory Appl. 121, 19–39 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  21. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

    MATH  Google Scholar 

  22. Benson, H.P.: Concave minimization: theory, applications, and algorithms. In: Horst, R., Pardalos, P.M. (eds.) Handbook of Global Optimization. Kluwer Academic, Dordrecht (1995)

    Google Scholar 

  23. Benson, H.P.: Deterministic algorithms for constrained concave minimization: a unified critical survey. Naval Res. Logist. 43, 765–795 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  24. Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 2nd edn. Springer, Berlin (1993)

    Google Scholar 

  25. Kuhn, H.W., Tucker, A.W.: Nonlinear programming. In: Neyman, J. (ed.) Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability. University of California Press, Berkeley (1951)

    Google Scholar 

  26. Benson, H.P.: Solving sum of ratios fractional programs via concave minimization. Working Paper, University of Florida, Department of Decision and Information Sciences, March (2006)

Download references

Author information

Authors and Affiliations

  1. Warrington College of Business Administration, University of Florida, Gainesville, FL, USA

    H. P. Benson

Authors
  1. H. P. Benson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to H. P. Benson.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Benson, H.P. Solving Sum of Ratios Fractional Programs via Concave Minimization. J Optim Theory Appl 135, 1–17 (2007). https://doi.org/10.1007/s10957-007-9199-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-007-9199-8

Keywords

Search

Navigation