摘要
对线性两比式和这一非凸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)
出处
《河南师范大学学报（自然科学版）》
CAS
北大核心
2018年第1期9-15,共7页
Journal of Henan Normal University(Natural Science Edition)
基金
国家自然科学基金(11571029
11471325
11771056)
关键词
线性比式和
线性规划
分支定界
对偶
二阶锥规划
sum of linear-ratios
global optimization
branch and bound
duality
second order cone programming
