IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v192y2022i3d10.1007_s10957-021-01992-y.html
   My bibliography  Save this article

An Outcome-Space-Based Branch-and-Bound Algorithm for a Class of Sum-of-Fractions Problems

Author

Listed:
  • Bo Zhang

    (Ningxia University)

  • YueLin Gao

    (North Minzu University
    North Minzu University)

  • Xia Liu

    (Ningxia University)

  • XiaoLi Huang

    (North Minzu University)

Abstract

In this paper, we study the problem of maximizing the sum of a concave–convex quadratic fractional function on a non-empty, bounded, convex quadratic feasible set, which is called the problem (QCQFP). By using a conventional semidefinite program (SDP) relaxation, QCQFP is reformulated as a class of linear fractional programming problems over the cone of positive semidefinite matrices, which we refer to these problems as SDFP. After expatiating the properties of SDFP, we transform SDFP into its equivalent problem (ESDFP) whose non-convexity is mainly reflected in the newly added nonlinear equality constraints. By relaxing these nonlinear equality constraints into linear constraints, a special SDP relaxation is generated for ESDFP. Based on these results, an effective branch-and-bound algorithm is designed, and its theoretical convergence and worst-case complexity are proved. Numerical experiments demonstrate that the proposed algorithm is effective and feasible.

