| 线性两比式和的全局优化新算法 |
| |
| 引用本文： | 夏勇,王龙飞.线性两比式和的全局优化新算法[J].河南师范大学学报(自然科学版),2018(1). |
| |
| 作者姓名： | 夏勇 王龙飞 |
| |
| 作者单位： | 北京航空航天大学数学与系统科学学院; |
| |
| 摘 要： | 对线性两比式和这一非凸NP-困难的优化问题提出新的全局优化算法.首先把原问题等价地转化为一维参数优化问题.设计了巧妙的下界估计方法,在此基础上提出相应的分支定界算法,该算法最坏情况下可需要O(1/ε)迭代步以求得ε-近似全局最优解.数值结果表明,提出的新算法优于商业软件包BARON.此外,针对线性两比式和问题的一个具有隐凸性(等价于一个二阶锥规划)的应用特例,分支定界算法比基于CVX平台调用SDPT3求解相应的二阶锥规划等价模型效率更高.
|
| 关 键 词： | 线性比式和 线性规划 分支定界 对偶 二阶锥规划 |
A new global optimization algorithm for minimizing the sum of two linear ratios |
| |
| Institution: | ,School of Mathematics and Systems Science,Beihang University |
| |
| Abstract: | 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 SDPT3 for solving(SOCP). |
| |
| Keywords: | sum-of-linear-ratios global optimization branch and bound duality second-order cone programming |
| 本文献已被 CNKI 等数据库收录！ |
|
