线性两比式和的全局优化新算法  

A new global optimization algorithm for minimizing the sum of two linear ratios

作　　者：夏勇[1] 王龙飞 Xia Yong;Wang Longfei(School of Mathematics and Systems Science,Beihang University,Beijing 100191,China)

机构地区：[1]北京航空航天大学数学与系统科学学院,北京100191

出　　处：《河南师范大学学报（自然科学版）》2018年第1期9-15,共7页Journal of Henan Normal University(Natural Science Edition)

基　　金：国家自然科学基金(11571029;11471325;11771056)

摘　　要：对线性两比式和这一非凸NP-困难的优化问题提出新的全局优化算法.首先把原问题等价地转化为一维参数优化问题.设计了巧妙的下界估计方法,在此基础上提出相应的分支定界算法,该算法最坏情况下可需要O(1/ε)迭代步以求得ε-近似全局最优解.数值结果表明,提出的新算法优于商业软件包BARON.此外,针对线性两比式和问题的一个具有隐凸性(等价于一个二阶锥规划)的应用特例,分支定界算法比基于CVX平台调用SDPT3求解相应的二阶锥规划等价模型效率更高.We propose a new global optimization algorithm for minimizing the sum of two linear ratios over a polytope(P),which is NP-hard.We first reformulate(P)as a univariate minimization problem.Based on a newly developed lower bounding approach,we propose an efficient branch-and-bound algorithm,which can find a globalε-approximation solution in at most O(1/ε)iterations.Numerical results show that our new algorithm highly outperforms the software BARON.Moreover,for a special case of(P)which has a second order cone programming reformulation(SOCP),our branch and bound algorithm even works much faster than calling SDPT3for solving(SOCP).

关 键 词：线性比式和 线性规划 分支定界 对偶 二阶锥规划 

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