Search Advanced

AIMS Mathematics

2023, Volume 8, Issue 4: 9247-9264. doi: 10.3934/math.2023464
Previous Article Next Article
Research article

A novel algorithm for solving sum of several affine fractional functions

  • 1.
    School of Science, Beijing University of Technology, Beijing 100124, China
  • 2.
    School of Mathematics and Statistics, Nanyang Normal University, Nanyang 473061, China
  • 3.
    School of Mathematical Sciences, Henan Institute of Science and Technology, Xinxiang 453003, China
  • 4.
    Postdoctoral Research Station of Control Science and Engineering, Henan University of Science and Technology, Luoyang 471023, China
  • Received: 17 October 2022 Revised: 18 January 2023 Accepted: 01 February 2023 Published: 14 February 2023

  • MSC : 90C26, 90C32

  • By using the outer space branch-and-reduction scheme, we present a novel algorithm for globally optimizing the sum of several affine fractional functions problem (SAFFP) over a nonempty compact set. For providing the reliable lower bounds in the searching process of iterations, we devise a novel linearizing method to establish the affine relaxation problem (ARP) for the SAFFP. Thus, the main computational work involves solving a series of ARP. For improving the convergence speed of the algorithm, an outer space region reduction technique is proposed by utilizing the objective function characteristics. Through computational complexity analysis, we estimate the algorithmic maximum iteration times. Finally, numerical comparison results are given to reveal the algorithmic computational advantages.

    Citation: Hongwu Li, Yuling Feng, Hongwei Jiao, Youlin Shang. A novel algorithm for solving sum of several affine fractional functions[J]. AIMS Mathematics, 2023, 8(4): 9247-9264. doi: 10.3934/math.2023464

    Related Papers:

  • By using the outer space branch-and-reduction scheme, we present a novel algorithm for globally optimizing the sum of several affine fractional functions problem (SAFFP) over a nonempty compact set. For providing the reliable lower bounds in the searching process of iterations, we devise a novel linearizing method to establish the affine relaxation problem (ARP) for the SAFFP. Thus, the main computational work involves solving a series of ARP. For improving the convergence speed of the algorithm, an outer space region reduction technique is proposed by utilizing the objective function characteristics. Through computational complexity analysis, we estimate the algorithmic maximum iteration times. Finally, numerical comparison results are given to reveal the algorithmic computational advantages.


    加载中


    [1] E. B. Bajalinov, Linear-fractional programming theory, methods, applications and software, Springer Science & Business Media, Vol. 84, 2003. https://doi.org/10.1007/978-1-4419-9174-4
    [2] I. M. Stancu-Minasian, A eighth bibliography of fractional programming, Optimization, 66 (2017), 439-470. https://doi.org/10.1080/02331934.2016.1276179 doi: 10.1080/02331934.2016.1276179
    [3] T. Kuno, T. Masaki, A practical but rigorous approach to sum-of-ratios optimization in geometric applications, Comput. Optim. Appl., 54 (2013), 93-109. https://doi.org/10.1007/s10589-012-9488-5 doi: 10.1007/s10589-012-9488-5
    [4] I. M. Stancu-Minasian, A ninth bibliography of fractional programming, Optimization, 68 (2019), 2125-2169. https://doi.org/10.1080/02331934.2019.1632250 doi: 10.1080/02331934.2019.1632250
    [5] Y. Ji, H. Li, H. Zhang, Risk-averse two-stage stochastic minimum cost consensus models with asymmetric adjustment cost, Group Decis. Negot., 31 (2022), 261-291. https://doi.org/10.1007/s10726-021-09752-z doi: 10.1007/s10726-021-09752-z
    [6] S. Qu, L. Shu, J. Yao, Optimal pricing and service level in supply chain considering misreport behavior and fairness concern, Comput. Ind. Eng., 174 (2022), 108759. https://doi.org/10.1016/j.cie.2022.108759 doi: 10.1016/j.cie.2022.108759
    [7] 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. https://doi.org/10.1007/BF00120666 doi: 10.1007/BF00120666
    [8] H. Konno, H. Yamashita, Minimizing sums and products of linear fractional functions over a polytope, Nav. Res. Log., 46 (1999), 583-596.
    [9] J. E. Falk, S. W. Palocsay, Image space analysis of generalized fractional programs, J. Glob. Optim., 4 (1994), 63-88. https://doi.org/10.1007/BF01096535 doi: 10.1007/BF01096535
    [10] N. T. H. Phuong, H. Tuy, A unified monotonic approach to generalized linear fractional programming, J. Glob. Optim., 26 (2003), 229-259. https://doi.org/10.1023/A:1023274721632 doi: 10.1023/A:1023274721632
    [11] H. Konno, K. Fukaishi, A branch-and-bound algorithm for solving low-rank linear multiplicative and fractional programming problems, J. Glob. Optim., 18 (2000), 283-299. https://doi.org/10.1023/A:1008314922240 doi: 10.1023/A:1008314922240
    [12] H. Jiao, S. Liu, A practicable branch and bound algorithm for sum of linear ratios problem, Eur. J. Oper. Res., 243 (2015), 723-730. https://doi.org/10.1016/j.ejor.2015.01.039 doi: 10.1016/j.ejor.2015.01.039
    [13] Y. Ji, K. C. Zhang, S. J. Qu, A deterministic global optimization algorithm, Appl. Math. Comput., 185 (2007), 382-387. https://doi.org/10.1016/j.amc.2006.06.101 doi: 10.1016/j.amc.2006.06.101
    [14] H. P. Benson, A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem, Eur. J. Oper. Res., 182 (2007), 597-611. https://doi.org/10.1016/j.ejor.2006.08.036 doi: 10.1016/j.ejor.2006.08.036
    [15] T. Kuno, A revision of the trapezoidal branch-and-bound algorithm for linear sum-of-ratios problems, J. Glob. Optim., 33 (2005), 215-234. https://doi.org/10.1007/s10898-004-1952-z doi: 10.1007/s10898-004-1952-z
    [16] H. Jiao, Y. Shang, W. Wang, Solving generalized polynomial problem by using new affine relaxed technique, Int. J. Comput. Math., 99 (2022), 309-331. https://doi.org/10.1080/00207160.2021.1909727 doi: 10.1080/00207160.2021.1909727
    [17] H. W. Jiao, Y. L. Shang, Two-level linear relaxation method for generalized linear fractional programming, J. Oper. Res. Soc. China, 2022, 1-26. https://doi.org/10.1007/s40305-021-00375-4
    [18] H. Jiao, Y. Shang, R. Chen, A potential practical algorithm for minimizing the sum of affine fractional functions, Optimization, 2022, 1-31. https://doi.org/10.1080/02331934.2022.2032051
    [19] H. Jiao, J. Ma, P. Shen, Y. Qiu, Effective algorithm and computational complexity for solving sum of linear ratios problem, J. Ind. Manag. Optim., 2022. https://doi.org/10.3934/jimo.2022135
    [20] H. Jiao, J. Ma, An efficient algorithm and complexity result for solving the sum of general ratios problem, Chaos Soliton. Fract., 164 (2022), 112701. https://doi.org/10.1016/j.chaos.2022.112701 doi: 10.1016/j.chaos.2022.112701
    [21] H. Jiao, B. Li, Solving min-max linear fractional programs based on image space branch-and-bound scheme, Chaos Soliton. Fract., 164 (2022), 112682. https://doi.org/10.1016/j.chaos.2022.112682 doi: 10.1016/j.chaos.2022.112682
    [22] H. Jiao, W. Wang, Y. Shang, Outer space branch-reduction-bound algorithm for solving generalized affine multiplicative problem, J. Comput. Appl. Math., 419 (2023), 114784. https://doi.org/10.1016/j.cam.2022.114784 doi: 10.1016/j.cam.2022.114784
    [23] H. Jiao, J. Ma, Y. Shang, Image space branch-and-bound algorithm for globally solving minimax linear fractional programming problem, Pac. J. Optim., 18 (2022), 195-212.
    [24] J. Ma, H. Jiao, J. Yin, Y. Shang, Outer space branching search method for solving generalized affine fractional optimization problem, AIMS Math., 8 (2022), 1959-1974. https://doi.org/10.3934/math.2023101 doi: 10.3934/math.2023101
    [25] H. Jiao, W. Wang, J. Yin, Y. Shang, Image space branch-reduction-bound algorithm for globally minimizing a class of multiplicative problems, RAIRO-Oper. Res., 56 (2022), 1533-1552. https://doi.org/10.1051/ro/2022061 doi: 10.1051/ro/2022061
    [26] H. Jiao, R. Chen, A parametric linearizing approach for quadratically inequality constrained quadratic programs, Open Math., 16 (2018), 407-419. https://doi.org/10.1515/math-2018-0037 doi: 10.1515/math-2018-0037
    [27] H. Jiao, S. Liu, An efficient algorithm for quadratic sum-of-ratios fractional programs problem, Numer. Func. Anal. Optim., 38 (2017), 1426-1445. https://doi.org/10.1080/01630563.2017.1327869 doi: 10.1080/01630563.2017.1327869
    [28] H. Jiao, S. Liu, J. Yin, Y. Zhao, Outcome space range reduction method for global optimization of sum of affine ratios problem, Open Math., 14 (2016), 736-746. https://doi.org/10.1515/math-2016-0058 doi: 10.1515/math-2016-0058
    [29] 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. https://doi.org/10.1016/j.cam.2018.10.038 doi: 10.1016/j.cam.2018.10.038
    [30] D. Depetrini, M. Locatelli, Approximation algorithm for linear fractional multiplicative problems, Math. Program., 128 (2011), 437-443. https://doi.org/10.1007/s10107-009-0309-2 doi: 10.1007/s10107-009-0309-2
    [31] S. Schaible, J. Shi, Fractional programming: the sum-of-ratios case, Optim. Method. Softw., 18 (2003), 219-229. https://doi.org/10.1080/1055678031000105242 doi: 10.1080/1055678031000105242
    [32] P. Saxena, R. Jain, Duality in linear fractional programming under fuzzy environment using hyperbolic membership functions, Int. J. Fuzzy Syst. Appl. (IJFSA), 9 (2020), 1-21. https://doi.org/10.4018/IJFSA.2020070101 doi: 10.4018/IJFSA.2020070101
    [33] M. Borza, A. S. Rambely, A linearization to the sum of linear ratios programming problem, Mathematics, 9 (2021), 1004. https://doi.org/10.3390/math9091004 doi: 10.3390/math9091004
    [34] M. Goli, S. H. Nasseri, Extension of duality results and a dual simplex method for linear programming problems with intuitionistic fuzzy variables, Fuzzy Inf. Eng., 12 (2020), 392-411. https://doi.org/10.1080/16168658.2021.1908818 doi: 10.1080/16168658.2021.1908818
    [35] R. Horst, H. Tuy, Global optimization: deterministic approaches, Springer Science & Business Media, 2013. https://doi.org/10.1007/978-3-662-02598-7
    [36] A. Khajavirad, N. V. Sahinidis, A hybrid LP/NLP paradigm for global optimization relaxations, Math. Program. Comput., 10 (2018), 383-421. https://doi.org/10.1007/s12532-018-0138-5 doi: 10.1007/s12532-018-0138-5
  • Reader Comments
  • © 2023 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.4

Metrics

Article views(831) PDF downloads(55) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(2)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog