A new global optimization algorithm for minimizing the sum of two linear ratios
- 分享到:
摘要：
对线性两比式和这一非凸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 [理学—运筹学与控制论]
