使用凸二次规划求解0-1二次程序的精确解法

"这篇论文是关于使用凸二次规划方法求解精确0-1二次规划问题的。作者包括Alain Billionnet、Sourour Elloumi和Marie-Christine Plateau，发表于2005年6月10日。0-1二次规划问题是一种在满足线性约束条件下，最小化二次函数的问题。本文提出了一种通用方法，通过将问题重新形式化为具有凸二次目标函数的等价0-1规划，然后利用标准的混合整数二次规划求解器来解决。这种方法在某种意义上是最优的，它利用了原始问题的等式约束，并需要求解半定规划问题。论文还展示了将该方法应用于稠密子图问题上的实验结果，结果显示对于这类问题，这种方法具有良好的性能。" 这篇论文详细探讨了如何利用凸二次规划（Convex Quadratic Programming, CQP）来精确求解0-1二次规划问题（0-1 Quadratic Programming, QP）。在0-1二次规划中，目标是寻找0或1变量的组合，以最小化一个二次函数，同时满足一系列线性约束。这类问题在组合优化、运筹学和机器学习等领域中有广泛的应用。 作者提出的解决方案包括两个主要步骤：首先，他们将原始的非凸0-1 QP问题转换为一个等价的0-1规划问题，其目标函数是凸的。这种转化过程依赖于问题的等式约束，并可能涉及到半定规划（Semidefinite Programming, SDP）的求解，这是一种复杂但更易于处理的优化问题类型，能保证找到全局最优解。其次，他们利用现有的混合整数二次规划（Mixed Integer Quadratic Programming, MIQP）求解器来找到这个凸问题的解。 在实际应用中，他们选择了稠密子图问题（Densest k-Subgraph Problem）作为案例研究，这是一个典型的NP难问题，寻找给定图中顶点数为k的最稠密子图。实验结果证明了所提方法的有效性，尤其是在解决这类问题时，能够提供精确的解决方案。 总体来说，这项工作为解决非凸优化问题提供了一个新的视角，特别是在处理0-1二次规划问题时，通过凸化技术将其转化为更容易求解的形式。这对于优化算法的设计和改进，以及在实际应用中的部署都具有重要的理论和实践意义。