×

zbMATH — the first resource for mathematics

Semidefinite approximations for quadratic programs over orthogonal matrices. (English) Zbl 1203.90121
Summary: Finding global optimum of a non-convex quadratic function is in general a very difficult task even when the feasible set is a polyhedron. We show that when the feasible set of a quadratic problem consists of orthogonal matrices from \({\mathbb{R}^{n\times k}}\) , then we can transform it into a semidefinite program in matrices of order \(kn\) which has the same optimal value. This opens new possibilities to get good lower bounds for several problems from combinatorial optimization, like the Graph partitioning problem (GPP), the Quadratic assignment problem (QAP) etc. In particular we show how to improve significantly the well-known Donath-Hoffman eigenvalue lower bound for GPP by semidefinite programming. In the last part of the paper we show that the copositive strengthening of the semidefinite lower bounds for GPP and QAP yields the exact values.

MSC:
90C20 Quadratic programming
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
90C27 Combinatorial optimization
Software:
QAPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anstreicher K.: Recent advances in the solution of quadratic assignment problems. Math. Program. B 97, 27–42 (2003) · Zbl 1035.90067
[2] Alpert C.J., Kahng A.B.: Recent directions in netlist partition: a survey. Integr. VLSI J. 19, 1–81 (1995) · Zbl 0876.94063 · doi:10.1016/0167-9260(95)00008-4
[3] Anstreicher K., Wolkowicz H.: On lagrangian relaxation of quadratic matrix constraints. SIAM J. Matrix Anal. Appl. 22, 41–55 (2000) · Zbl 0990.90088 · doi:10.1137/S0895479898340299
[4] Arora S., Karger D., Karpinski M.: Polynomial time approximation schemes for dense instances of NP-hard problems. J. Comput. Syst. Sci. 58(1), 193–210 (1999) · Zbl 0937.68160 · doi:10.1006/jcss.1998.1605
[5] Beck A.: Quadratic matrix programming. SIAM J. Optim. 17, 1224–1238 (2007) · Zbl 1136.90025 · doi:10.1137/05064816X
[6] Bomze I., Duer M., de Klerk E., Roos C., Quist A.J., Terlaky T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18, 301–320 (2000) · Zbl 0970.90057 · doi:10.1023/A:1026583532263
[7] Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program., published online on April 29th (2008) · Zbl 1180.90234
[8] Burer S., Vandenbussche D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16, 726–750 (2006) · Zbl 1113.90100 · doi:10.1137/040609574
[9] Burkard, R.E., Cela, E., Karisch, S.E., Rendl, F.: QAPLIB–a quadratic assignment problem library. Available at http://www.seas.upenn.edu/qaplib/ , July (2007) · Zbl 0729.90993
[10] de Klerk E., Pasechnik D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12, 875–892 (2002) · Zbl 1035.90058 · doi:10.1137/S1052623401383248
[11] de Klerk, E., Sotirov, R.: Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. To appear in Math. Program., available on http://www.springerlink.com/content/85302n245v250051/fulltext.pdf . · Zbl 1184.90120
[12] Donath W.E., Hoffman A.J.: Lower bounds for the partitioning of graphs. IBM J. Res. Dev. 17, 420–425 (1973) · Zbl 0259.05112 · doi:10.1147/rd.175.0420
[13] Falkner J., Rendl F., Wolkowicz H.: A computational study of graph partitioning. Math. Program. 66(2), 211–240 (1994) · Zbl 0830.90130 · doi:10.1007/BF01581147
[14] Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979) · Zbl 0411.68039
[15] Guttmann-Beck N., Hassin R.: Approximation algorithms for minimum K-cut. Algorithmica 27, 198–207 (2000) · Zbl 0951.68178 · doi:10.1007/s004530010013
[16] Helmberg C., Rendl F., Mohar B., Poljak S.: A spectral approach to bandwidth and separator problems in graphs. Linear Multilinear Algebra 39, 73–90 (1995) · Zbl 0832.05093 · doi:10.1080/03081089508818381
[17] Hoffman A.J., Wielandt H.W.: The variation of the spectrum of a normal matrix. Duke Math. J. 20, 37–39 (1953) · Zbl 0051.00903 · doi:10.1215/S0012-7094-53-02004-3
[18] Karisch, S.E., Rendl, F.: Semidefinite programming and graph equipartition. In: Topics in Semidefinite and Interior-point Methods, The Fields Institute for Research in Mathematical Sciences, vol. 18. Communications Series, American Mathematical Society, Providence, RI (1998) · Zbl 0905.90171
[19] Lisser A., Rendl F.: Graph partitioning using linear and semidefinite programming. Math. Program. 95(1), 91–101 (2003) · Zbl 1030.90079 · doi:10.1007/s10107-002-0342-x
[20] Motzkin T.S., Straus E.G.: Maxima for graphs and a new proof of a theorem of Túran. Can. J. Math. 17, 533–540 (1965) · Zbl 0129.39902 · doi:10.4153/CJM-1965-053-6
[21] Papadimitriou C.H., Steiglitz K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, Mineola, NY (1998) · Zbl 0944.90066
[22] Povh, J.: Application of semidefinite and copositive programming in combinatorial optimization. PhD Thesis, University of Ljubljana, Ljubljana (2006)
[23] Povh J., Rendl F.: A copositive programming approach to graph partitioning. SIAM J. Optim. 18, 223–241 (2007) · Zbl 1143.90025 · doi:10.1137/050637467
[24] Povh J., Rendl F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6, 231–241 (2009) · Zbl 1167.90597 · doi:10.1016/j.disopt.2009.01.002
[25] Rendl F., Sotirov R.: Bounds for the quadratic assignment problem using the bundle method. Math. Program. 109(2–3), 505–524 (2007) · Zbl 1278.90303 · doi:10.1007/s10107-006-0038-8
[26] Rendl F., Wolkowicz H.: A projection technique for partitioning the nodes of a graph. Ann. Oper. Res. 58, 155–179 (1995) · Zbl 0841.90120 · doi:10.1007/BF02032130
[27] Wolkowicz H., Zhao Q.: Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96–97, 461–479 (1999) · Zbl 0932.90030 · doi:10.1016/S0166-218X(99)00102-X
[28] Zhao Q., Karisch S.E., Rendl F., Wolkowicz H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2, 71–109 (1998) · Zbl 0904.90145 · doi:10.1023/A:1009795911987
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.