Convex hull of the orthogonal similarity set with applications in quadratic assignment problems

Yong Xia

doi:10.3934/jimo.2013.9.689

Article Contents

2013, Volume 9, Issue 3: 689-701. Doi: 10.3934/jimo.2013.9.689

This issue Previous Article Stable strong and total parametrized dualities for DC optimization problems in locally convex spaces Next Article Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming

Convex hull of the orthogonal similarity set with applications in quadratic assignment problems

Yong Xia^1,

1.
State Key Laboratory of Software Development Environment, LMIB of the Ministry of Education, School of Mathematics and System Sciences, Beihang University, Beijing, 100191

Received: August 2012

Revised: November 2012

Published: July 2013

Abstract Related Papers Cited by

Abstract

In this paper, we study thoroughly the convex hull of the orthogonal similarity set and give a new representation. When applied in quadratic assignment problems, it motivates two new lower bounds. The first is equivalent to the projected eigenvalue bound, while the second highly outperforms several well-known lower bounds in literature.

Keywords:

Mathematics Subject Classification: Primary: 90C27; Secondary: 90C22.

Citation:

Related Papers

Cited by

References

[1]	K. M. Anstreicher and H. Wolkowicz, On lagrangian relaxation of quadratic matrix constraints, SIAM J. Matrix Anal. Appl., 22 (2000), 41-55.doi: 10.1137/S0895479898340299.
[2]	K. M. Anstreicher, Eigenvalue bounds versus semidefinite relaxations for the quadratic assignment problem, SIAM Journal on Optimization, 11 (2001), 254-265.doi: 10.1137/S1052623499354904.
[3]	K. M. Anstreicher and N. W. Brixius, A new bound for the quadratic assignment problem based on convex quadratic programming, Mathematical Programming Ser. A, 89 (2001), 341-357.doi: 10.1007/PL00011402.
[4]	K. M. Anstreicher, Recent advances in the solution of quadratic assignment Problems, Mathematical Programming Ser. B, 97 (2003), 24-42.
[5]	R. E. Burkard, Locations with spatial interactions: The quadratic assignment problem, in "Discrete Location Theory" (eds. P. B.Mirchandani and R. L.Francis), Wiley, New York, (1991), 387-437.
[6]	R. E. Burkard, E. Çela, P. M. Pardalos and L. S. Pitsoulis, The quadratic assignment Problem, in "Handbook of Combinatorial Optimization" (eds. D.-Z. Du and P. M. Pardalos), 3, Kluwer, (1998), 241-337.
[7]	E. Çela, "The Quadratic Assignment Problem: Theory and Algorithms," Kluwer Academic Publishers, Dordrecht, 1998.
[8]	Y. Ding and H. Wolkowicz, A low-dimensional semidefinite relaxation for the quadratic assignment problem, Mathematics of Operations Research, 34 (2009), 1008-1022.doi: 10.1287/moor.1090.0419.
[9]	C. S. Edwards, The derivation of a greedy approximator for the Koopmans-Beckmann quadratic assignment problem, Proceedings of the 77-th Combinatorial Programming Conference (CP77) (1977), 55-86.
[10]	C. S. Edwards, A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem, Mathematical Programming Study, 13 (1980), 35-52.
[11]	P. A. Fillmore and J. P. Williams, Some convexity theorems for matrices, Glasgow Math. J., 12 (1971), 110-117.doi: 10.1017/S0017089500001221.
[12]	G. Finke, R. E. Burkard and F. Rendl, Quadratic assignment problems, Ann. Discrete Math., 31 (1987), 61-82.doi: 10.1016/S0304-0208(08)73232-8.
[13]	M. Grant and S. Boyd, "{CVX}: {Matlab} Software for Disciplined Convex Programming," http://cvxr.com/cvx. version 1. 21 (2010)
[14]	S. W. Hadley, F. Rendl and H. Wolkowicz, A new lower bound via projection for the quadratic assignment problem, Math. Oper. Res., 17 (1992), 727-739.doi: 10.1287/moor.17.3.727.
[15]	G. G. Hardy, J. E. Littlewood and G. Pólya, "Inequalities," Cambridge University Press, London and New York, 1952.
[16]	E. M. Loiola, N. M. M. Abreu, P. O. Boaventura-Netto, P. Hahn and T. Querido, A survey for the quadratic assignment problem, European Journal of Operational Research, 176 (2007), 657-690.doi: 10.1016/j.ejor.2005.09.032.
[17]	A. W. Marshall and I. Olkin, "Inequalities: Theory of Majorization and its Application," Academic Press, New York, NY, 1979.
[18]	M. L. Overton and R. S. Womersley, On the sum of the largest eigenvalues of a symmetric matrix, SIAM J. Matrix Anal. Appl., 13 (1992), 41-45.doi: 10.1137/0613006.
[19]	P. M. Pardalos, F. Rendl and H. Wolkowicz, The Quadratic Assignment Problem: A Survey and Recent Developments, in "Quadratic Assignment and Related Problems" (eds. P. M. Pardalos and H. Wolkowicz), 16 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science,AMS. 16 (1994), 1-42.
[20]	S. Sahni and T. Gonzalez, P-complete approximation problems, Journal of the Association of Computing Machinery, 23 (1976), 555-565.doi: 10.1145/321958.321975.
[21]	Y. Xia, Second order cone programming relaxation for quadratic assignment problems, Optimization Methods $&$ Software, 23 (2008), 441-449.doi: 10.1080/10556780701843405.
[22]	Y. Xia, New sufficient global optimality conditions for linearly constrained bivalent quadratic optimization problem, Journal of Industrial and Management Optimization, 5 (2009), 881-892.doi: 10.3934/jimo.2009.5.881.
[23]	Y. Xia, Convex hull presentation of a quadratically constrained set and its application in solving quadratic programming problems, Asia-Pacific Journal of Operational Research, 26 (2009), 769-778.doi: 10.1142/S0217595909002468.