Quadratically constrained quadratic programs (QQPs) play an important model
ing role for many diverse problems. These problems are in general NP hard a
nd numerically intractable. Lagrangian relaxations often provide good appro
ximate 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 su
bproblems, the Lagrangian relaxation provides the exact optimal value, i.e.
, there is a zero duality gap. However, this is not true for the general QQ
P, or even the QQP with two convex constraints, but a nonconvex objective.
In this paper we consider a certain QQP where the quadratic constraints cor
respond 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 (XX)-X-T = I has a zero duality gap. T
his result has natural applications to quadratic assignment and graph parti
tioning 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 rel
axing quadratic matrix constraints can be used to obtain a strengthened sem
idefinite relaxation for the max-cut problem.