• 论文 • 上一篇    下一篇

求线性比式和问题全局解的输出空间分枝定界算法

张博1, 高岳林2,3   

  1. 1. 宁夏大学数学统计学院, 银川 750021;
    2. 北方民族大学数学与信息科学学院, 银川 750021;
    3. 宁夏智能信息与大数据处理重点实验室, 银川 750021
  • 收稿日期:2021-04-27 出版日期:2022-05-14 发布日期:2022-05-06
  • 通讯作者: 高岳林,Email:gaoyuelin@263.net.
  • 基金资助:
    国家自然科学基金项目(11961001),宁夏高等教育一流学科建设资助项目(NXYLXK2017B09),北方民族大学重大专项(ZDZX201901)资助.

张博, 高岳林. 求线性比式和问题全局解的输出空间分枝定界算法[J]. 计算数学, 2022, 44(2): 233-256.

Zhang Bo, Gao YueLin. AN OUTPUT-SPACE BRANCH-AND-BOUND ALGORITHM FOR FINDING THE GLOBAL SOLUTION OF THE SUM-OF-LINEAR-RATIOS PROBLEM[J]. Mathematica Numerica Sinica, 2022, 44(2): 233-256.

AN OUTPUT-SPACE BRANCH-AND-BOUND ALGORITHM FOR FINDING THE GLOBAL SOLUTION OF THE SUM-OF-LINEAR-RATIOS PROBLEM

Zhang Bo1, Gao YueLin2,3   

  1. 1. School of Mathematics and Statistics, Ningxia University, Yinchuan 750021, China;
    2. School of mathematics and information science, North Minzu University, Ningxia, Yinchuan 750021, China;
    3. Ningxia province key laboratory of intelligent information and data processing, Ningxia, Yinchuan 750021, China
  • Received:2021-04-27 Online:2022-05-14 Published:2022-05-06
基于对p-1维输出空间进行剖分的思想,提出了一种求解线性比式和问题的分枝定界算法.通过一种两阶段转换方法得到原问题的一个等价问题,该问题的非凸性主要体现在新增加的p-1个非线性等式约束上.利用双线性函数的凹凸包络对这些非线性约束进行凸化,这就为等价问题构造了凸松弛子问题.将凸松弛子问题中的冗余约束去掉并进行等价转换,从而获得了一个比凸松弛子问题规模更小、约束更少的线性规划问题.证明了算法的理论收敛性和计算复杂性.数值实验表明该算法是有效可行的.
Based on the idea of subdividing p - 1-dimensional output space, a branch-and-bound algorithm for solving the sum-of-linear-ratios problem is proposed. An equivalent problem of the original problem is obtained by a two-stage transformation method, which makes the non-convexity mainly reflected in the newly added p-1 nonlinear equality constraints in the equivalent problem. These nonlinear constraints are convexized by using the concave and convex envelope of bilinear functions, and the convex relaxation subproblem is constructed for the equivalent problem. By removing the redundant constraints of the convex relaxation subproblem and making equivalent transformation, a linear programming problem with smaller scale and fewer constraints than the convex relaxation subproblem is obtained. The theoretical convergence and computational complexity of the algorithm are proved. Numerical experiments illustrate the validity and feasibility of the algorithm.

MR(2010)主题分类: 

