On Lagrangian Relaxation of Quadratic Matrix Constraints
On Lagrangian Relaxation of Quadratic Matrix Constraints
复制标题
DOI：
10.1137/s0895479898340299
复制
发表时间：
2000-04
期刊：
影响因子：
--
通讯作者：
K. Anstreicher;Henry Wolkowicz
中科院分区：
文献类型：
--
作者：
K. Anstreicher;Henry Wolkowicz
二次约束二次规划（QQPs）在许多不同的问题中起着重要的建模作用。这些问题一般都是NP困难和数值难以处理的。拉格朗日松弛通常为这些难题提供很好的近似解。这样的松弛等价于半定规划松弛。对于QQP的几种特殊情况，如凸规划和信赖域子问题，拉格朗日松弛给出了精确的最优值，即对偶间隙为零。然而，对于一般的QQP，甚至具有两个凸约束的QQP，而是一个非凸目标，都不是这样。本文考虑了一类特定的QQP，其中二次约束对应于矩阵正交性条件XXT= 1。对于这个问题，我们证明了基于放宽约束XXT=I和看似冗余的约束XT X=I的拉格朗日对偶具有零对偶间隙。这个结果在二次分配和图划分问题，以及最小化矩阵最大特征值的加权和问题上有很好的应用。我们还证明了二次矩阵约束的松弛技术可以用来得到最大切问题的强化半定松弛。
Quadratically constrained quadratic programs (QQPs) play an important modeling role for many diverse problems. These problems are in general NP hard and numerically intractable. Lagrangian relaxations often provide good approximate solutions to these hard problems. Such relaxations are equivalent to semidefinite programming relaxations. For several special cases of QQP, e.g., convex programs and trust region subproblems, the Lagrangian relaxation provides the exact optimal value, i.e., there is a zero duality gap. However, this is not true for the general QQP, or even the QQP with two convex constraints, but a nonconvex objective. In this paper we consider a certain QQP where the quadratic constraints correspond to the matrix orthogonality condition XXT=I. For this problem we show that the Lagrangian dual based on relaxing the constraints XXT=I and the seemingly redundant constraints XT X=I has a zero duality gap. This result has natural applications to quadratic assignment and graph partitioning problems, as well as the problem of minimizing the weighted sum of the largest eigenvalues of a matrix. We also show that the technique of relaxing quadratic matrix constraints can be used to obtain a strengthened semidefinite relaxation for the max-cut problem.