• 论文 • 上一篇    下一篇

线性比式和规划问题的输出空间分支定界算法

高岳林1,2, 张博2,3   

  1. 1. 北方民族大学数学与信息科学学院, 银川 750021;
    2. 宁夏科学计算与智能信息处理协同创新中心, 银川 750021;
    3. 宁夏大学数学统计学院, 银川 750021
  • 收稿日期:2018-07-25 出版日期:2020-05-15 发布日期:2020-05-15
  • 基金资助:

    国家自然科学基金(11961001),宁夏高等教育一流学科建设资助项目(NXYLXK2017B09),北方民族大学重大专项(ZDZX201901)资助.

高岳林, 张博. 线性比式和规划问题的输出空间分支定界算法[J]. 计算数学, 2020, 42(2): 207-222.

Gao YueLin, Zhang Bo. AN OUTCOME-SPACE BRANCH AND BOUND ALGORITHM FOR THE SUM-OF-LINEAR-RATIOS PROGRAMMING PROBLEM[J]. Mathematica Numerica Sinica, 2020, 42(2): 207-222.

AN OUTCOME-SPACE BRANCH AND BOUND ALGORITHM FOR THE SUM-OF-LINEAR-RATIOS PROGRAMMING PROBLEM

Gao YueLin1,2, Zhang Bo2,3   

  1. 1. School of mathematics and information science, North Minzu University, Yinchuan 750021, China;
    2. Ningxia province cooperative innovation center of scientific computing and intelligent information processing, Yinchuan 750021, China;
    3. School of Mathematics and Statistics, Ningxia University, Yinchuan 750021, China
  • Received:2018-07-25 Online:2020-05-15 Published:2020-05-15
本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.
In this paper, a new global optimization algorithm is proposed for a class of NP-hard nonlinear programming problems: the sum-of-linear-ratios Programming problem. First of all, the original problem is equivalent to a nonlinear programming problem by introducing p auxiliary variables, and the objective function of the nonlinear programming problem is the sum of the product. At the same time, p new nonlinear equality constraints are added to the original problem. By constructing convex and concave envelopes, the objective function and constraint conditions of the equivalent problem are reduced linearly to form a lower bound linear relaxation programming problem of the original problem. A branch and bound algorithm based on solving the linear programming problem is proposed, and the convergence of the algorithm is proved. Finally, the numerical results show that the proposed algorithm is feasible and effective.

MR(2010)主题分类: 

()
[1] Schaible S. Fractionalprogramming[M]. Collection:Handbook of Global Optimization, 1995, 495-608.

[2] Konno H, Inori M. Bond Portfolio Optimization by Bilinear Fractional Programming[J]. J. Oper. Res. Soc. Jpn., 1989, 32:143-158.

[3] Cploantoni C S, Manes R P, Whinston A. Programming, Profit Rates and Pricing Decisions[J]. Account. Rev., 1969, 44:467-481.

[4] Konno H, Yajima Y, Matsui T. Parametric simplex algorithms for solving a special class of nonconvex minimization problems[J]. J. Glob. Optim., 1991, 1(1):65-81.

[5] Falk J E, Palocsay S W. Image space analysis of generalized fractional programs[J]. J. Glob. Optim., 1994, 4(1):63-88.

[6] Jiao H W, Liu S Y. A practicable branch and bound algorithm for sum of linear ratios problem[J]. Eur. J. Oper. Res., 2015, 243(3):723-730.

[7] Shen P P, Wang C F. Global optimization for sum of linear ratios problem with coefficients[J]. Appl. Math. Comput., 2006, 176(1):219-229.

[8] Wang C F, Shen P P. A global optimization algorithm for linear fractional programming[J]. Appl. Math. Comput., 2008, 204(1):281-287.

[9] Gao Y, Jin S. A global optimization algorithm for sum of linear ratios problem[J]. J. Appl. Math., 2013, 2013(3):785-790.

[10] Ji Y, Zhang K C, Qu S J. A deterministic global optimization algorithm[J]. ppl. Math. Comput., 2013, 12(22):382-387.

[11] Shi Y. Global optimization for sum of ratios problems[D]. Dissertation of master degree for Henan Normal University, 2011.

[12] Nguyen T H P, Tuy H. A Unified Monotonic Approach to Generalized Linear Fractional Programming[J]. J. Glob. Optim., 2003, 26(3):229-259.

[13] Shen P P, Lu T. Regional division and reduction algorithm for minimizing the sum of linear fractional functions[J]. J. Inequal. Appl., 2018, 2018(1):63.

[14] Jiao H, Liu S, Yin J, et al. Outcome space range reduction method for global optimization of sum of affine ratios problem[J]. Open Math., 2016, 14(1):736-746.

[15] Shen P P, Zhang T, Wang C F. Solving a class of generalized fractional programming problems using the feasibility of linear programs[J]. J. Inequal. Appl., 2017, 2017(1):147.

[16] 胡勇文, 陈国华, 孟凡净. 低维线性分式规划的高效全局优化算法[J]. 科技广场, 2017, (1).

[17] Locatelli M. Approximation algorithm for a class of global optimization problems. J. Glob. Optim., 2013, 55:13-25.

[18] Depetrini D, Locatelli M. Approximation of linear fractional-multiplicative problems[J]. Math. Program., 2011, 128(1-2):437-443.

[19] Mccormick G P. Computability of global solutions to factorable nonconvex programs:Part I Convex underestimating problems[J]. Math. Program., 1976, 10(1):147-175.

[20] Sahinidis N. BARON user manual v.17.8.9[EB/OL].[2019-4-27]. http://minlp.com.
[1] 高岳林, 井霞. 一类线性乘积规划问题的分支定界缩减方法[J]. 计算数学, 2013, 35(1): 89-98.
[2] 高岳林, 魏飞. 一类非负二次整数规划问题的分支定界缩减方法[J]. 计算数学, 2011, 33(3): 233-248.
[3] 高岳林, 李会荣. 非线性约束优化问题的混合粒子群算法[J]. 计算数学, 2010, 32(2): 135-146.
[4] 彭拯,邬冬华,田蔚文,. 约束全局最优化的水平值估计算法[J]. 计算数学, 2007, 29(3): 293-304.
阅读次数
全文


摘要