()
[1] Schaible S. Fractional Programming[J]. Operations Research, 2001, 24(3):452-461.
[2] Konno H and Watanabe H. Bond portfolio optimization problems and their applications to index tracking:A partial optimization approach[J]. Journal of the Operations Research Society of Japan, 1996, 39(3):295-306.
[3] Konno H and Inori M. Bond portfolio optimization by bilinear fractional programming[J]. Journal of the Operations Research Society of Japan, 1989, 32(2):143-158.
[4] Colantoni C S, Manes R P and Whinston A. Programming, Profit Rates and Pricing Decisions[J]. Accounting Review, 1969, 44(3):467-481.
[5] Sawik B. Downside risk approach for multi-objective portfolio optimization[J]. Operations Research Proceedings. 2012, 2011:191-196.
[6] Matsui T. NP-hardness of linear multiplicative programming and related problems[J]. Journal of Global Optimization, 1996, 9(2):113-119.
[7] Jiao H W and Liu S Y. A practicable branch and bound algorithm for sum of linear ratios problem[J]. European Journal of Operational Research, 2015, 243(3):723-730.
[8] Charnes A and Cooper W W. Programming with linear fractional functionals[J]. Naval Research Logistics Quarterly, 1963, 10(1):273-274.
[9] Jiao H W, Liu S Y, Yin J B and Zhao Y F. Outcome space range reduction method for global optimization of sum of affine ratios problem[J]. Open Mathematics, 2016, 14(1):736-746.
[10] Benson H P. Branch-and-Bound Outer Approximation Algorithm for Sum-of-Ratios Fractional Programs[J]. Journal of Optimization Theory and Applications, 2010, 146(1):1-18.
[11] Carlsson J G and Shi J. A linear relaxation algorithm for solving the sum-of-linear-ratios problem with lower dimension[J]. Operations Research Letters, 2013, 41(4):381-389.
[12] Ashtiani A M, Ferreira P. A branch-and-cut algorithm for a class of sum-of-ratios problems[J]. Applied Mathematics and Computation, 2015, 268:596-608.
[13] Liu X, Gao Y, Zhang B. A new global optimization algorithm for a class of linear fractional programming[J]. Mathematics. 2019, 7(9):867.
[14] Gao Y L and Zhang B. An outcome-space branch and bound algorithm for the sum-of-linear-ratios programming problem[J]. Mathematica Numerica Sinica, 2020, 42(2):207-222.
[15] Shen P P and Lu T. Regional division and reduction algorithm for minimizing the sum of linear fractional functions[J]. Journal of Inequalities and Applications, 2018, 2018(1):63.
[16] Nesterov Y and Nemirovskii A. An interior-point method for generalized linear-fractional programming[J]. Mathematical Programming, 2003, 69:177-204.
[17] Konno H, Abe N. Minimization of the sum of three linear fractional functions[J]. Journal of Global Optimization, 1999, 15:419-432.
[18] Benson H. On the global optimization of sums of linear fractional functions over a convex set[J]. Journal of Optimization Theory and Applications, 2004, 121(1):19-39.
[19] Shen P, Zhang T and Wang C. Solving a class of generalized fractional programming problems using the feasibility of linear programs[J]. Journal of Inequalities and Applications, 2017, 2017(1):147.
[20] Shen P P, Huang B D and Wang L F. Range division and linearization algorithm for a class of linear ratios optimization problems[J]. Journal of Computational and Applied Mathematics, 2019, 350:324-342.
[21] Falk J and Palocsay S. Image space analysis of generalized fractional programs[J]. Journal of Global Optimization, 1994, 4(1):63-88.
[22] Phuong N and Tuy H. A unified monotonic approach to generalized linear fractional programming[J]. Journal of Global Optimization, 2003, 26(3):229-259.
[23] Konno H, Yajima Y and Matsui T. Parametric simplex algorithms for solving a special class of nonconvex minimization problems[J]. Journal of Global Optimization, 1991, 1:65-81.
[24] Konno H, Yamashita H. Minimizing sums and products of linear fractional functions over a polytope[J]. Naval Research Logs (NRL), 1999, 46(5):583-596.
[25] Benson H P. On the Construction of Convex and Concave Envelope Formulas for Bilinear and Fractional Functions on Quadrilaterals[J]. Computational Optimization and Applications, 2004, 27(1):5-22.
[1] 申子慧, 陈玉松. 一类特殊的分式规划问题的ε-近似算法[J]. 计算数学, 2022, 44(1): 137-144.
[2] 高岳林, 张博. 线性比式和规划问题的输出空间分支定界算法[J]. 计算数学, 2020, 42(2): 207-222.
[3] 申子慧, 申培萍. 线性分式多乘积规划问题的完全多项式时间近似算法[J]. 计算数学, 2019, 41(2): 212-218.
[4] 申培萍, 申子慧. 广义线性多乘积问题的完全多项式时间近似算法[J]. 计算数学, 2017, 39(3): 287-294.
[5] 高岳林, 吴佩佩. 非线性整数规划的一个新的无参数填充函数算法[J]. 计算数学, 2017, 39(3): 321-327.
[6] 申培萍, 申子慧. 一类广义分式规划问题的完全多项式时间近似算法[J]. 计算数学, 2015, 37(2): 179-185.
[7] 申培萍, 张永俊, 梁彦超. 一类广义分式规划问题的ε-近似算法[J]. 计算数学, 2014, 36(3): 303-308.
[8] 靳利霞,唐焕文,李斌,计明军,朱训芝. 一类连续函数模拟退火算法及其收敛性分析[J]. 计算数学, 2005, 27(1): 19-30.
[9] 陈志平,郤峰. 求解中大规模复杂凸二次整数规划问题的新型分枝定界算法[J]. 计算数学, 2004, 26(4): 445-458.
[10] 马万,王兴华. 多元积分方程自适应解法的最优化[J]. 计算数学, 2004, 26(2): 161-168.
[11] 何尚录,徐成贤. 求解一类非单调线性互补问题的路径跟踪法及其计算复杂性[J]. 计算数学, 2001, 23(3): 299-306.
阅读次数
全文


摘要