论文部分内容阅读
众所周知，寻找非凸二次规划的全局解是一类NP-hard问题。一个非凸二次规划可能包含许多个局部解，并且在很多情况下，局部解与全局解相差很大。目前使用较多的寻找全局解的方法是分枝定界方法。KKT分枝是目前最好的分枝方法；而定界的方法，一般是通过引入一些额外的变量，把这个问题移到一个更高维的空间中去求解。这样做的缺点是使所得到的松弛问题的维数显著增加，而使用投影技术构造的低维松弛却可以弥补这个缺点。正是基于KKT分枝和用于定界的低维投影松弛在实际中的好的表现，本文构造了盒约束非凸二次规划问题的分支一切割算法，并应用此算法求解了一些随机产生的问题。数值结果表明本文算法是有效的。