Strong duality for a trust-region type relaxation of the quadratic assignment problem

Citation
K. Anstreicher et al., Strong duality for a trust-region type relaxation of the quadratic assignment problem, LIN ALG APP, 301(1-3), 1999, pp. 121-136
Citations number
36
Categorie Soggetti
Mathematics
Journal title
LINEAR ALGEBRA AND ITS APPLICATIONS
ISSN journal
00243795 → ACNP
Volume
301
Issue
1-3
Year of publication
1999
Pages
121 - 136
Database
ISI
SICI code
0024-3795(19991101)301:1-3<121:SDFATT>2.0.ZU;2-B
Abstract
Lagrangian duality underlies many efficient algorithms for convex minimizat ion problems. A key ingredient is strong duality. Lagrangian relaxation als o provides lower bounds for non-convex problems, where the quality of the l ower bound depends on the duality gap. Quadratically constrained quadratic programs (QQPs) provide important examples of non-convex programs. For the simple case of one quadratic constraint (the trust-region subproblem) stron g duality holds. In addition, necessary and sufficient (strengthened) secon d-order optimality conditions exist. However, these duality results already fail for the two trust-region subproblem. Surprisingly, there are classes of more complex, non-convex QQPs where strong duality holds. One example is the special case of orthogonality constraints, which arise naturally in re laxations for the quadratic assignment problem (QAP). In this paper we show that strong duality also holds for a relaxation of QAP where the orthogona lity 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 proble ms. Our proof of strong duality introduces and uses a generalization of the Hoffman-Wielandt inequality. (C) 1999 Published by Elsevier Science Inc. A ll rights reserved.