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

摘要：

对线性两比式和这一非凸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).

作者：

夏勇 王龙飞

Xia Yong;Wang Longfei(School of Mathematics and Systems Science,Beihang University,Beijing 100191,China)

机构地区：

北京航空航天大学数学与系统科学学院

出处：

《betway官方app 学报：自然科学版》 CAS 北大核心 2018年第1期9-15,共7页

基金：

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

关键词：

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

sum of linear-ratios global optimization branch and bound duality second order cone programming

分类号：

O221.2 [理学—运筹学与控制论]

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