On the Minimization Problem of the Sum of Ratios

Authors

  • Davaajargal Jargalsaikhan Institute of Mathematics and Digital Technology, Mongolian Academy of Sciences, Ulaanbaatar 13330, Mongolia https://orcid.org/0000-0001-7585-2943
  • Bayarjargal Darkhijav Department of Applied Mathematics, National University of Mongolia, Ulaanbaatar 14200, Mongolia

DOI:

https://doi.org/10.5564/jimdt.v4i1.2656

Keywords:

Dinkelbach-type algorithm, gradient descent method

Abstract

We consider the problem of minimizing a sums of ratios that belong to a class of global optimization problems. Since the problem is nonconvex, the application of local search algorithms cannot always guarantee to find a global solution. It has been shown that problem can be solved by DC programming methods and algorithms. Dinkelbach-type algorithms are more efficient techniques because fractional problems reduce to a scalarized optimization problem. For solving the problem, we apply a generalized Dinkelbach algorithm requires finding the roots of a nonlinear equation. The numerical experiments were conducted on Python Jupyter Notebook for a box constrained set. The problem also has been solved by a gradient descent method and compared with the Dinkelbach algorithm. Numerical results are provided.

Бутархай Програмчлалын Нийлбэр Хэлбэрийн Бодлогыг Минимумчлах нь

Хураангуй: Энэхүү судалгаандаа бид глобал оптимизацийн ангилалд багтах бутархай программчлалын минимумчлах бодлогыг авч үзсэн болно. Бодлого нь ерөнхий тохиол-долд гүдгэр биш тул локал хайлтын аргаар бодоход үргэлж глобал шийд олдохгүй. Энэ төрлийн бодлогыг DC програмчлалын аргаар шийдэж болохыг харуулсан. Динкельбах алгоритм нь бутархай программчлалын бодлогыг энгийн оптимизацийн бодлогод шилжүүлдэг тул илүү үр дүнтэй арга юм. Иймд энэ бодлогыг бодоход Динкельбах алгоритм ашиглан олон хувьсагчтай шугаман бус тэгшитгэлийн шийдийг олох арга руу шилжүүлэх боломжтой байдаг. Тооцооллыг Python Jupyter Notebook дээр 100 хүртэлх хэмжээ-сийн хувьд хийсэн ба үүний зэрэгцээ градиент бууралтын арга дээр үр дүнгийн туршилтхийж, Динкельбах алгоритмтай харьцуулсан болно.

Түлхүүр үгс: Динкелбах алгоритм, градиент бууралтын арга

Abstract
110
PDF 145

References

T. V. Gruzdeva, and A. S. Strekalovsky, “On solving the sum-of-ratios problem,” Applied Mathematics and Computation, Vol. 318, pp. 260-269, 2018, doi: https://doi.org/10.1016/j.amc.2017.07.074.

W. Dinkelbach, “On nonlinear fractional programming,” Management Science, Vol. 13, pp. 492–498, 1967, doi: https://doi.org/10.1287/mnsc.13.7.492.

S. Schaible, and J. Shi, “Fractional Programming:The sum-of ratio case,” Optimization Methods and Software, Vol.18, No. 2, pp. 219–229, 2003, doi: https://doi.org/10.1080/1055678031000105242.

R. W. Freund, and F. Jarre, “Solving the Sum-of-Ratio Problem by an Interior-Point Method,” Journal of Global Optimization, Vol. 19, pp. 83-102, 2001, doi: https://doi.org/10.1023/A:1008316327038.

A. Cambini, L. Martein, and S. Schaible “On maximizing a sum of ratios,” Journal of Information and Optimization Sciences, Vol. 10, pp. 65–79, 1989, doi: https://doi.org/10.1080/02522667.1989.10698952.

D. Z. Chen, O. Daescu, Y. Dai, N. Katoh, X. Wu and J. Xu, “Efficient algorithms and implementations for optimizing the sum of linear fractional functions, with applications,” Technical Report, Department of Computer Science, University of Notre Dame, Notre Dame, IN, 1998.

J. E. Falk, and S. W. Palocsay, “Optimizing the sum of linear fractional functions, in: C.A. Floudas and P.M. Pardalos (eds.),” Recent Advances in Global Optimization, Princeton University Press, Princeton, NJ, pp. 221–258, 1992, doi: https://doi.org/10.1515/9781400862528.221.

H. Konno, and T. Kuno, “Generalized linear multiplicative and fractional programming,”Annals of Operations Research, Vol. 25, pp. 147–161, 1990, doi: https://doi.org/10.1007/BF02283691.

H. Konno, and H. Yamashita, “Minimization of the sum and the product of several linear fractional functions over a polytope,” Manuscript. Department of Industrial Engineering and Management, Tokyo Institute of Technology, Tokyo, Japan, 1998.

K. Ritter, “A parametric method for solving certain nonconcave maximization problems,” J.Computer and System Sciences, Vol. 1, pp. 44–54, 1967, doi: https://doi.org/10.1021/ed044p54.

S. Schaible, “Fractional programming with sums of ratios,” Working Paper Series, Graduate School of Management, University of California, Riverside, CA, no. 96-04, 1996.

A. E. Mouatasim, “ Fast gradient descent algorithm for image classification with neural networks,” Signal, Image and Video Processing, Vol. 14, pp. 1565–1572, 2020, doi: https://doi.org/10.1007/s11760-020-01696-2.

N. Cui, “Applying Gradient Descent in Convolutional Neural Networks,” Journal of Physics: Conference Series, Vol. 1004: 012027, 2018, doi: https://doi.org/10.1088/1742-6596/1004/1/012027.

D. Kraft, “A software package for sequential quadratic programming,” DFVLR-FB 88-28, 1988.

J. Nocedal, and S. J. Wright, “Numerical Optimizationg,” Springer, ISBN: 978-0-387-30303-1, 2006.

D. P. Bertsekas, “Nonlinear Programming,” Athena Scientific Press, Second edition, 1999.

R. Enkhbat, D. Tsedenbayar, and E. Enkhtsolmon, “Extremal Properties of the Cesaro Operator,” Mongolian Mathematical Journal, Vol. 23, no. 1, pp. 7-15, 2021.

Downloads

Published

2022-12-26

How to Cite

Jargalsaikhan, D., & Darkhijav, B. (2022). On the Minimization Problem of the Sum of Ratios. Journal of Institute of Mathematics and Digital Technology, 4(1), 9–15. https://doi.org/10.5564/jimdt.v4i1.2656

Issue

Section

Articles