Top

Published in:

2020 | OriginalPaper | Chapter

On Solving the Quadratic Sum-of-Ratios Problems

Authors : Tatiana V. Gruzdeva, Alexander S. Strekalovsky

Published in: Mathematical Optimization Theory and Operations Research

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper addresses the numerical solution of fractional programs with quadratic functions in the ratios. Instead of considering a sum-of-ratios problem directly, we developed an efficient global search algorithm, which is based on two approaches to the problem. The first one adopts a reduction of the fractional minimization problem to the solution of an equation with an optimal value of a parametric d.c. minimization problem. The second approach reduces the original problem to the optimization problem with nonconvex (d.c.) constraints. Hence, the fractional programs can be solved by applying the Global Search Theory of d.c. optimization.

The global search algorithm developed for sum-of-ratios problems was tested on the examples with quadratic functions in the numerators and denominators of the ratios. The numerical experiments demonstrated that the algorithm performs well when solving rather complicated quadratic sum-of-ratios problems with up to 100 variables or 1000 terms in the sum.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter D.C. Constrained Optimization Approach for Solving Metal Recovery Processing Problem

next chapter Adaptive Descent Splitting Method for Decomposable Optimization Problems

Ashtiani, A.M., Ferreira, P.A.V.: A branch-and-cut algorithm for a class of sum-of-ratios problems. Appl. Math. Comput. 268, 596–608 (2015)MathSciNetMATH

Barkova, M.V.: On generating nonconvex optimization test problems. In: Khachay, M., Kochetov, Y., Pardalos, P. (eds.) MOTOR 2019. LNCS, vol. 11548, pp. 21–33. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-22629-9_2CrossRefMATH

Bugarin, F., Henrion, D., Lasserre, J.B.: Minimizing the sum of many rational functions. Math. Programm. Comput. 8(1), 83–111 (2015). https://doi.org/10.1007/s12532-015-0089-zMathSciNetCrossRefMATH

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

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

Freund, R.W., Jarre, F.: Solving the sum-of-ratios problem by an interior-point method. J. Glob. Optim. 19(1), 83–102 (2001). https://doi.org/10.1023/A:1008316327038MathSciNetCrossRefMATH

Frenk, J.B.G., Schaible, S.: Fractional programming. In: Hadjisavvas, S.S.N., Komlosi, S. (eds.) Handbook of Generalized Convexity and Generalized Monotonicity. Series Nonconvex Optimization and Its Applications, vol. 76, pp. 335–386. Springer, Heidelberg (2002). https://doi.org/10.1007/b101428CrossRef

Gruzdeva, T.V., Enkhbat, R., Tungalag, N.: Fractional programming approach to a cost minimization problem in electricity market. Yugoslav J. Oper. Res. 29(1), 43–50 (2019)MathSciNetCrossRef

Gruzdeva, T.V., Strekalovskiy, A.S.: On solving the sum-of-ratios problem. Appl. Math. Comput. 318, 260–269 (2018)MathSciNetMATH

10.

Gruzdeva, T., Strekalovsky, A.: An approach to fractional programming via D.C. constraints problem: local search. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 404–417. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44914-2_32CrossRef

11.

Gruzdeva, T., Strekalovsky, A.: A D.C. programming approach to fractional problems. In: Battiti, R., Kvasov, D.E., Sergeyev, Y.D. (eds.) LION 2017. LNCS, vol. 10556, pp. 331–337. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69404-7_27CrossRef

12.

Gruzdeva, T.V., Strekalovsky, A.S.: On a Solution of Fractional Programs via D.C. Optimization Theory. In: CEUR Workshop Proceedings, OPTIMA-2017, vol. 1987, pp. 246–252 (2017)

13.

Hiriart-Urruty, J.B.: Generalized differentiability, duality and optimization for problems dealing with difference of convex finctions. In: Ponstein, J. (ed.) Convexity and Duality in Optimization. Lecture Notes in Economics and Mathematical Systems, vol. 256, pp. 37–69. Springer, Berlin (1985). https://doi.org/10.1007/978-3-642-45610-7_3CrossRef

14.

Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer, Heidelberg (1996). https://doi.org/10.1007/978-3-662-03199-5CrossRefMATH

15.

Horst, R., Pardalos, P.M. (eds.): Handbook of Global Optimization. Nonconvex Optimization and its Applications. Kluwer Academic Publishers, Dordrecht (1995)

16.

Kuno, T.: A branch-and-bound algorithm for maximizing the sum of several linear ratios. J. Glob. Optim. 22, 155–174 (2002). https://doi.org/10.1023/A:1013807129844MathSciNetCrossRefMATH

17.

Ma, B., Geng, L., Yin, J., Fan, L.: An effective algorithm for globally solving a class of linear fractional programming problem. J. Softw. 8(1), 118–125 (2013)CrossRef

18.

Schaible, S., Shi, J.: Fractional programming: the sum-of-ratios case. Optim. Meth. Softw. 18, 219–229 (2003)MathSciNetCrossRef

19.

Strekalovsky, A.S.: Elements of Nonconvex Optimization. Nauka, Novosibirsk (2003). (in Russian)

20.

Strekalovsky, A.S.: Global optimality conditions and exact penalization. Optim. Lett. 13(3), 597–615 (2019). https://doi.org/10.1007/s11590-017-1214-xMathSciNetCrossRefMATH

21.

Strekalovsky, A.S.: On local search in d.c. optimization problems. Appl. Math. Comput. 255, 73–83 (2015)MathSciNetMATH

22.

Strekalovsky, A.S.: On solving optimization problems with hidden nonconvex structures. In: Rassias, T.M., Floudas, C.A., Butenko, S. (eds.) Optimization in Science and Engineering, pp. 465–502. Springer, New York (2014). https://doi.org/10.1007/978-1-4939-0808-0_23CrossRefMATH

23.

Strekalovsky, A.S.: On the merit and penalty functions for the D.C. Optimization. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 452–466. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44914-2_36CrossRefMATH

24.

Strekalovsky, A.S.: Global optimality conditions in nonconvex optimization. J. Optim. Theory Appl. 173(3), 770–792 (2017). https://doi.org/10.1007/s10957-016-0998-7MathSciNetCrossRefMATH

25.

Strekalovsky, A.S.: Minimizing sequences in problems with D.C. constraints. Comput. Math. Math. Phys. 45(3), 418–429 (2005)MathSciNet

26.

Strekalovsky, A.S., Gruzdeva, T.V.: Local Search in Problems with Nonconvex Constraints. Comput. Math. Math. Phys. 47, 381–396 (2007)MathSciNetCrossRef

27.

Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-Convex Constraints. Sequential and Parallel Algorithms. Springer, New York (2000)CrossRef

28.

Tuy, H.: Parametric decomposition. Convex Analysis and Global Optimization. SOIA, vol. 110, pp. 283–336. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-31484-6_9CrossRefMATH

29.

Vicente, L.N., Calamai, P.H., Judice, J.J.: Generation of disjointly constrained bilinear programming test problems. Comput. Optim. Appl. 1(3), 299–306 (1992). https://doi.org/10.1007/BF00249639MathSciNetCrossRefMATH

Title: On Solving the Quadratic Sum-of-Ratios Problems
Authors: Tatiana V. Gruzdeva
Alexander S. Strekalovsky
Publisher: Springer International Publishing
Book: Mathematical Optimization Theory and Operations Research
Print ISBN: 978-3-030-49987-7

Electronic ISBN: 978-3-030-49988-4

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-49988-4_8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner