This paper mainly studies the sum-of-linear-ratios problems, which have important applications in finance, economy and computational vision. In this process, we first propose a new method to re-represent the original problem as an equivalent problem (EP). Secondly, by relaxing these constraints, a nonlinear relaxation subproblem is constructed for EP. In view of the special structure of the relaxation, it is reconstructed as a second-order cone programming (SOCP) problem, which is essentially a SOCP relaxation of EP. Thirdly, through the structural characteristics of the objective function of EP, a region reduction technique is designed to accelerate the termination of the algorithm as much as possible. By integrating the SOCP relaxation and acceleration strategy into the branch and bound framework, a new global optimization algorithm is developed. Further, the theoretical convergence and computational complexity of the algorithm are analyzed. Numerical experiment results reveal that the algorithm is effective and feasible.
Citation: Bo Zhang, Yuelin Gao, Ying Qiao, Ying Sun. A nonlinear relaxation-strategy-based algorithm for solving sum-of-linear-ratios problems[J]. AIMS Mathematics, 2024, 9(9): 25396-25412. doi: 10.3934/math.20241240
This paper mainly studies the sum-of-linear-ratios problems, which have important applications in finance, economy and computational vision. In this process, we first propose a new method to re-represent the original problem as an equivalent problem (EP). Secondly, by relaxing these constraints, a nonlinear relaxation subproblem is constructed for EP. In view of the special structure of the relaxation, it is reconstructed as a second-order cone programming (SOCP) problem, which is essentially a SOCP relaxation of EP. Thirdly, through the structural characteristics of the objective function of EP, a region reduction technique is designed to accelerate the termination of the algorithm as much as possible. By integrating the SOCP relaxation and acceleration strategy into the branch and bound framework, a new global optimization algorithm is developed. Further, the theoretical convergence and computational complexity of the algorithm are analyzed. Numerical experiment results reveal that the algorithm is effective and feasible.
| [1] |
B. Zhang, Y. Gao, X. Liu, X. Huang, A new deterministic global computing algorithm for solving a kind of linear fractional programming, Optimization, 72 (2023), 1485–1531. http://dx.doi.org/10.1080/02331934.2022.2027940 doi: 10.1080/02331934.2022.2027940
|
| [2] |
B. Zhang, Y. Gao, An output-space based branch-and-bound algorithm for sum-of-linear-ratios problem, Asia Pac. J. Oper. Res., 42 (2023), 2250010. http://dx.doi.org/10.1142/S0217595922500105 doi: 10.1142/S0217595922500105
|
| [3] | S. Schaible, Fractional programming, In: Horst, R., Pardalos, P.M. (eds) Handbook of Global Optimization. Nonconvex Optimization and Its Applications, Boston: Springer Press, 1995. http://dx.doi.org/10.1007/978-1-4615-2025-2_10 |
| [4] |
H. Konno, H. Watanabe, Bond portfolio optimization problems and their applications to index tracking: A partial optimization approach, J. Oper. Res. Soc. Jpn., 39 (2017), 295–306. http://dx.doi.org/10.2307/3010378 doi: 10.2307/3010378
|
| [5] |
H. Konno, M. Inori, Bond portfolio optimization by bilinear fractional programming, J. Oper. Res. Soc. Jpn., 32 (1989), 143–158. http://dx.doi.org/10.2307/2583552 doi: 10.2307/2583552
|
| [6] |
C. Colantoni, R. Manes, A. Whinston, Programming, profit rates and pricing decisions, Account. Rev., 44 (1969), 467–481. http://dx.doi.org/10.2307/244427 doi: 10.2307/244427
|
| [7] | B. Sawik, Downside risk approach for multi-objective portfolio optimization, In: Klatte, D., Luthi, HJ., Schmedders, K. (eds) Operations Research Proceedings 2011, Berlin: Springer Press, 2012. http://dx.doi.org/10.1007/978-3-642-29210-1_31 |
| [8] |
A. Billionnet, Mathematical optimization ideas for biodiversity conservation, Eur. J. Oper. Res., 231 (2013), 514–534. http://dx.doi.org/10.1016/j.ejor.2013.03.025 doi: 10.1016/j.ejor.2013.03.025
|
| [9] |
C. Kao, Network data envelopment analysis: A review, Eur. J. Oper. Res., 239 (2014), 1–16. http://dx.doi.org/10.1016/j.ejor.2014.02.039 doi: 10.1016/j.ejor.2014.02.039
|
| [10] |
T. Kuno, T. Masaki, A practical but rigorous approach to sum-of-ratios optimization in geometric applications, Comput. Optim. Appl., 54 (2013), 93–109. http://dx.doi.org/10.1007/s10589-012-9488-5 doi: 10.1007/s10589-012-9488-5
|
| [11] |
A. Fakhri, M. Ghatee, Minimizing the sum of a linear and a linear fractional function applying conic quadratic representation: Continuous and discrete problems, Optimization, 65 (2016), 1023–1038. http://dx.doi.org/10.1080/02331934.2015.1113532 doi: 10.1080/02331934.2015.1113532
|
| [12] |
T. Matsui, NP-hardness of linear multiplicative programming and related problems, J. Global Optim., 9 (1996), 113–119. http://dx.doi.org/10.1007/BF00121658 doi: 10.1007/BF00121658
|
| [13] |
B. Ozkok, An iterative algorithm to solve a linear fractional programming problem, Comput. Ind. Eng., 140 (2020), 106234. http://dx.doi.org/10.1016/j.cie.2019.106234 doi: 10.1016/j.cie.2019.106234
|
| [14] |
A. Charnes, W. Cooper, Programming with linear fractional functionals, Nav. Res. Log., 9 (1962), 181–186. http://dx.doi.org/10.1002/nav.3800150308 doi: 10.1002/nav.3800150308
|
| [15] |
H. Konno, Y. Yajima, T. Matsui, Parametric simplex algorithms for solving a special class of nonconvex minimization problems, J. Global Optim., 1 (1991), 65–81. http://dx.doi.org/10.1007/BF00120666 doi: 10.1007/BF00120666
|
| [16] |
Y. Xia, L. Wang, X. Wang, Globally minimizing the sum of a convex-concave fraction and a convex function based on wave-curve bounds, J. Global Optim., 77 (2020), 301–318. http://dx.doi.org/10.1007/s10898-019-00870-2 doi: 10.1007/s10898-019-00870-2
|
| [17] |
Y. Nesterov, A. Nemirovskii, An interior-point method for generalized linear-fractional programming, Math. Program., 69 (2003), 177–204. http://dx.doi.org/10.1007/BF01585557 doi: 10.1007/BF01585557
|
| [18] |
H. Konno, N. Abe, Minimization of the sum of three linear fractional functions, J. Global Optim., 15 (1999), 419–432. http://dx.doi.org/10.1023/A:1008376731013 doi: 10.1023/A:1008376731013
|
| [19] |
H. Benson, On the global optimization of sums of linear fractional func- tions over a convex set, J. Optim. Theory Appl., 121 (2004), 19–39. http://dx.doi.org/10.1023/B:JOTA.0000026129.07165.5a doi: 10.1023/B:JOTA.0000026129.07165.5a
|
| [20] |
P. Shen, B. Huang, L. Wang, Range division and linearization algorithm for a class of linear ratios optimization problems, J. Comput. Appl. Math., 350 (2019), 324–342. http://dx.doi.org/10.1016/j.cam.2018.10.038 doi: 10.1016/j.cam.2018.10.038
|
| [21] |
J. Falk, S. Palocsay, Image space analysis of generalized fractional programs, J. Global Optim., 4 (1994), 63–88. http://dx.doi.org/10.1007/BF01096535 doi: 10.1007/BF01096535
|
| [22] |
N. Phuong, H. Tuy, A unified monotonic approach to generalized linear fractional programming, J. Global Optim., 26 (2003), 229–259. http://dx.doi.org/10.1007/BF01096535 doi: 10.1007/BF01096535
|
| [23] |
H. Konno, H. Yamashita, Minimizing sums and products of linear fractional functions over a polytope, Nav. Res. Log., 46 (1999), 583–596. http://dx.doi.org/10.1002/(SICI)1520-6750(199908)46:5<583::AID-NAV8>3.0.CO;2-5 doi: 10.1002/(SICI)1520-6750(199908)46:5<583::AID-NAV8>3.0.CO;2-5
|
| [24] |
H. Benson, A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem, Eur. J. Oper. Res., 182 (2007), 597–611. http://dx.doi.org/10.1016/j.ejor.2006.08.036 doi: 10.1016/j.ejor.2006.08.036
|
| [25] |
H. Benson, Branch-and-bound outer approximation algorithm for sum-of-ratios fractional programs, J. Optim. Theory Appl., 146 (2010), 1–18. http://dx.doi.org/10.1007/s10957-010-9647-8 doi: 10.1007/s10957-010-9647-8
|
| [26] |
J. Carlsson, J. Shi, A linear relaxation algorithm for solving the sum-of-linear-ratios problem with lower dimension, Ope. Res. Lett., 41 (2013), 381–389. http://dx.doi.org/10.1016/j.orl.2013.04.005 doi: 10.1016/j.orl.2013.04.005
|
| [27] |
H. Jiao, B. Li, Y. Shang, An outer space approach to tackle generalized affine fractional program problems, J. Optim. Theory Appl., 201 (2024), 1–35. http://dx.doi.org/10.1007/s10957-023-02368-0 doi: 10.1007/s10957-023-02368-0
|
| [28] |
H. Jiao, B. Li, W. Yang, A criterion-space branch-reduction-bound algorithm for solving generalized multiplicative problems, J. Global Optim., 89 (2024), 597–632. http://dx.doi.org/10.1007/s10898-023-01358-w doi: 10.1007/s10898-023-01358-w
|
| [29] |
A. Ashtiani, A. Paulo, A branch-and-cut algorithm for a class of sum-of-ratios problems, Appl. Math. Comput., 268 (2015), 596–608. http://dx.doi.org/10.1016/j.amc.2015.06.089 doi: 10.1016/j.amc.2015.06.089
|
| [30] |
H. Jiao, S. Liu, A practicable branch and bound algorithm for sum of linear ratios problem, Eur. J. Oper. Res., 243 (2015), 723–730. http://dx.doi.org/10.1016/j.ejor.2015.01.039 doi: 10.1016/j.ejor.2015.01.039
|
| [31] |
S. Liu, L. Ge, An outcome space algorithm for minimizing a class of linear ratio optimization problems, Comput. Appl. Math., 40 (2021), 225. http://dx.doi.org/10.1007/s40314-021-01614-3 doi: 10.1007/s40314-021-01614-3
|
| [32] |
X. Liu, Y. Gao, B. Zhang, A new global optimization algorithm for a class of linear fractional programming, Mathematics, 7 (2019), 867. http://dx.doi.org/10.3390/math7090867 doi: 10.3390/math7090867
|
| [33] |
H. Jiao, J. Ma, An efficient algorithm and complexity result for solving the sum of general affine ratios problem, Chaos Soliton. Fract., 164 (2022), 112701. http://dx.doi.org/10.1016/j.chaos.2022.112701 doi: 10.1016/j.chaos.2022.112701
|
| [34] |
P. Shen, Y. Wang, D. Wu, A spatial branch and bound algorithm for solving the sum of linear ratios optimization problem, Numer. Algorithms, 93 (2023), 1373–1400. http://dx.doi.org/10.1007/s11075-022-01471-z doi: 10.1007/s11075-022-01471-z
|
| [35] |
I. Stancu-Minasian, A ninth bibliography of fractional programming, Optimization, 68 (2019), 2125–2169. http://dx.doi.org/10.1080/02331934.2019.1632250 doi: 10.1080/02331934.2019.1632250
|
| [36] |
P. Shen, T. Lu, Regional division and reduction algorithm for minimizing the sum of linear fractional functions, J. Inequal. Appl., 2018 (2018), 63. http://dx.doi.org/10.1186/s13660-018-1651-9 doi: 10.1186/s13660-018-1651-9
|
| [37] |
A. Khajavirad, N. Sahinidis, A hybrid LP/NLP paradigm for global optimization relaxations, Math. Prog. Comput., 10 (2018), 383–421. http://dx.doi.org/10.1007/s12532-018-0138-5 doi: 10.1007/s12532-018-0138-5
|
Bo Zhang, Yuelin Gao, Ying Qiao, Ying Sun. A nonlinear relaxation-strategy-based algorithm for solving sum-of-linear-ratios problems[J]. AIMS Mathematics, 2024, 9(9): 25396-25412. doi: 10.3934/math.20241240
DownLoad: