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.
Similar content being viewed by others
References
Charnes, A., Cooper, W.W.: Programming with linear fractional functions. Nav. Res. Logist. Q. 9, 181–186 (1962)
Schaible, S.: Fractional programming II, on Dinkelbach’s algorithm. Manag. Sci. 22, 868–873 (1976)
Dinkelbach, W.: On nonlinear fractional programming. Manag. Sci. 13, 492–498 (1967)
Pardalos, P.M., Phillips, A.T.: Global optimization of fractional programs. J. Glob. Optim. 1, 173–182 (1991)
Schaible, S.: Fractional programming. In: Horst, R., Pardalos, P. (eds.) Handbook of Global Optimization. Kluwer Academic, Dordrecht (1995)
Lo, A., Mackinlay, C.: Maximizing predictability in the stock and bond markets. Macroecon. Dyn. 1, 102–134 (1997)
Gotoh, J., Konno, H.: Maximization of the ratio of two convex quadratic functions over a polytope. Comput. Optim. Appl. 20, 43–60 (2001)
Konno, H., Thach, P.T., Tuy, H.: Optimization on Low Rank Nonconvex Structures. Kluwer Academic, Dordrecht (1997)
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)
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)
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)
Wolsey, L.A.: Integer Programming. Wiley, New York (1998)
Bertsekas, D.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1995)
Luenberger, D.G.: Nonlinear Programming, 2nd edn. Kluwer Academic, Dordrecht (2003)
Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)
Ibaraki, T.: Parametric approaches to fractional programs. Math. Program. 26, 345–362 (1983)
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)
Gantmacher, F.R.: The Theory of Matrices. Chelsea, New York (1959)
Author information
Authors and Affiliations
Corresponding author
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
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
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-007-9188-y