论文标题
在布尔二次问题的半决赛放松中增强低级解决方案
Enhancing low-rank solutions in semidefinite relaxations of Boolean quadratic problems
论文作者
论文摘要
布尔二次优化问题发生在许多应用中。它们混合的整体连续性质是具有挑战性的，因为它本质上是NP固有的。为了进行这种动机，在文献中提出了半决赛编程松弛（SDR）来近似解决方案，从而将问题重新验证为凸优化。但是，SDR不能保证提取正确的二进制最小化器。在本文中，我们提出了一种增强二元溶液恢复的新方法。提出的方法的关键是开发有关所需解决方案特征值的已知信息。随着提出的方法产生非凸面程序，我们开发和分析了迭代下降策略，其实际有效性通过数值结果显示。
Boolean quadratic optimization problems occur in a number of applications. Their mixed integer-continuous nature is challenging, since it is inherently NP-hard. For this motivation, semidefinite programming relaxations (SDR's) are proposed in the literature to approximate the solution, which recasts the problem into convex optimization. Nevertheless, SDR's do not guarantee the extraction of the correct binary minimizer. In this paper, we present a novel approach to enhance the binary solution recovery. The key of the proposed method is the exploitation of known information on the eigenvalues of the desired solution. As the proposed approach yields a non-convex program, we develop and analyze an iterative descent strategy, whose practical effectiveness is shown via numerical results.
