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

Kurt Anstreicher; Xin Chen; Henry Wolkowicz; Ya-Xiang Yuan

doi:10.1016/S0024-3795(99)00205-0

Back

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

Journal article

Open access

Peer reviewed

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

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

Linear algebra and its applications, Vol.301(1), pp.121-136

11/01/1999

DOI: 10.1016/S0024-3795(99)00205-0

Files and links (1)

url

https://doi.org/10.1016/s0024-3795(99)00205-0View

Published (Version of record) Open Access

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.

49M40

52A41

90C20

90C27

Lagrangian relaxations

Quadratic assignment problem

Quadratically constrained quadratic programs

Semidefinite programming

Details

Title: Subtitle: Strong duality for a trust-region type relaxation of the quadratic assignment problem
Creators: Kurt Anstreicher - University of Iowa
Xin Chen - Operations Research Center, MIT, 77 Mass Ave, Bldg E40-194,ctyCambridge, MA 02139 UK
Henry Wolkowicz - University of Waterloo
Ya-Xiang Yuan - Institute of Computing Technology
Resource Type: Journal article
Publication Details: Linear algebra and its applications, Vol.301(1), pp.121-136
DOI: 10.1016/S0024-3795(99)00205-0
ISSN: 0024-3795
eISSN: 1873-1856
Publisher: Elsevier Inc
Language: English
Date published: 11/01/1999
Academic Unit: Industrial and Systems Engineering; Computer Science; Business Analytics
Record Identifier: 9984380460202771

Metrics

5 Record Views

21 Times Cited - Web of Science