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

doi:10.12286/jssx.2020.2.207

计算数学 ›› 2020, Vol. 42 ›› Issue (2): 207-222.DOI: 10.12286/jssx.2020.2.207

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

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

1. 北方民族大学数学与信息科学学院, 银川 750021;
2. 宁夏科学计算与智能信息处理协同创新中心, 银川 750021;
3. 宁夏大学数学统计学院, 银川 750021

收稿日期:2018-07-25 出版日期:2020-05-15 发布日期:2020-05-15
基金资助:
国家自然科学基金（11961001），宁夏高等教育一流学科建设资助项目（NXYLXK2017B09），北方民族大学重大专项（ZDZX201901）资助.

PDF ( 250 ) 引用被引次数 ( 1 )

高岳林, 张博. 线性比式和规划问题的输出空间分支定界算法[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 YueLin^1,2, Zhang Bo^2,3

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.

Key words: Global Optimization, sum-of-linear-ratios Programming problem, Branch and Bound, Convex (concave) envelope, Outcome-Space

MR(2010)主题分类:

90C30

分享此文:

[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]. 计算数学, 2022, 44(2): 233-256.
[2]	高岳林, 井霞. 一类线性乘积规划问题的分支定界缩减方法[J]. 计算数学, 2013, 35(1): 89-98.
[3]	高岳林, 魏飞. 一类非负二次整数规划问题的分支定界缩减方法[J]. 计算数学, 2011, 33(3): 233-248.
[4]	高岳林, 李会荣. 非线性约束优化问题的混合粒子群算法[J]. 计算数学, 2010, 32(2): 135-146.
[5]	彭拯,邬冬华,田蔚文,. 约束全局最优化的水平值估计算法[J]. 计算数学, 2007, 29(3): 293-304.

阅读次数

全文

摘要

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

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

扫码分享