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

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

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