title:
Is Lagrangian (SDP) Relaxation Best for Quadratically constrained
Quadratic Programs


abstract:
Lagrangian duality lies behind efficient algorithms for convex
minimization problems.
Lagrangian relaxation provides lower bounds for 
nonconvex problems, where the quality of the lower bound depends on
the duality gap.
For quadratically constrained quadratic programs, the dual of
the Lagrangian dual is equivalent to the semidefinite
relaxation. Thus, the Lagrangian relaxation can be efficiently
computed using primal-dual interior-point methods for the SDP
relaxation.

Quadratically constrained quadratic programs (QQP) provide important
examples of nonconvex programs. For the simple case of one
quadratic constraint (the trust region subproblem) strong duality
holds. In addition, necessary and sufficient (strengthened)
second order optimality conditions exist. 
However, these nice duality results already fail for the 
two trust region subproblem. 
However, the Lagrangian relaxation provides excellent bounds for many
QQPs, e.g. max-cut, graph partitioning, and quadratic assignment
problems.

Surprisingly, there are classes of nonconvex
QQPs where strong duality holds.  This includes the special cases
of orthogonality type constraints.
For these problems we first show that strong duality holds and that
the trust region type necessary and sufficient optimality
conditions hold. This also provides an extension of the
Hoffman-Wielandt inequality.