Skip to main content
Springer Nature Link
Log in

An Efficient Algorithm for Solving Convex–Convex Quadratic Fractional Programs

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

Abstract

This paper is concerned with an efficient algorithm for solving a convex-convex type quadratic fractional program whose objective function is defined as the ratio of two convex quadratic functions and whose constraints are linear. This is a typical nonconcave maximization problem with multiple local maxima.

The algorithm to be proposed here is a combination of (i) the classical Dinkelbach approach, (ii) the integer programming approach for solving nonconvex quadratic programming problems and (iii) the standard nonlinear programming algorithm.

It will be shown that an exact algorithm which is a combination of (i) and (ii) above can solve problems much larger than those solved by an earlier algorithm based on a branch and bound algorithm. It addition, the combination of (i)–(iii) can solve much larger problems within a practical amount of time.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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. Charnes, A., Cooper, W.W.: Programming with linear fractional functions. Nav. Res. Logist. Q. 9, 181–186 (1962)

    Article  MATH  MathSciNet  Google Scholar 

  2. Schaible, S.: Fractional programming II, on Dinkelbach’s algorithm. Manag. Sci. 22, 868–873 (1976)

    MATH  MathSciNet  Google Scholar 

  3. Dinkelbach, W.: On nonlinear fractional programming. Manag. Sci. 13, 492–498 (1967)

    Article  MathSciNet  Google Scholar 

  4. Pardalos, P.M., Phillips, A.T.: Global optimization of fractional programs. J. Glob. Optim. 1, 173–182 (1991)

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

  6. Lo, A., Mackinlay, C.: Maximizing predictability in the stock and bond markets. Macroecon. Dyn. 1, 102–134 (1997)

    Article  MATH  Google Scholar 

  7. Gotoh, J., Konno, H.: Maximization of the ratio of two convex quadratic functions over a polytope. Comput. Optim. Appl. 20, 43–60 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  8. Konno, H., Thach, P.T., Tuy, H.: Optimization on Low Rank Nonconvex Structures. Kluwer Academic, Dordrecht (1997)

    MATH  Google Scholar 

  9. Phong, T.Q., An, L.T.H., Tao, P.D.: Decomposition branch and bound method for globally solving linearly constrained indefinite quadratic minimization problems. Oper. Res. Lett. 17, 215–220 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  10. Konno, H., Yamamoto, R.: Global optimization vs integer programming in portfolio optimization under nonconvex transaction cost. Report ISE03-07, Department of Industrial and System Engineering, Chuo University, Tokyo, Japan (2003)

  11. Konno, H., Yamamoto, R.: Integer programming approaches in mean-risk model. Report ISE03-08, Department of Industrial and System Engineering, Chuo University, Tokyo, Japan (2003)

  12. Wolsey, L.A.: Integer Programming. Wiley, New York (1998)

    MATH  Google Scholar 

  13. Bertsekas, D.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1995)

    MATH  Google Scholar 

  14. Luenberger, D.G.: Nonlinear Programming, 2nd edn. Kluwer Academic, Dordrecht (2003)

    MATH  Google Scholar 

  15. Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)

    MATH  Google Scholar 

  16. Ibaraki, T.: Parametric approaches to fractional programs. Math. Program. 26, 345–362 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  17. Sekitani, K., Shi, J.M., Yamamoto, Y.: General fractional programming: minmax convex-convex quadratic case. In: Proceedings of APORS’94, pp. 505–514. World Scientific, Singapore (1995)

    Google Scholar 

  18. Gantmacher, F.R.: The Theory of Matrices. Chelsea, New York (1959)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial and Systems Engineering, Chuo University, Tokyo, Japan

    R. Yamamoto & H. Konno

  2. MTB Investment Technology Institute Company, Tokyo, Japan

    R. Yamamoto

Authors
  1. R. Yamamoto
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. H. Konno
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to R. Yamamoto.

Additional information

Communicated by S. Schaible.

This research was supported in part by the Grant-in-Aid for Scientific Research of the Ministry of Education, Science, Culture and Sports of Japan B(2) 15310122 and 15656025. The authors acknowledge the generous support of the Hitachi Company and the Japan Credit Research Company.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Yamamoto, R., Konno, H. An Efficient Algorithm for Solving Convex–Convex Quadratic Fractional Programs. J Optim Theory Appl 133, 241–255 (2007). https://doi.org/10.1007/s10957-007-9188-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-007-9188-y

Keywords

Search

Navigation