Suggested Citation

  • Bo Zhang & YueLin Gao & Xia Liu & XiaoLi Huang, 2022. "An Outcome-Space-Based Branch-and-Bound Algorithm for a Class of Sum-of-Fractions Problems," Journal of Optimization Theory and Applications, Springer, vol. 192(3), pages 830-855, March.
    • Handle: RePEc:spr:joptap:v:192:y:2022:i:3:d:10.1007_s10957-021-01992-y
    DOI: 10.1007/s10957-021-01992-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-021-01992-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-021-01992-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Jiao, Hong-Wei & Liu, San-Yang, 2015. "A practicable branch and bound algorithm for sum of linear ratios problem," European Journal of Operational Research, Elsevier, vol. 243(3), pages 723-730.
    2. Peiping Shen & Kaimin Wang & Ting Lu, 2020. "Outer space branch and bound algorithm for solving linear multiplicative programming problems," Journal of Global Optimization, Springer, vol. 78(3), pages 453-482, November.
    3. Bartosz Sawik, 2012. "Downside Risk Approach for Multi-Objective Portfolio Optimization," Operations Research Proceedings, in: Diethard Klatte & Hans-Jakob Lüthi & Karl Schmedders (ed.), Operations Research Proceedings 2011, edition 127, pages 191-196, Springer.
    4. Cheng Lu & Zhibin Deng & Qingwei Jin, 2017. "An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints," Journal of Global Optimization, Springer, vol. 67(3), pages 475-493, March.
    5. Ashtiani, Alireza M. & Ferreira, Paulo A.V., 2015. "A branch-and-cut algorithm for a class of sum-of-ratios problems," Applied Mathematics and Computation, Elsevier, vol. 268(C), pages 596-608.
    6. Hiroshi Konno & Hajime Yamashita, 1999. "Minimizing sums and products of linear fractional functions over a polytope," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(5), pages 583-596, August.
    7. Nesterov, Y. & Nemirovskii, A., 1995. "An interior-point method for generalized linear-fractional programming," LIDAM Reprints CORE 1168, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Schaible, Siegfried & Ibaraki, Toshidide, 1983. "Fractional programming," European Journal of Operational Research, Elsevier, vol. 12(4), pages 325-338, April.
    9. Lei-Hong Zhang, 2013. "On optimizing the sum of the Rayleigh quotient and the generalized Rayleigh quotient on the unit sphere," Computational Optimization and Applications, Springer, vol. 54(1), pages 111-139, January.
    10. X. Liu & Y.L. Gao & B. Zhang & F.P. Tian, 2019. "A New Global Optimization Algorithm for a Class of Linear Fractional Programming," Mathematics, MDPI, vol. 7(9), pages 1-21, September.
    11. Goedhart, Marc H. & Spronk, Jaap, 1995. "Financial planning with fractional goals," European Journal of Operational Research, Elsevier, vol. 82(1), pages 111-124, April.
    12. H. P. Benson, 2004. "On the Global Optimization of Sums of Linear Fractional Functions over a Convex Set," Journal of Optimization Theory and Applications, Springer, vol. 121(1), pages 19-39, April.
    13. Werner Dinkelbach, 1967. "On Nonlinear Fractional Programming," Management Science, INFORMS, vol. 13(7), pages 492-498, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Gao, YueLin & Zhang, Bo, 2023. "Output-space branch-and-bound reduction algorithm for generalized linear fractional-multiplicative programming problem," Chaos, Solitons & Fractals, Elsevier, vol. 175(P1).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jiao, Hongwei & Ma, Junqiao, 2022. "An efficient algorithm and complexity result for solving the sum of general affine ratios problem," Chaos, Solitons & Fractals, Elsevier, vol. 164(C).
    2. Bo Zhang & YueLin Gao & Xia Liu & XiaoLi Huang, 2023. "Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems," Journal of Global Optimization, Springer, vol. 86(1), pages 61-92, May.
    3. Hou, Zhisong & Liu, Sanyang, 2023. "A spatial branch-reduction-bound algorithm for solving generalized linear fractional problems globally," Chaos, Solitons & Fractals, Elsevier, vol. 176(C).
    4. Claassen, G.D.H., 2014. "Mixed integer (0–1) fractional programming for decision support in paper production industry," Omega, Elsevier, vol. 43(C), pages 21-29.
    5. Jalili Marand, Ata & Li, Hongyan & Thorstenson, Anders, 2019. "Joint inventory control and pricing in a service-inventory system," International Journal of Production Economics, Elsevier, vol. 209(C), pages 78-91.
    6. Gruzdeva, Tatiana V. & Strekalovsky, Alexander S., 2018. "On solving the sum-of-ratios problem," Applied Mathematics and Computation, Elsevier, vol. 318(C), pages 260-269.
    7. Mojtaba Borza & Azmin Sham Rambely, 2021. "A Linearization to the Sum of Linear Ratios Programming Problem," Mathematics, MDPI, vol. 9(9), pages 1-10, April.
    8. Abderrahman Bouhamidi & Mohammed Bellalij & Rentsen Enkhbat & Khalid Jbilou & Marcos Raydan, 2018. "Conditional Gradient Method for Double-Convex Fractional Programming Matrix Problems," Journal of Optimization Theory and Applications, Springer, vol. 176(1), pages 163-177, January.
    9. Bram L. Gorissen, 2015. "Robust Fractional Programming," Journal of Optimization Theory and Applications, Springer, vol. 166(2), pages 508-528, August.
    10. Hladík, Milan, 2010. "Generalized linear fractional programming under interval uncertainty," European Journal of Operational Research, Elsevier, vol. 205(1), pages 42-46, August.
    11. Jae Hyoung Lee & Liguo Jiao, 2018. "Solving Fractional Multicriteria Optimization Problems with Sum of Squares Convex Polynomial Data," Journal of Optimization Theory and Applications, Springer, vol. 176(2), pages 428-455, February.
    12. Shen, Peiping & Zhu, Zeyi & Chen, Xiao, 2019. "A practicable contraction approach for the sum of the generalized polynomial ratios problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 36-48.
    13. Yong Xia & Longfei Wang & Xiaohui Wang, 2020. "Globally minimizing the sum of a convex–concave fraction and a convex function based on wave-curve bounds," Journal of Global Optimization, Springer, vol. 77(2), pages 301-318, June.
    14. Chong Hyun Park & Gemma Berenguer, 2020. "Supply Constrained Location‐Distribution in Not‐for‐Profit Settings," Production and Operations Management, Production and Operations Management Society, vol. 29(11), pages 2461-2483, November.
    15. Zhijun Xu & Jing Zhou, 2021. "A Global Optimization Algorithm for Solving Linearly Constrained Quadratic Fractional Problems," Mathematics, MDPI, vol. 9(22), pages 1-12, November.
    16. Ekta Jain & Kalpana Dahiya & Vanita Verma, 2018. "Integer quadratic fractional programming problems with bounded variables," Annals of Operations Research, Springer, vol. 269(1), pages 269-295, October.
    17. Tunjo Perić & Josip Matejaš & Zoran Babić, 2023. "Advantages, sensitivity and application efficiency of the new iterative method to solve multi-objective linear fractional programming problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 31(3), pages 751-767, September.
    18. Lin, Yun Hui & Wang, Yuan & He, Dongdong & Lee, Loo Hay, 2020. "Last-mile delivery: Optimal locker location under multinomial logit choice model," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    19. Hongwei Jiao & Binbin Li & Wenqiang Yang, 2024. "A criterion-space branch-reduction-bound algorithm for solving generalized multiplicative problems," Journal of Global Optimization, Springer, vol. 89(3), pages 597-632, July.
    20. Luca Consolini & Marco Locatelli & Jiulin Wang & Yong Xia, 2020. "Efficient local search procedures for quadratic fractional programming problems," Computational Optimization and Applications, Springer, vol. 76(1), pages 201-232, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:192:y:2022:i:3:d:10.1007_s10957-021-01992-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.