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

Kurt Anstreicher, Xin Chen, Henry Wolkowicz, Ya Xiang Yuan

Research output: Contribution to journalArticlepeer-review

Abstract

Lagrangian duality underlies many efficient algorithms for convex minimization problems. A key ingredient is strong duality. Lagrangian relaxation also provides lower bounds for non-convex problems, where the quality of the lower 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) 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 sub-problem. 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 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.

Original languageEnglish (US)
Pages (from-to)121-136
Number of pages16
JournalLinear Algebra and Its Applications
Volume301
Issue number1-3
DOIs
StatePublished - Nov 1 1999
Externally publishedYes

Keywords

  • Lagrangian relaxations
  • Quadratic assignment problem
  • Quadratically constrained quadratic programs
  • Semidefinite programming

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Strong duality for a trust-region type relaxation of the quadratic assignment problem'. Together they form a unique fingerprint.

Cite this