Strong Duality for a Trust-Region Type Relaxation of the
Quadratic Assignment Problem
Kurt Anstreicher, Xin Chen, Henry Wolkowicz, Ya-Xiang Yuan
Lagrangian duality underlies many efficient algorithms for convex
minimization problems. A key ingredient is strong duality. Lagrangian
relaxation also provides lower bounds for nonconvex problems, where
the quality of the lower bound depends on the duality gap.
Quadratically constrained quadratic programs (QQPs) 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 duality results already
fail for the two trust region subproblem.
Surprisingly, there are classes of more complex, nonconvex QQPs where
strong duality holds. One example is the special case of
orthogonality constraints, which arise naturally in relaxations for
the quadratic assignment problem (QAP). In this paper we show that
strong duality also holds for a relaxation of QAP where the
orthogonality constraint is replaced by a semidefinite inequality
constraint. Using this strong duality result, and semidefinite
duality, we develop new trust-region type necessary and sufficient
optimality conditions for these problems. Our proof of strong duality
introduces and uses a generalization of the Hoffman-Wielandt
inequality.
Research Report CORR 98-31
University of Waterloo
Department of Combinatorics and Optimization
Waterloo, Ontario N2L 3G1, Canada
Contact:
[email protected]