一类多乘积规划问题的对偶界方法

On the Global Optimization for a Class of Sum of Convex-Convex Ratios Problem

针对一类目标函数和约束函数都是多乘积的规划问题给出一种求其全局最优解的分支定界算法.该算法利用Lagrange对偶理论将其中关键的定界问题转化为一系列易于求解的线性规划,并且这些线性规划的规模固定不变,从而更容易应用到实际问题中.理论分析和数值算例表明提出的算法可行有效.

This paper presents a branch and duality bound algorithm for globally solving the sum of convex-convex ratios problem with nonconvex feasible region. The algorithm uses a branch and bound scheme where Lagrangian duality theory is used to obtain the lower bounds. As a result, the lowe-bounding subproblems during the algorithm search are all ordinary linear programs that can be solved very efficiently and that do not grow in size from iteration to iteration. Convergence of the algorithm is proved and some numerical experiments are given to show the feasibility of the proposed algorithm.