On the Minimization Problem of the Sum of Ratios
DOI:
https://doi.org/10.5564/jimdt.v4i1.2656Keywords:
Dinkelbach-type algorithm, gradient descent methodAbstract
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 хүртэлх хэмжээ-сийн хувьд хийсэн ба үүний зэрэгцээ градиент бууралтын арга дээр үр дүнгийн туршилтхийж, Динкельбах алгоритмтай харьцуулсан болно.
Түлхүүр үгс: Динкелбах алгоритм, градиент бууралтын арга
115
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
How to Cite
Issue
Section
License
Copyright (c) 2022 Davaajargal Jargalsaikhan, Bayarjargal Darkhijav
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
The authors grant the Journal of Institute of Mathemathics and Digital Technology a license to publish the article and identify itself as the original publisher.
Articles in the Journal of Institute of Mathemathics and Digital Technology are Open Access articles published under a Creative Commons Attribution-NonCommercial 4.0 International License - CC BY NC.
This license permits NonComericial use, distribution and reproduction in any medium, provided the original work is properly cited.
