Abstract
We investigate in this paper the duality gap between the binary quadratic optimization problem and its semidefinite programming relaxation. We show that the duality gap can be underestimated by \({\xi_{r+1}\delta^2}\), where δ is the distance between {−1, 1}n and certain affine subspace, and ξ r+1 is the smallest positive eigenvalue of a perturbed matrix. We also establish the connection between the computation of δ and the cell enumeration of hyperplane arrangement in discrete geometry.
Similar content being viewed by others
References
Allemand K., Fukuda K., Liebling T.M., Steiner E.: A polynomial case of unconstrained zero-one quadratic optimization. Math. Program. 91, 49–52 (2001)
Avis D., Fukuda K.: Reverse search for enumeration. Discret. Appl. Math. 65, 21–46 (1996)
Beck A., Teboulle M.: Global optimality conditions for quadratic optimization problems with binary constraints. SIAM J. Optim. 11, 179–188 (2000)
Ben-Ameur W., Neto J.: Spectral bounds for the maximum cut problem. Networks 52, 8–13 (2008)
Ben-Tal, A.: Conic and robust optimization. Lecture notes, Universita di Roma La Sapienzia, Rome, Italy (2002)
Billionnet A., Elloumi S.: Using a mixed integer quadratic programming solver for the unconstrained quadratic 0–1 problem. Math. Program. 109, 55–68 (2007)
Çela E., Klinz B., Meyer C.: Polynomially solvable cases of the constant rank unconstrained quadratic 0–1 programming problem. J. Comb. Optim. 12, 187–215 (2006)
Chakradhar S.T., Bushnell M.: A solvable class of quadratic 0–1 programming. Discret. Appl. Math. 36, 233–251 (1992)
Delorme C., Poljak S.: Laplacian eigenvalues and the maximum cut problem. Math. Program. 62, 557–574 (1993)
Fang S.C., Gao D.Y., Sheu R.L., Wu S.Y.: Canonical dual approach to solve 0–1 quadratic programming problems. J. Ind. Manag. Optim. 4, 125–142 (2008)
Gao D.Y., Ruan N., Sherali H.D.: Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality. J. Glob. Optim. 45, 473–497 (2009)
Goemans M.X., Williamson D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995)
Huang H.X., Pardalos P.M., Prokopyev O.A.: Lower bound improvement and forcing rule for quadratic binary programming. Comput. Optim. Appl. 33, 187–208 (2006)
Lemaréchal C., Oustry F.: SDP relaxations in combinatorial optimization from a Lagrangian point of view. In: Hadjisavvas, N., Pardalos, P.M. (eds) Advances in Convex Analysis and Global Optimization, pp. 119–134. Kluwer, Dordrecht (2001)
Li D., Sun X.L.: Nonlinear Integer Programming. Springer, New York (2006)
Li D., Sun X.L., Gu S.S., Gao J.J., Liu C.L.: Polynomially solvable cases of binary quadratic programs. In: Chinchuluun, A., Pardalos, P.M., Enkhbat, R., Tseveendorj, I. (eds) Optimization and Optimal Control: Theory and Applications, pp. 199–225. Springer, New York (2010)
Malik U., Jaimoukha I.M., Halikias G.D., Gungah S.K.: On the gap between the quadratic integer programming problem and its semidefinite relaxation. Math. Program. 107, 505–515 (2006)
Nesterov Y., Nemirovsky A.: Interior-Point Polynomial Methods in Convex Programming. SIAM, Philadelphia, PA (1994)
Pardalos P.M.: Construction of test problems in quadratic bivalent programming. ACM Trans. Math. Softw. 17, 74–87 (1991)
Pardalos, P.M., Wolkowicz, H. (eds): Topics in Semidefinite and Interior-Point Methods. Fields Institute Communications, American Mathematical Society, Providence (1998)
Pardalos, P.M., Wolkowicz, H. (eds): Novel Approaches to Hard Discrete Optimization. Fields Institute Communications, American Mathematical Society, Providence (2003)
Picard J.C., Ratliff H.D.: Minimum cuts and related problems. Networks 5, 357–370 (1975)
Poljak S., Rendl F., Wolkowicz H.: A recipe for semidefinite relaxation for (0, 1)-quadratic programming. J. Glob. Optim. 7, 51–73 (1995)
Poljak S., Wolkowicz H.: Convex relaxations of (0–1) quadratic programming. Math. Oper. Res. 20, 550–561 (1995)
Shor N.Z.: Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25, 1–11 (1987)
Sleumer N.: Output-sensitive cell enumeration in hyperplane arrangements. Nord. J. Comput. 6, 137–161 (1999)
Vandenberghe L., Boyd S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996)
Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds): Handbook of Semidefinite Programming: Theory, Algorithms, and Applications. Kluwer Academic Publishers, Dordrecht (2000)
Zaslavsky T.: Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. Mem. Am. Math. Soc. 1, 1–101 (1975)
Zheng X.J., Sun X.L., Li D., **a Y.: Duality gap estimation of linear equality constrained binary quadratic programming. Math. Oper. Res. 35, 864–880 (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by National Natural Science Foundation of China under grants 10971034 and 70832002, by the Joint NSFC/RGC grants under grant 71061160506, and by Research Grants Council of Hong Kong under grant 414207.
Rights and permissions
About this article
Cite this article
Sun, X.L., Liu, C.L., Li, D. et al. On duality gap in binary quadratic programming. J Glob Optim 53, 255–269 (2012). https://doi.org/10.1007/s10898-011-9683-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-011-9683-4