##
On Lagrangian Relaxation of Quadratic Matrix Constraints

###
Kurt Anstreicher and Henry Wolkowicz

Quadratically constrained quadratic programs (QQP)
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 $X\tran X=I$. For this
problem we show that the Lagrangian dual based on relaxing the constraints
$X\tran X=I$, {\em and} the seemingly redundant constraints $X\tran 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.
Research Report CORR 98-24
University of Waterloo
Department of Combinatorics and Optimization
Waterloo, Ontario N2L 3G1, Canada

Contact:
hwolkowi@orion.math.uwaterloo.ca