Abstract
The paper deals with fractional optimization problems where the objective function (ratio of two functions) is defined on a Cartesian product of two real normed spaces X and Y. Within this framework, we are interested to determine the so-called partial minimizers, i.e. points in \(X\times Y\) with the property that any of its variables minimizes the objective function, restricted to this variable, with respect to the other one. While any global minimizer is obviously a partial minimizer, the reverse implication holds true only under additional assumptions (e.g. separability properties of the involved functions). By exploiting the particularities of the objective function, we deliver a Dinkelbach type algorithm for computing partial minimizers of fractional optimization problems. Further assumptions on the involved spaces and functions, such as Lipschitz-type continuity, partial Fr\'{e}chet differentiability, and coercivity, enable us to establish the convergence of our algorithm to a partial minimizer.
Authors
Christian Günther
Alexandru Orzan
Faculty of Mathematics and Computer Science, Babeş-Bolyai University, Cluj-Napoca, Romania; Department of Mathematics, Technical University of Cluj-Napoca, Cluj-Napoca, Romania
Radu Precup
Babes-Bolyai University, Cluj-Napoca, Romania &
Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy
Keywords
Fractional optimization; Dinkelbach type algorithm; coercive function; partial minimizer
Paper coordinates
??
About this paper
Journal
Optimization
A Journal of Mathematical Programming and Operations Research
Publisher Name
Taylor and Francis
Print ISSN
Online ISSN
google scholar link
[1] Shen K, Yu W. Fractional programming for communication systems–part I: power control and beamforming. IEEE Trans Signal Process. 2018;66(10):2616–2630. doi: 10.1109/TSP.2018.2812733 [Crossref] [Web of Science ®], [Google Scholar]
[2] Shen K, Yu W. Fractional programming for communication systems–part II: uplink scheduling via matching. IEEE Trans Signal Process. 2018;66(10):2631–2644. doi: 10.1109/TSP.2018.2812748 [Crossref] [Web of Science ®], [Google Scholar]
[3] Elbenani B, Ferland JA. Cell formation problem solved exactly with the Dinkelbach algorithm. University of Montreal; 2012. (Report CIRRELT-2012-07). [Google Scholar]
[4] Frenk JBG, Schaible S. Fractional programming. In: Hadjisavvas N, Komlósi S, Schaible S, editors. Handbook of generalized convexity and generalized monotonicity. New York (NY): Springer; 2005. p. 335–386. [Crossref], [Google Scholar]
[5] Göpfert A, Riahi H, Tammer C, et al. Variational methods in partially ordered spaces. New York (NY): Springer; 2006. [Google Scholar]
[6] Schaible S. A survey of fractional programming. In: Schaible S, Ziemba WT, editors. Generalized concavity in optimization and economics. New York (NY): Academic Press; 1981. p. 417–440. [Google Scholar]
[7] Schaible S. Bibliography in fractional programming. Math Methods Oper Res. 1982;26(1):211–241. doi: 10.1007/BF01917115 [Crossref], [Google Scholar]
[8] Schaible S, Shi J. Fractional programming: the sum-of-ratios case. Optim Methods Softw. 2003;18(2):219–229. doi: 10.1080/1055678031000105242 [Taylor & Francis Online] [Web of Science ®], [Google Scholar]
[9] Precup R. Linear and semilinear partial differential equations. Berlin (BE): De Gruyter; 2013. [Google Scholar]
[10] Stancu-Minasian IM. Fractional programming: theory, methods and applications. Dordrecht (NL): Kluwer; 1997. [Crossref], [Google Scholar]
[11] Stancu-Minasian IM, Tigan S. Continuous time linear-fractional programming. the minimum-risk approach. RAIRO Oper Res. 2000;34(4):397–409. doi: 10.1051/ro:2000121 [Crossref] [Web of Science ®], [Google Scholar]
[12] Dinkelbach W. On nonlinear fractional programming. Manage Sci. 1967;13(7):492–498. doi: 10.1287/mnsc.13.7.492 [Crossref], [Google Scholar]
[13] Crouzeix JP, Ferland JA. Algorithms for generalized fractional programming. Math Program. 1991;52(1-3):191–207. doi: 10.1007/BF01582887 [Crossref], [Google Scholar]
[14] Crouzeix JP, Ferland JA, Nguyen VH. Revisiting Dinkelbach-type algorithms for generalized fractional programs. OPSEARCH. 2008;45(2):97–110. doi: 10.1007/BF03398807 [Crossref], [Google Scholar]
[15] Orzan A, Precup R. Dinkelbach type approximation algorithms for nonlinear fractional optimization problems. Numer Funct Anal Optim. 2023;44(9):954–969. doi: 10.1080/01630563.2023.2217893 [Taylor & Francis Online] [Web of Science ®], [Google Scholar]
[16] Ródenas RG, López ML, Verastegui D. Extensions of Dinkelbach’s algorithm for solving non-linear fractional programming problems. Top. 1999;7(1):33–70. doi: 10.1007/BF02564711 [Crossref], [Google Scholar]
[17] Shi J. A combined algorithm for fractional programming. Ann Oper Res. 2001;103(1/4):135–147. doi: 10.1023/A:1012998904482 [Crossref], [Google Scholar]
[18] Tammer K, Tammer C, Ohlendorf E. Multicriterial fractional optimization. Berlin (BE): Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Mathematik; 2005. [Google Scholar]
[19] Barbu V, Precupanu T. Convexity and optimization in Banach spaces. Alphen aan de Rijn (NL): Sijthoff and Noordhoff; 1978. [Google Scholar]
[20] Cambini A, Martein L. Generalized convexity and optimization: theory and applications. Berlin (DE): Springer-Verlag; 2009. [Google Scholar]
[21] Boţ RI, Csetnek ER. Proximal-gradient algorithms for fractional programming. Optimization. 2017;66(8):1383–1396. doi: 10.1080/02331934.2017.1294592 [Taylor & Francis Online] [PubMed] [Web of Science ®], [Google Scholar]
[22] Boţ RI, Dao MN, Li G. Extrapolated proximal subgradient algorithms for nonconvex and nonsmooth fractional programs. Math Oper Res. 2021;47(3):2415–2443. [Crossref], [Google Scholar]
[23] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn. 2010;3(1):1–122. doi: 10.1561/2200000016 [Crossref], [Google Scholar]
[24] Geissler B, Morsi A, Schewe L, et al. Penalty alternating direction methods for mixed-integer optimization: a new view on feasibility pumps. SIAM J Optim. 2017;27(3):1611–1636. doi: 10.1137/16M1069687 [Crossref] [Web of Science ®], [Google Scholar]
[25] Goldstein T, O’Donoghue B, Setzer S, et al. Fast alternating direction optimization methods. SIAM J Imaging Sci. 2014;7(3):1588–1623. doi: 10.1137/120896219 [Crossref] [Web of Science ®], [Google Scholar]
[26] Kleinert T, Schmidt M. Computing feasible points of bilevel problems with a penalty alternating direction method. INFORMS J Comput. 2021;33(1):198–215. doi: 10.1287/ijoc.2019.0945 [Crossref] [Web of Science ®], [Google Scholar]
[27] Hiriart-Urruty JB. Generalized differentiability / duality and optimization for problems dealing with differences of convex functions. In: Ponstein J, editor. Convexity and duality in optimization. Lecture notes in economics and mathematical systems, vol. 256. Berlin, Heidelberg (DE): Springer; 1985. p. 37–70. [Crossref], [Google Scholar]
[28] Le Thi HA, Pham DT. The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann Oper Res. 2005;133(1-4):23–46. doi: 10.1007/s10479-004-5022-1 [Crossref] [Web of Science ®], [Google Scholar]
[29] Le Thi HA, Pham DT. Open issues and recent advances in DC programming and DCA. J Glob Optim. 2023. doi: 10.1007/s10898-023-01272-1 [Crossref] [Web of Science ®], [Google Scholar]
[30] de Oliveira W. The ABC of DC programming. Set-Valued Var Anal. 2020;28(4):679–706. doi: 10.1007/s11228-020-00566-w [Crossref] [Web of Science ®], [Google Scholar]
[31] Singer I. Duality for nonconvex approximation and optimization. New York (NY): Springer; 2006. [Crossref], [Google Scholar]
[32] Toland JF. A duality principle for non-convex optimisation and the calculus of variations. Arch Rational Mech Anal. 1979;71(1):41–61. doi: 10.1007/BF00250669 [Crossref] [Web of Science ®], [Google Scholar]
[33] Breckner WW, Kassay G. A systematization of convexity concepts for sets and functions. J Convex Anal. 1997;4:109–127. [Google Scholar]
[34] Zălinescu C. Convex analysis in general vector spaces. Singapore (SG): World Scientific Publising; 2002. [Crossref], [Google Scholar]
[35] Precup R. Methods in nonlinear integral equations. Dordrecht (DR): Springer; 2002. [Crossref], [Google Scholar]
[36] Precup R. Nash-type equilibria and periodic solutions to nonvariational systems. Adv Nonlinear Anal. 2014;3:197–207. doi: 10.1515/anona-2014-0006 [Crossref] [Web of Science ®], [Google Scholar]