Search Advanced

AIMS Mathematics

2025, Volume 10, Issue 9: 22650-22677. doi: 10.3934/math.20251008
Previous Article Next Article
Research article

A linear fractional relaxation-based algorithm for solving sum-of-linear- ratios problems

  • 1.
    School of Mathematics and Information Sciences, North Minzu University, Yinchuan, 750021, China
  • 2.
    Ningxia province key laboratory of intelligent information and data processing, North Minzu University, Yinchuan, 750021, China
  • 3.
    Ningxia mathematics basic discipline research center, North Minzu University, Yinchuan, 750021, China
  • Published: 29 September 2025

  • MSC : 90C26, 90C32

  • This paper investigated the linear ratio sum problem, a complex non-convex optimization problem with extensive applications in finance, economics, computer vision, and other fields. We proposed a novel global optimization approach that reformulated the original problem into an equivalent one with nonlinear constraints. The approach constructed linear fractional relaxation subproblems via constraint relaxation and leveraged the structural properties of the relaxations to transform these subproblems into linear programming formulations, thereby ensuring efficient computation. Furthermore, rectangular branching rules were designed based on the relaxed nonlinear constraints. These rules, complemented by region elimination techniques, accelerated convergence by exploiting the structure of the objective function. By integrating these components into a branch-and-bound framework, a novel global optimization algorithm was devised. Theoretical analysis confirmed the convergence and computational complexity of the proposed algorithm, while numerical tests validated its effectiveness and feasibility.

    Citation: Bo Zhang, Ying Sun, Ying Qiao, Yuelin Gao. A linear fractional relaxation-based algorithm for solving sum-of-linear- ratios problems[J]. AIMS Mathematics, 2025, 10(9): 22650-22677. doi: 10.3934/math.20251008

    Related Papers:

  • This paper investigated the linear ratio sum problem, a complex non-convex optimization problem with extensive applications in finance, economics, computer vision, and other fields. We proposed a novel global optimization approach that reformulated the original problem into an equivalent one with nonlinear constraints. The approach constructed linear fractional relaxation subproblems via constraint relaxation and leveraged the structural properties of the relaxations to transform these subproblems into linear programming formulations, thereby ensuring efficient computation. Furthermore, rectangular branching rules were designed based on the relaxed nonlinear constraints. These rules, complemented by region elimination techniques, accelerated convergence by exploiting the structure of the objective function. By integrating these components into a branch-and-bound framework, a novel global optimization algorithm was devised. Theoretical analysis confirmed the convergence and computational complexity of the proposed algorithm, while numerical tests validated its effectiveness and feasibility.



    加载中


    [1] B. Zhang, Y. Gao, Y. Qiao, Y. Sun, A nonlinear relaxation-strategy-based algorithm for solving sum-of-linear-ratios problems, AIMS Math., 9 (2024), 25396–25412. http://dx.doi.org/10.3934/math.20241240 doi: 10.3934/math.20241240
    [2] S. Schaible, Fractional programming, In: Handbook of global optimization, Boston: Springer, 1995. http://dx.doi.org/10.1007/978-1-4615-2025-2_10
    [3] H. Konno, H. Watanabe, Bond portfolio optimization problems and their applications to index tracking: A partial optimization approach, J. Oper. Res. Soc. Jpn., 39 (1996), 295–306. http://dx.doi.org/10.15807/jorsj.39.295 doi: 10.15807/jorsj.39.295
    [4] 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
    [5] B. Sawik, Downside risk approach for multi-objective portfolio optimization, In: Operations Research Proceedings 2011, Berlin: Springer, 2012. http://dx.doi.org/10.1007/978-3-642-29210-1_31
    [6] 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
    [7] 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
    [8] T. Matsui, NP-hardness of linear multiplicative programming and related problems, J. Glob. Optim., 9 (1996), 113–119. http://dx.doi.org/10.1007/BF00121658 doi: 10.1007/BF00121658
    [9] A. Charnes, W. Cooper, Programming with linear fractional functionals, Nav. Res. Log., 9 (1962), 181–186. http://dx.doi.org/10.1002/nav.3800090303 doi: 10.1002/nav.3800090303
    [10] 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
    [11] H. Konno, Y. Yajima, T. Matsui, Parametric simplex algorithms for solving a special class of nonconvex minimization problems, J. Glob. Optim., 1 (1991), 65–81. http://dx.doi.org/10.1007/BF00120666 doi: 10.1007/BF00120666
    [12] 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. Glob. Optim., 77 (2020), 301–318. http://dx.doi.org/10.1007/s10898-019-00870-2 doi: 10.1007/s10898-019-00870-2
    [13] Y. Nesterov, A. Nemirovskii, An interior-point method for generalized linear-fractional programming, Math. Program., 69 (1995), 177–204. http://dx.doi.org/10.1007/BF01585557 doi: 10.1007/BF01585557
    [14] H. Konno, N. Abe, Minimization of the sum of three linear fractional functions, J. Glob. Optim., 15 (1999), 419–432. http://dx.doi.org/10.1023/A:1008376731013 doi: 10.1023/A:1008376731013
    [15] H. Benson, On the global optimization of sums of linear fractional functions 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
    [16] 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
    [17] J. Falk, S. Palocsay, Image space analysis of generalized fractional programs, J. Glob. Optim., 4 (1994), 63–88. http://dx.doi.org/10.1007/BF01096535 doi: 10.1007/BF01096535
    [18] N. Phuong, H. Tuy, A unified monotonic approach to generalized linear fractional programming, J. Glob. Optim., 26 (2003), 229–259. http://dx.doi.org/10.1023/A:1023274721632 doi: 10.1023/A:1023274721632
    [19] 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
    [20] 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
    [21] 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
    [22] J. Carlsson, J. Shi, A linear relaxation algorithm for solving the sum-of-linear-ratios problem with lower dimension, Oper. 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
    [23] 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
    [24] 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
    [25] 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
    [26] B. Zhang, Y. Gao, An output-space based branch-and-bound algorithm for sum-of-linear-ratios problem, Asia Pac. J. Oper. Res., 40 (2023), 2250010. http://dx.doi.org/10.1142/S0217595922500105 doi: 10.1142/S0217595922500105
    [27] 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
    [28] 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
    [29] 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
    [30] P. Shen, Y. Wang, D. Wu, A spatial branch and bound algorithm for solving the sum of linear ratios optimization problem, Numer. Algor., 93 (2023), 1373–1400. http://dx.doi.org/10.1007/s11075-022-01471-z doi: 10.1007/s11075-022-01471-z
    [31] B. Huang, P. Shen, An efficient global optimization algorithm for the sum of linear ratios problems based on a novel adjustable branching rule, Comput. Optim. Appl., 91 (2025), 1339–1371. http://dx.doi.org/10.1007/s10589-025-00679-8 doi: 10.1007/s10589-025-00679-8
    [32] H. Luo, Y. Xu, H. Wu, G. Wang, A new branch-and-cut algorithm for linear sum-of-ratios problem based on slo method and lo relaxation, Comput. Optim. Appl., 90 (2025), 257–301. http://dx.doi.org/10.1007/s10589-024-00622-3 doi: 10.1007/s10589-024-00622-3
    [33] Y. Deng, P. Shen, An adaptive branch-and-bound reduction algorithm for minimizing sum of linear ratios programs, Comput. Appl. Math., 44 (2025), 107. http://dx.doi.org/10.1007/s40314-024-03063-0 doi: 10.1007/s40314-024-03063-0
    [34] A. Khajavirad, N. Sahinidis, A hybrid LP/NLP paradigm for global optimization relaxations, Math. Prog. Comp., 10 (2018), 383–421. http://dx.doi.org/10.1007/s12532-018-0138-5 doi: 10.1007/s12532-018-0138-5
    [35] F. H. Mathis, L. J. Mathis, A nonlinear programming algorithm for hospital management, SIAM Rev., 37 (1995), 230–234. https://doi.org/10.1137/1037046 doi: 10.1137/1037046
    [36] P. Shen, Y. Deng, Y. Wang, A one-dimensional branching rule based branch-and-bound algorithm for minimax linear fractional programming, J. Comput. Appl. Math., 448 (2024), 115900. http://dx.doi.org/10.1016/j.cam.2024.115900 doi: 10.1016/j.cam.2024.115900
  • Reader Comments
  • © 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
AIMS Mathematics
1.8 3.1

Metrics

Article views(501) PDF downloads(67) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(6)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog