American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming
  • JIMO Home
  • This Issue
  • Next Article
    Stable strong and total parametrized dualities for DC optimization problems in locally convex spaces
July  2013, 9(3): 689-701. doi: 10.3934/jimo.2013.9.689

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, China

Received  August 2012 Revised  November 2012 Published  April 2013

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: semidefinite programming., Orthogonal similarity, quadratic assignment problem, convex hull, lower bound.
Mathematics Subject Classification: Primary: 90C27; Secondary: 90C2.
Citation: Yong Xia. Convex hull of the orthogonal similarity set with applications in quadratic assignment problems. Journal of Industrial & Management Optimization, 2013, 9 (3) : 689-701. doi: 10.3934/jimo.2013.9.689
References:
[1]

K. M. Anstreicher and H. Wolkowicz, On lagrangian relaxation of quadratic matrix constraints,, SIAM J. Matrix Anal. Appl., 22 (2000), 41.  doi: 10.1137/S0895479898340299.  Google Scholar

[2]

K. M. Anstreicher, Eigenvalue bounds versus semidefinite relaxations for the quadratic assignment problem,, SIAM Journal on Optimization, 11 (2001), 254.  doi: 10.1137/S1052623499354904.  Google Scholar

[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.  doi: 10.1007/PL00011402.  Google Scholar

[4]

K. M. Anstreicher, Recent advances in the solution of quadratic assignment Problems,, Mathematical Programming Ser. B, 97 (2003), 24.   Google Scholar

[5]

R. E. Burkard, Locations with spatial interactions: The quadratic assignment problem,, in, (1991), 387.   Google Scholar

[6]

R. E. Burkard, E. Çela, P. M. Pardalos and L. S. Pitsoulis, The quadratic assignment Problem,, in, 3 (1998), 241.   Google Scholar

[7]

E. Çela, "The Quadratic Assignment Problem: Theory and Algorithms,", Kluwer Academic Publishers, (1998).   Google Scholar

[8]

Y. Ding and H. Wolkowicz, A low-dimensional semidefinite relaxation for the quadratic assignment problem,, Mathematics of Operations Research, 34 (2009), 1008.  doi: 10.1287/moor.1090.0419.  Google Scholar

[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), (1977), 55.   Google Scholar

[10]

C. S. Edwards, A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem,, Mathematical Programming Study, 13 (1980), 35.   Google Scholar

[11]

P. A. Fillmore and J. P. Williams, Some convexity theorems for matrices,, Glasgow Math. J., 12 (1971), 110.  doi: 10.1017/S0017089500001221.  Google Scholar

[12]

G. Finke, R. E. Burkard and F. Rendl, Quadratic assignment problems,, Ann. Discrete Math., 31 (1987), 61.  doi: 10.1016/S0304-0208(08)73232-8.  Google Scholar

[13]

M. Grant and S. Boyd, "{CVX}: {Matlab} Software for Disciplined Convex Programming,", , (2010).   Google Scholar

[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.  doi: 10.1287/moor.17.3.727.  Google Scholar

[15]

G. G. Hardy, J. E. Littlewood and G. Pólya, "Inequalities,", Cambridge University Press, (1952).   Google Scholar

[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.  doi: 10.1016/j.ejor.2005.09.032.  Google Scholar

[17]

A. W. Marshall and I. Olkin, "Inequalities: Theory of Majorization and its Application,", Academic Press, (1979).   Google Scholar

[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.  doi: 10.1137/0613006.  Google Scholar

[19]

P. M. Pardalos, F. Rendl and H. Wolkowicz, The Quadratic Assignment Problem: A Survey and Recent Developments,, in, 16 (1994), 1.   Google Scholar

[20]

S. Sahni and T. Gonzalez, P-complete approximation problems,, Journal of the Association of Computing Machinery, 23 (1976), 555.  doi: 10.1145/321958.321975.  Google Scholar

[21]

Y. Xia, Second order cone programming relaxation for quadratic assignment problems,, Optimization Methods $&$ Software, 23 (2008), 441.  doi: 10.1080/10556780701843405.  Google Scholar

[22]

Y. Xia, New sufficient global optimality conditions for linearly constrained bivalent quadratic optimization problem,, Journal of Industrial and Management Optimization, 5 (2009), 881.  doi: 10.3934/jimo.2009.5.881.  Google Scholar

[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.  doi: 10.1142/S0217595909002468.  Google Scholar

show all references

References:
[1]

K. M. Anstreicher and H. Wolkowicz, On lagrangian relaxation of quadratic matrix constraints,, SIAM J. Matrix Anal. Appl., 22 (2000), 41.  doi: 10.1137/S0895479898340299.  Google Scholar

[2]

K. M. Anstreicher, Eigenvalue bounds versus semidefinite relaxations for the quadratic assignment problem,, SIAM Journal on Optimization, 11 (2001), 254.  doi: 10.1137/S1052623499354904.  Google Scholar

[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.  doi: 10.1007/PL00011402.  Google Scholar

[4]

K. M. Anstreicher, Recent advances in the solution of quadratic assignment Problems,, Mathematical Programming Ser. B, 97 (2003), 24.   Google Scholar

[5]

R. E. Burkard, Locations with spatial interactions: The quadratic assignment problem,, in, (1991), 387.   Google Scholar

[6]

R. E. Burkard, E. Çela, P. M. Pardalos and L. S. Pitsoulis, The quadratic assignment Problem,, in, 3 (1998), 241.   Google Scholar

[7]

E. Çela, "The Quadratic Assignment Problem: Theory and Algorithms,", Kluwer Academic Publishers, (1998).   Google Scholar

[8]

Y. Ding and H. Wolkowicz, A low-dimensional semidefinite relaxation for the quadratic assignment problem,, Mathematics of Operations Research, 34 (2009), 1008.  doi: 10.1287/moor.1090.0419.  Google Scholar

[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), (1977), 55.   Google Scholar

[10]

C. S. Edwards, A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem,, Mathematical Programming Study, 13 (1980), 35.   Google Scholar

[11]

P. A. Fillmore and J. P. Williams, Some convexity theorems for matrices,, Glasgow Math. J., 12 (1971), 110.  doi: 10.1017/S0017089500001221.  Google Scholar

[12]

G. Finke, R. E. Burkard and F. Rendl, Quadratic assignment problems,, Ann. Discrete Math., 31 (1987), 61.  doi: 10.1016/S0304-0208(08)73232-8.  Google Scholar

[13]

M. Grant and S. Boyd, "{CVX}: {Matlab} Software for Disciplined Convex Programming,", , (2010).   Google Scholar

[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.  doi: 10.1287/moor.17.3.727.  Google Scholar

[15]

G. G. Hardy, J. E. Littlewood and G. Pólya, "Inequalities,", Cambridge University Press, (1952).   Google Scholar

[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.  doi: 10.1016/j.ejor.2005.09.032.  Google Scholar

[17]

A. W. Marshall and I. Olkin, "Inequalities: Theory of Majorization and its Application,", Academic Press, (1979).   Google Scholar

[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.  doi: 10.1137/0613006.  Google Scholar

[19]

P. M. Pardalos, F. Rendl and H. Wolkowicz, The Quadratic Assignment Problem: A Survey and Recent Developments,, in, 16 (1994), 1.   Google Scholar

[20]

S. Sahni and T. Gonzalez, P-complete approximation problems,, Journal of the Association of Computing Machinery, 23 (1976), 555.  doi: 10.1145/321958.321975.  Google Scholar

[21]

Y. Xia, Second order cone programming relaxation for quadratic assignment problems,, Optimization Methods $&$ Software, 23 (2008), 441.  doi: 10.1080/10556780701843405.  Google Scholar

[22]

Y. Xia, New sufficient global optimality conditions for linearly constrained bivalent quadratic optimization problem,, Journal of Industrial and Management Optimization, 5 (2009), 881.  doi: 10.3934/jimo.2009.5.881.  Google Scholar

[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.  doi: 10.1142/S0217595909002468.  Google Scholar

[1]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002
[2]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141
[3]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881
[4]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[5]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[6]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[7]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[8]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[9]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378
[10]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401
[11]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[12]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261
[13]

Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090
[14]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (133)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences