A spectral bundle method with bounds
A spectral bundle method with bounds
复制标题
DOI：
10.1007/s101070100270
复制
发表时间：
2002-12
影响因子：
2.7
通讯作者：
中科院分区：
文献类型：
--
作者：
二次0-1规划或图划分问题的半定松弛是众所周知的高质量问题。然而，即使对于中等规模的问题，用原始对偶内点方法求解它们也需要花费很多时间。Helmberg和Rendl最近的谱束方法可以非常有效地解决大型结构等式约束半定规划，如果原始矩阵变量的迹是固定的，就像在许多应用中发生的那样。我们扩展的方法，使它可以处理不等式约束，而不会严重增加计算时间。此外，我们引入不精确的空步骤。这消除了计算次梯度的精确特征向量的需要，这在理论和实践中带来了沿着显著的优点。令人鼓舞的初步计算结果的报告。
Semidefinite relaxations of quadratic 0-1 programming or graph partitioning problems are well known to be of high quality. However, solving them by primal-dual interior point methods can take much time even for problems of moderate size. The recent spectral bundle method of Helmberg and Rendl can solve quite efficiently large structured equality-constrained semidefinite programs if the trace of the primal matrix variable is fixed, as happens in many applications. We extend the method so that it can handle inequality constraints without seriously increasing computation time. In addition, we introduce inexact null steps. This abolishes the need of computing exact eigenvectors for subgradients, which brings along significant advantages in theory and in practice. Encouraging preliminary computational results are reported.