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

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

本文旨在针对线性比式和规划这一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.