Skip to main content
SpringerLink
Log in

Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

At the intersection of nonlinear and combinatorial optimization, quadratic programming has attracted significant interest over the past several decades. A variety of relaxations for quadratically constrained quadratic programming (QCQP) can be formulated as semidefinite programs (SDPs). The primary purpose of this paper is to present a systematic comparison of SDP relaxations for QCQP. Using theoretical analysis, it is shown that the recently developed doubly nonnegative relaxation is equivalent to the Shor relaxation, when the latter is enhanced with a partial first-order relaxation-linearization technique. These two relaxations are shown to theoretically dominate six other SDP relaxations. A computational comparison reveals that the two dominant relaxations require three orders of magnitude more computational time than the weaker relaxations, while providing relaxation gaps averaging 3% as opposed to gaps of up to 19% for weaker relaxations, on 700 randomly generated problems with up to 60 variables. An SDP relaxation derived from Lagrangian relaxation, after the addition of redundant nonlinear constraints to the primal, achieves gaps averaging 13% in a few CPU seconds.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Adhya N., Tawarmalani M., Sahinidis N.V.: A Lagrangian approach to the pooling problem. Ind. Eng. Chem. 38, 1956–1972 (1999)

    Article  Google Scholar 

  2. Al-Khayyal F.A.: Generalized bilinear programming: Part I. Models, applications and linear programming relaxation. Eur. J. Oper. Res. 60, 306–314 (1992)

    Article  MATH  Google Scholar 

  3. Al-Khayyal F.A., Falk J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8, 273–286 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  4. Al-Khayyal F.A., Larsen C., Van Voorhis T.: A relaxation method for nonconvex quadratically constrained quadratic programs. J. Global Optim. 6, 215–230 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  5. Anstreicher, K., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. http://www.dollar.biz.uiowa.edu/~sburer/papers/023-qphull.pdf (2007)

  6. Anstreicher K.M.: Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Global Optim. 43, 471–484 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  7. Anstreicher K.M., Burer S.: DC versus copositive bounds for standard QP. J. Global Optim. 33(2), 299–312 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bao X., Sahinidis N.V., Tawarmalani M.: Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs. Optim. Methods Softw. 24, 485–504 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  9. Ben-Tal, A., Nemirovski, A.S.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2001)

    Book  MATH  Google Scholar 

  10. Benson, S.J., Ye, Y.: DSDP5: Software for semidefinite programming. Tech. Rep. ANL/MCS-P1289-0905, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL. ACM Trans. Math. Softw. http://www.mcs.anl.gov/~benson/dsdp (submitted, 2005)

  11. Bomze I.M., de Klerk E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24, 163–185 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  12. Bomze I.M., Dur M., de Klerk E., Roos C., Quist A.J., Terlaky T.: On copositive programming and standard quadratic optimization problems. J. Global Optim. 18(4), 301–320 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  13. Bomze I.M., Frommlet F., Rubey M.: Improved SDP bounds for minimizing quadratic functions over the l(1)-ball. Optim. Lett. 1(1), 49–59 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  14. Bomze I.M., Locatelli M., Tardella F.: New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability. Math. Program. 115(1), 31–64 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  15. Borchers B.: CSDP, A C library for semidefinite programming. Optim. Methods Softw. 11, 613–623 (1999)

    Article  MathSciNet  Google Scholar 

  16. Brooke A., Kendrick D., Meeraus A.: GAMS—A User’s Guide. The Scientific Press, Redwood City, CA (1988)

    Google Scholar 

  17. Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Tech. rep., University of Iowa, Iowa City, IA. http://www.optimization-online.org/DB_FILE/2009/01/2184.pdf (2008)

  18. Burer S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120(2), 295–479 (2009)

    Article  MathSciNet  Google Scholar 

  19. Burer, S., Chen, J.: Relaxing the optimality conditions of box QP. Tech. rep., Dept. of Management Sciences, University of Iowa, Iowa City, IA 52240. Available at http://www.optimization-online.org/DB_FILE/2007/10/1815.pdf (2007)

  20. Burer S., Vandenbussche D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program. 112, 259–282 (2008)

    Article  MathSciNet  Google Scholar 

  21. Dorneich M.C., Sahinidis N.V.: Global optimization algorithms for chip layout and compaction. Eng. Optim. 25, 131–154 (1995)

    Article  Google Scholar 

  22. Fujie T., Kojima M.: Semidefinite programming relaxation for nonconvex quadratic programs. J. Global Optim. 10, 367–380 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  23. Goemans M.X., Williamson D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  24. Hao E.P.: Quadratically constrained quadratic programming: some applications and a method for solution. Math. Methods Oper. Res. 26, 105–119 (1982)

    MATH  Google Scholar 

  25. Linderoth J.: A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Math. Program. 103, 251–282 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  26. Liu M.L., Sahinidis N.V.: Process planning in a fuzzy environment. Eur. J. Oper. Res. 100, 142–169 (1997)

    Article  MATH  Google Scholar 

  27. Locatelli M., Raber U.: Packing equal circles in a square: a deterministic global optimization approach. Discret. Appl. Math. 122, 139–166 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  28. McCormick G.P.: Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Program. 10, 147–175 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  29. Mittelmann H.D.: An independent benchmarking of SDP and SOCP solvers. Math. Program. 95, 407–430 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  30. Nowak I.: A new semidefinite programming bound for indefinite quadratic forms over a simplex. J. Global Optim. 14, 357–364 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  31. Pólik I., Terlaky T.: A survey of the S-Lemma. SIAM Rev. 49, 371–418 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  32. Poljak S., Rendl F., Wolkowicz H.: A recipe for semidefinite relaxation for (0,1)-quadratic programming. J. Global Optim. 7(1), 51–73 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  33. Quist A.J., de Klerk E., Roos C., Terlaky T.: Copositive relaxations for general quadratic programming. Optim. Methods Softw. 9, 185–208 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  34. Rikun A.D.: A convex envelope formula for multilinear functions. J. Global Optim. 10, 425–437 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  35. Rockafellar R.T.: Convex Analysis Princeton. Mathematical Series. Princeton University Press, Princeton (1970)

    Google Scholar 

  36. Sherali H.D.: Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. Acta Mathematica Vietnamica 22, 245–270 (1997)

    MathSciNet  MATH  Google Scholar 

  37. Sherali H.D.: RLT: a unified approach for discrete and continuous nonconvex optimization. Ann. Oper. Res. 149(1), 185–193 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  38. Shor N.Z.: Quadratic optimization problems. Soviet J. Comput. Syst. Sci. 25, 1–11 (1987)

    MathSciNet  MATH  Google Scholar 

  39. Shor N.Z.: Dual quadratic estimates in polynomial and Boolean programming. Ann. Oper. Res. 25, 163–168 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  40. Shor N.Z.: Dual estimates in multiextremal problems. J. Global Optim. 2, 411–418 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  41. Sutou A., Dai Y.: Global optimization approach to unequal sphere packing problems in 3D. J. Optim. Theory Appl. 114, 671–694 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  42. Tawarmalani M., Sahinidis N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103, 225–249 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  43. Van Voorhis T.: A global optimization algorithm using lagrangian underestimates and the interval Newton method. J. Global Optim. 24, 349–370 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  44. Vavasis S.A.: Quadratic programming is in NP. Inf. Process. Lett. 36, 73–77 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  45. Wolkowicz, H.: Semidefinite and lagrangian relaxations for hard combinatorial problems. In: Proceedings of the 19th IFIP TC7 Conference on System Modelling and Optimization, pp. 269–310. Kluwer, B.V., Deventer, The Netherlands (2000)

  46. Wolkowicz H.: A note on lack of strong duality for quadratic problems with orthogonal constraints. Eur. J. Oper. Res. 143(2), 356–364 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  47. Wolkowicz H., Anjos M.F.: Semidefinite programming for discrete optimization and matrix completion problems. Discret. Appl. Math. 123(1–3), 513–577 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  48. Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook of Semidefinite Programming. Theory, Algorithms, and Applications. Kluwer (2000)

  49. Xie W., Sahinidis N.V.: A branch-and-bound algorithm for the continuous facility layout problem. Comput. Chem. Eng. 32, 1016–1028 (2008)

    Article  Google Scholar 

  50. Yamashita M., Fujisawa K., Kojima M.: Implementation and evaluation of SDPA 6.0 (SemiDefinite Programming Algorithm 6.0). Optim. Methods Softw. 18, 491–505 (2003)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Chemical and Biomolecular Engineering, University of Illinois at Urbana-Champaign, Urbana, IL, 61801, USA

    Xiaowei Bao

  2. Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA, 15213, USA

    Nikolaos V. Sahinidis

  3. Krannert School of Management, Purdue University, West Lafayette, IN, 47907, USA

    Mohit Tawarmalani

Authors
  1. Xiaowei Bao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nikolaos V. Sahinidis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mohit Tawarmalani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nikolaos V. Sahinidis.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bao, X., Sahinidis, N.V. & Tawarmalani, M. Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons. Math. Program. 129, 129–157 (2011). https://doi.org/10.1007/s10107-011-0462-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-011-0462-2

Keywords

Mathematics Subject Classification (2000)

Search

Navigation