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

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

作　　者：张博 高岳林 Zhang Bo;Gao YueLin(School of Mathematics and Statistics,Ningxia University,Yinchuan 750021,China;School of mathematics and information science,North Minzu University,Ningxia,Yinchuan 750021,China;Ningxia province key laboratory of intelligent information and data processing,Ningxia,Yinchuan 750021,China)

机构地区：[1]宁夏大学数学统计学院,银川750021 [2]北方民族大学数学与信息科学学院,银川750021 [3]宁夏智能信息与大数据处理重点实验室,银川750021

出　　处：《计算数学》2022年第2期233-256,共24页Mathematica Numerica Sinica

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

摘　　要：基于对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.

关 键 词：全局优化 线性比式和问题 分枝定界 输出空间 计算复杂性 

分 类 号：O221[理学—运筹学与控制论]