Abstract
The global optimization of the sum of linear fractional functions has attracted the interest of researchers and practitioners for a number of years. Since these types of optimization problems are nonconvex, various specialized algorithms have been proposed for globally solving these problems. However, these algorithms may be difficult to implement and are usually relatively inaccessible. In this article, we show that, by using suitable transformations, a number of potential and known methods for globally solving these problems become available. These methods are often more accessible and use more standard tools than the customized algorithms proposed to date. They include, for example, parametric convex programming and concave minimization methods.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
SCHAIBLE, S., A Note on the Sum of a Linear and Linear-Fractional Function, Naval Research Logistics Quarterly, Vol.24, 691–693, 1977.
ALMOGY, Y., and LEVIN, O., Parametric Analysis of a Multistage Stochastic Shipping Problem, Operational Research 69, Edited by J. Lawrence, Tavistock Publications, London, England, 1970.
FALK, J. E., and PALOCSAY, S. W., Optimizing the Sum of Linear Fractional Functions, Recent Advances in Global Optimization, Edited by C. A. Floudas, and P. M. Pardalos, Princeton University Press, Princeton, New Jersey, 1992.
COLANTONI, C. S., MANES, R. P., and WHINSTON, A., Programming, Profit Rates, and Pricing Decisions, Accounting Review, Vol.44, 467–481, 1969.
KONNO, H., and INORI, M., Bond Portfolio Optimization by Bilinear Fractional Programming, Journal of the Operations Research Society of Japan, Vol.32, 143–158, 1989.
KONNO, H., and WATANABE, H., Bond Portfolio Optimization Problems and Their Applications to Index Tracking: A Partial Optimization Approach, Journal of the Operations Research Society of Japan, Vol.39, 295–306, 1996.
CAMBINI, A., MARTEIN, L., and SCHAIBLE, S., On Maximizing a Sum of Ratios, Journal of Information and Optimization Sciences, Vol.10, 65–79, 1989.
KONNO, H., YAJIMA, Y., and MATSUI, T., Parametric Simplex Algorithms for Solving a Special Class of Nonconvex Minimization Problems, Journal of Global Optimization, Vol.1, 65–81, 1991.
FALK, J. E., and PALOCSAY, S. W., Image Space Analysis of Generalized Fractional Programs, Journal of Global Optimization, Vol.4, 63–88, 1994.
KONNO, H., KUNO, T., and YAJIMA, Y., Global Minimization of a Generalized Convex Multiplicative Function, Journal of Global Optimization, Vol.4, 47–62, 1994.
BENSON, H. P., Concave Minimization: Theory, Applications, and Algorithms, Handbook of Global Optimization, Edited by R. Horst and P. M. Pardalos, Kluwer Academic Publishers, Dordrecht, Netherlands, 1995.
BENSON, H. P., Deterministic Algorithms for Constrained Concave Minimization: A Unified Critical Survey, Naval Research Logistics, Vol.43, 765–795, 1996.
QUESADA, I., and GROSSMANN, I., A Global Optimization Algorithm for Linear Fractional and Bilinear Programs, Journal of Global Optimization, Vol.6, 39–76, 1995.
KONNO, H., and YAMASHITA, H., Minimizing Sums and Products of Linear Fractional Functions over a Polytope, Naval Research Logistics, Vol.46, 583–596, 1999.
KONNO, H., and ABE, N., Minimization of the Sum of Three Linear Fractional Functions, Journal of Global Optimization, Vol.15, 419–432, 1999.
KONNO, H., and FUKAISHI, K., A Branch-and-Bound Algorithm for Solving Low-Rank Linear Multiplicative and Fractional Programming Problems, Journal of Global Optimization, Vol.18, 283–299, 2000.
ANDROULAKIS, I. P., MARANAS, C. D., and FLOUDAS, C. A., αBB: A Global Optimization Method for General Constrained Nonconvex Problems, Journal of Global Optimization, Vol.7, 337–363, 1995.
KUNO, T., A Branch-and-Bound Algorithm for Maximizing the Sum of Several Linear Ratios, Journal of Global Optimization, Vol.22, 155–174, 2002.
CHEN, D. Z., DAESCU, O., DAI, Y., KATOH, N., WU, X., and XU, J., Optimizing the Sum of Linear Fractional Functions and Applications, Proceedings of the 11th ACM/SIAM Symposium on Discrete Algorithms, 2000.
SCHAIBLE, S., Fractional Programming with Sums of Ratios, Scalar and Vector Optimization in Economic and Financial Problems, Proceedings of the Workshop in Milan, Italy, 1995; Edited by E. Castagnoli, and G. Giorgi, Elioprint, Milano, Italy, 1996.
SCHAIBLE, S., Fractional Programming, Handbook of Global Optimization, Edited by R. Horst and P. M. Pardalos, Kluwer Academic Publishers, Dordrecht, Netherlands, 1995.
BENSON, H. P., Generating Sum-of-Ratios Test Problems in Global Optimization, Journal of Optimization Theory and Applications, Vol.119, 615–621, 2003.
CHARNES, A., and COOPER, W. W., Programming with Linear Fractional Functionals, Naval Research Logistics Quarterly, Vol.19, 181–186, 1962.
HORST, R., and THOAI, N. V., Decomposition Approach for the Global Minimization of Biconcave Functions over Polytopes, Journal of Optimization Theory and Applications, Vol.88, 561–583, 1996.
MANGASARIAN, O. L., Nonlinear Programming, McGraw-Hill, New York, NY, 1969.
HORST, R., and PARDALOS, P. M., Editors, Handbook of Global Optimization, Kluwer Academic Publishers, Dordrecht, Netherlands, 1995.
ROCKAFELLAR, R. T., Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.
HORST, R., and TUY, H., Global Optimization: Deterministic Approaches, 2nd Edition, Springer Verlag, Berlin, Germany, 1993.
HORST, R., An Algorithm for Nonconvex Programming Problems, Mathematical Programming, Vol.10, 312–321, 1976.
FLOUDAS, C. A., and VISWESWARAN, V., Primal-Relaxed Dual Global Optimization Approach, Journal of Optimization Theory and Applications, Vol.78, 187–225, 1993.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Benson, H.P. On the Global Optimization of Sums of Linear Fractional Functions over a Convex Set. Journal of Optimization Theory and Applications 121, 19–39 (2004). https://doi.org/10.1023/B:JOTA.0000026129.07165.5a
Issue Date:
DOI: https://doi.org/10.1023/B:JOTA.0000026129.07165.5a