Abstract
In this paper we establish some approximation versions of the classical Dinkelbach algorithm for nonlinear fractional optimization problems in Banach spaces. We start by examining what occurs if at any step of the algorithm, the generated point desired to be a minimizer can only be determined with a given error. Next we assume that the step error tends to zero as the algorithm advances. The last version of the algorithm we present is making use of Ekeland’s variational principle for generating the sequence of minimizer-like points. In the final part of the article we deliver some results in order to achieve a Palais-Smale type compactness condition that guarantees the convergence of our Dinkelbach-Ekeland algorithm.
Authors
Alexandru Orzan
Faculty of Mathematics and Computer Science, Babes-Bolyai University, Cluj-Napoca, Romania;
Department of Mathematics, Technical University of Cluj-Napoca, Cluj-Napoca, Romania
Radu Precup
Faculty of Mathematics and Computer Science and Institute of Advanced Studies in Science and Technology, Babes–Bolyai University, Cluj-Napoca, Romania;
Tiberiu Popoviciu Institute ofNumerical Analysis, Romanian Academy, Cluj-Napoca, Romania
Keywords
Dinkelbach algorithm; Ekeland principle; fractional optimization; Palais-Smale condition.
Paper coordinates
A. Orzan, R. Precup, Dinkelbach type approximation algorithms for nonlinear fractional optimization problems, Numerical Functional Analysis and Optimization, 44 (2023) no. 9, pp. 954–969. https://doi.org/10.1080/01630563.2023.2217893
About this paper
Journal
Numerical Functional Analysis and Optimization
Publisher Name
Taylor and Francis Ltd.
Print ISSN
Online ISSN
google scholar link
[1] Avriel, M., Diewert, W. E., Schaible, S., Zang, I. (1988). Generalized Concavity. New York, NY: Plenum Press.
[2] Cambini, A., Martein, L. (2009). Generalized Convexity and Optimization: Theory and Applications. Berlin: Springer.
[3] Elbenani, B., Ferland, J.A. (2012). Cell formation problem solved exactly with the Dinkelbach algorithm. CIRRELT-2012-07, University of Montreal, Montreal. Quebec., p.1–14.
[4] Stancu-Minasian, I. M. (1997). Fractional Programming. Dordrecht: Kluwer.
[5] Precup, R. (2013). Linear and Semilinear Partial Differential Equations. Berlin: De Gruyter.
[6] Crouzeix, J. P., Ferland, J. A. (1991). Algorithms for generalized fractional programming. Math. Program. 52(1-3):191–207. DOI: 10.1007/BF01582887.
[7] Frenk, J. B. G., Schaibe, S. (2005). Fractional programming. In: Hadjisavvas, N., Komlosi, S., Schaible, S.S., eds. Handbook of Generalized Convexity and Generalized Monotonicity, Vol. 76, Berlin: Springer, p. 335–386.
[8] Schaible, S. (1981). A survey of fractional programming. In: Schaible, S., Ziemba, W.T., eds. Generalized Concavity in Optimization and Economics. New York: Academic Press, pp. 417–440.
[9] Schaible, S. (1982). Bibliography in fractional programming. Math. Methods Oper. Res. 26(1):211–241. DOI: 10.1007/BF01917115.
[10] Bot¸, R. I., Csetnek, E. R. (2017). Proximal-gradient algorithms for fractional programming. Optimization. 66(8):1383–1396. DOI: 10.1080/02331934.2017.1294592.
[11] Bot¸, R. I., Dao, M. N., Li, G. (2022). Extrapolated proximal subgradient algorithms for nonconvex and nonsmooth fractional programs. Mathematics of OR. 47(3):2415–2443. DOI: 10.1287/moor.2021.1214.
[12] Crouzeix, J. P., Ferland, J. A., Nguyen, V. H. (2008). Revisiting Dinkelbach-type algorithms for generalized fractional programs. Operational Res. Soc. India. 45:96-110.
[13] Rodenas, R. G., Lopez, M. L., Verastegui, D. (1999). Extensions of Dinkelbach ’s algorithm for solving non-linear fractional programming problems. Top. 7(1):33–70. DOI: 10.1007/BF02564711.
[14] Schaible, S., Shi, J. (2003). Fractional programming: The sum-of-ratios case. Optim. Methods Softw. 18(2):219–229. DOI: 10.1080/1055678031000105242.
[15] Shi, J. (2001). A Combined algorithm for fractional programming. Ann. Oper. Res. 103(1/4):135–147. DOI: 10.1023/A:1012998904482.
[16] Tammer, K., Tammer, C., Ohlendorf, E. (2005). Multicriterial Fractional Optimization. Humboldt-Universitat zu Berlin, Mathematisch-Naturwissenschaftliche Fakultat II, Institut fur Mathematik, Berlin, preprint.
[17] Dinkelbach, W. (1967). On nonlinear fractional programming. Manage. Sci. 13(7): 492–498. DOI: 10.1287/mnsc.13.7.492.
[18] Ekeland, I. (1974). On the variational principle. J. Math. Anal. Appl. 47(2):324–353. DOI: 10.1016/0022-247X(74)90025-0.
[19] Frigon, M. (2011). On some generalizations of Ekeland’s principle and inward contractions in gauge spaces. J. Fixed Point Theory Appl. 10(2):279–298. DOI:10.1007/s11784-011-0068-6.
[20] Precup, R. (2014). Nash-type equilibria and periodic solutions to nonvariational systems. Adv. Nonlinear Anal. 3(4):197–207. DOI: 10.1515/anona-2014-0006.