A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming.

*(English)*Zbl 0843.90088Summary: We review various relaxations of \((0,1)\)-quadratic programming problems. These include semidefinite programs, parametric trust region problems and concave quadratic maximization. All relaxations that we consider lead to efficiency solvable problems. The main contributions of the paper are the following. Using Lagrangian duality, we prove equivalence of the relaxations in a unified and simple way. Some of these equivalences have been known previously, but our approach leads to short and transparent proofs. Moreover, we extend the approach to the case of equality constrained problems by taking the squared linear constraints into the objective function. We show how this technique can be applied to the Quadratic Assignment Problem, the Graph Partitioning Problem and the Max-Clique Problem. Finally, we show our relaxation to be best possible among all quadratic majorants with zero trace.

##### Keywords:

minmax eigenvalue problems; theta function; quadratic assignment; graph partitioning; max-clique problem; relaxations of \((0,1)\)-quadratic programming problems; semidefinite programs; parametric trust region problems; concave quadratic maximization; Lagrangian duality##### Software:

GQTPAR
Full Text:
DOI

##### References:

[1] | Adams, W. and Dealing, P.M. (1994), On the equivalence between roof duality and Lagrangian duality for unconstrained 0-1 quadratic programming problems.Discrete Appl. Math. 48:1-20. · Zbl 0794.90038 |

[2] | Alizadeh, F. (1992), Combinatorial optimization with semidefinite matrices. InProceedings of the Second Annual Integer Programming and Combinatorial Optimization Conference, CarnegieMellon University. |

[3] | Balas, E., Ceria, S., and Cornuejols, G. (1993), A lift-and-project cutting plane algorithm for mixed 0-1 programs.Mathematical Programming 58:295-324. · Zbl 0796.90041 |

[4] | Balas, E., Ceria, S., Cornuejols, G., and Pataki, G. (1994), Updated semidefinite constraints. Technical report, GSIA Carnegie Mellon University, Pittsburgh, PA, 1994. Personal communication. |

[5] | Bersekas, D.P. (1982),Constrained Optimization and Lagrange Multipliers. Academic Press, New York, NY. |

[6] | Delorme, C. and Poljak, S. (1993), Laplacian eigenvalues and the maximum cut problem.Math. Programming 62(3):557-574. · Zbl 0797.90107 |

[7] | Falkner, J., Rendl, F., Wolkowicz, H., and Zhao, Q., Semidefinite relaxations for the graph partitioning problem. Research report, University of Waterloo, Waterloo, Ontario, In progress. |

[8] | Finke, G., Burkard, R.E., and Rendl, F. (1987), Quadratic assignment problems.Annals of Discrete Mathematics 31:61-82. · Zbl 0607.90026 |

[9] | Forgó, F. (1988),Nonconvex Programming. Akadémiai Kiadó, Budapest. |

[10] | Goemans, M.X. and Williamson, D.P. (1993), 878-approximation algorithms for max cut and max 2sat. Technical report, Department of Mathematics, MIT. · Zbl 1345.68274 |

[11] | Haemmers, W. (1979), On some problems of lovasz concerning the shannon capacity of graphs.IEEE Transactions on Information Theory 25:231-232. · Zbl 0402.94029 |

[12] | Hammer, P.L., Hansen, P., and Simeone, B. (1984), Roof duality, complementation and persistency in quadratic 0-1 optimization.Mathematical Programming 28:121-155. · Zbl 0574.90066 |

[13] | Helmberg, C., Rendl, F., Vanderbei, R.J., and Wolkowicz, H., A primal-dual interior point method for the max-min eigenvalue problem.SIAM Journal on Optimization, To appear. Accepted Aug/94. |

[14] | Karisch, S., Rendl, F., Wolkowicz, H., and Zhao, Q. (1995), Quadratic Lagrangian relaxation for the quadratic assignment problem. Research report, University of Waterloo, Waterloo, Ontario, In progress. · Zbl 0904.90145 |

[15] | Knuth, D.E. (1994), The sandwich theorem.Electronic J. Combinatorics 1:48pp. · Zbl 0810.05065 |

[16] | Körner, F. (1988), A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm.Optimization 19:711-721. · Zbl 0658.90066 |

[17] | Körner, F. (1992), Remarks on a difficult test problem for quadratic boolean programming.Optimization 26:355-357. · Zbl 0815.65082 |

[18] | Lovász, L. (1979), On the Shannon capacity of a graph.IEEE Transactions on Information Theory 25:1-7. · Zbl 0395.94021 |

[19] | Lovász, L. and Schrijver, A. (1991), Cones of matrices and set-functions and 0-1 optimization.SIAM Journal on Optimization 1(2):166-190. · Zbl 0754.90039 |

[20] | Luenberger, D.G. (1984),Linear and Nonlinear Programming, Reading. Addison-Wesley, Massachusetts, second edition. · Zbl 0571.90051 |

[21] | Moreé, J.J. and Sorensen, D.C. (1983), Computing a trust region step.SIAM J. Sci. Statist. Comput 4:553-572. · Zbl 0551.65042 |

[22] | Pardalos, P., Rendl, F., and Wolkowicz, H. (1994), The quadratic assignment problem: A survey and recent developments. InProceedings of the DIMACS Workshop on Quadratic Assignment Problems, volume 16 ofDIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 1-41. American Mathematical Society. · Zbl 0817.90059 |

[23] | Poljak, S. and Wolkowicz, H., Convex relaxations of 0-1 quadratic programming.Annals of Operations Research. To appear. · Zbl 0845.90089 |

[24] | Rendl, F. and Wolkowicz, H., A projection technique for partitioning the nodes of a graph.Annals of Operations Research. To appear in the special issue of APMOD93. · Zbl 0841.90120 |

[25] | Schrijver, A. (1979), A comparison of the Delsarte and Lovász bounds.IEEE Trans. Infor. Theory, IT-25:425-429. · Zbl 0444.94009 |

[26] | Stern, R. and Wolkowicz, H., Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations.SIAM J. Optimization, To appear. Accepted June/93. |

[27] | Wolkowicz, H. (1981), Some applications of optimization in matrix theory.Linear Algebra and its Applications 40:101-118. · Zbl 0472.90078 |

[28] | Wolkowicz, H., Multiple indefinite trust region problems and semidefinite programming. Research report, University of Waterloo, 1994. In progress. |

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.