[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

SDP-based branch-and-bound for non-convex quadratic integer optimization

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

Semidefinite programming (SDP) relaxations have been intensively used for solving discrete quadratic optimization problems, in particular in the binary case. For the general non-convex integer case with box constraints, the branch-and-bound algorithm Q-MIST has been proposed by Buchheim and Wiegele (Math Program 141(1–2):435–452, 2013), which is based on an extension of the well-known SDP-relaxation for max-cut. For solving the resulting SDPs, Q-MIST uses an off-the-shelf interior point algorithm. In this paper, we present a tailored coordinate ascent algorithm for solving the dual problems of these SDPs. Building on related ideas of Dong (SIAM J Optim 26(3):1962–1985, 2016), it exploits the particular structure of the SDPs, most importantly a small rank of the constraint matrices. The latter allows both an exact line search and a fast incremental update of the inverse matrices involved, so that the entire algorithm can be implemented to run in quadratic time per iteration. Moreover, we describe how to extend this approach to a certain two-dimensional coordinate update. Finally, we explain how to include arbitrary linear constraints into this framework, and evaluate our algorithm experimentally.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Alizadeh, F., Haeberly, J.P., Overton, M.: Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77(1), 111–128 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  2. Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users’ Guide, 3rd edn. Society for Industrial and Applied Mathematics, Philadelphia (1999)

    Book  MATH  Google Scholar 

  3. Anjos, M.F., Lasserre, J.B. (eds.): Handbook on Semidefinite, Conic and Polynomial Optimization. International Series in Operations Research and Management Science, vol. 166. Springer, New York (2012)

    Google Scholar 

  4. Belotti, P., Lee, J., Liberti, L., Margot, F., Wächter, A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24(4–5), 597–634 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Billionnet, A., Elloumi, S., Lambert, A.: Extending the QCR method to general mixed-integer programs. Math. Program. 131(1–2), 381–401 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  6. Boas, P.V.E.: Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical report, University of Amsterdam, Department of Mathematics, Amsterdam (1981)

  7. Bonami, P., Biegler, L.T., Conn, A.R., Cornuéjols, G., Grossmann, I.E., Laird, C.D., Lee, J., Lodi, A., Margot, F., Sawaya, N., Wächter, A.: An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optim. 5, 186–204 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bonami, P., Gunluk, O., Linderoth, J.: Solving box-constrained nonconvex quadratic programs. Technical report, Optimization online (2016)

  9. Borchers, B.: CSDP, a C library for semidefinite programming. Optim. Methods Softw. 11(1–4), 613–623 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  10. Buchheim, C., Caprara, A., Lodi, A.: An effective branch-and-bound algorithm for convex quadratic integer programming. Math. Program. 135(1–2), 369–395 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  11. Buchheim, C., De Santis, M., Lucidi, S., Rinaldi, F., Trieu, L.: A feasible active set method with reoptimization for convex quadratic mixed-integer programming. SIAM J. Optim. 26(3), 1695–1714 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  12. Buchheim, C., Hübner, R., Schöbel, A.: Ellipsoid bounds for convex quadratic integer programming. SIAM J. Optim. 25(2), 741–769 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  13. Buchheim, C., Montenegro, M., Wiegele, A.: A coordinate ascent method for solving semidefinite relaxations of non-convex quadratic integer programs. In: Cerulli, R., Fujishige, S., Mahjoub, A. (eds.) ISCO. Lecture Notes in Computer Science, vol. 9849, pp. 110–122. Springer, Berlin (2016). https://doi.org/10.1007/978-3-319-45587-7

    Google Scholar 

  14. Buchheim, C., Wiegele, A.: Semidefinite relaxations for non-convex quadratic mixed-integer programming. Math. Program. 141(1–2), 435–452 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  15. Burer, S., Letchford, A.: On nonconvex quadratic programming with box constraints. SIAM J. Optim. 20(2), 1073–1089 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  16. Burer, S., Monteiro, R.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. (Ser. B) 95, 2003 (2001)

    Google Scholar 

  17. Burer, S., Vandenbussche, D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16(3), 726–750 (2006). https://doi.org/10.1137/040609574

    Article  MathSciNet  MATH  Google Scholar 

  18. Burer, S., Vandenbussche, D.: Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound. Comput. Optim. Appl. 43(2), 181–195 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  19. Dong, H.: Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations. SIAM J. Optim. 26(3), 1962–1985 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  20. Grippo, L., Palagi, L., Piccialli, V.: An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem. Math. Program. 126(1), 119–146 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  21. Helmberg, C.: Semidefinite programming for combinatorial optimization. Professorial dissertation, Technische Univertität Berlin, Berlin (2000)

  22. Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10(3), 673–696 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  23. Helmberg, C., Rendl, F., Weismantel, R.: A semidefinite programming approach to the quadratic knapsack problem. J. Comb. Optim. 4(2), 197–215 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  24. Homer, S., Peinado, M.: Design and performance of parallel and distributed approximation algorithms for maxcut. J. Parallel Distributed Comput. 46(1), 48–61 (1997)

    Article  Google Scholar 

  25. Kim, S., Kojima, M., Toh, K.C.: A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems. Math. Program. 156(1–2 (A)), 161–187 (2016). https://doi.org/10.1007/s10107-015-0874-5

    Article  MathSciNet  MATH  Google Scholar 

  26. Malick, J., Povh, J., Rendl, F., Wiegele, A.: Regularization methods for semidefinite programming. SIAM J. Optim. 20(1), 336–356 (2009). https://doi.org/10.1137/070704575

    Article  MathSciNet  MATH  Google Scholar 

  27. Misener, R., Floudas, C.A.: ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations. J. Glob. Optim. 59, 503–526 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  28. Montenegro, M.: A coordinate ascent method for solving semidefinite relaxations of non-convex quadratic integer programs. Phd thesis, Technische Universität Dortmund (2017)

  29. Ortega, J., Rheinboldt, W.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York (1970)

    MATH  Google Scholar 

  30. Park, J., Boyd, S.: A semidefinite programming method for integer convex quadratic minimization. Optim. Lett. 12, 499–518 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  31. Pisinger, D.: The quadratic knapsack problem a survey. Discrete Appl. Math. 155(5), 623–648 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  32. Poljak, S., Rendl, F.: Solving the max-cut problem using eigenvalues. Discrete Appl. Math. 62(1), 249–278 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  33. Sahinidis, N.V.: BARON 16.3.4: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual (2016)

  34. Sun, D., Toh, K.C., Yang, L.: A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints. SIAM J. Optim. 25(2), 882–915 (2015). https://doi.org/10.1137/140964357

    Article  MathSciNet  MATH  Google Scholar 

  35. 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 

  36. Wen, Z., Goldfarb, D., Yin, W.: Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2(3–4), 203–230 (2010). https://doi.org/10.1007/s12532-010-0017-1

    Article  MathSciNet  MATH  Google Scholar 

  37. Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming: Theory, Algorithms, and Applications. International Series in Operations Research and Management Science. Kluwer Academic, Boston (2000)

    Book  MATH  Google Scholar 

  38. Zhao, X.Y., Sun, D., Toh, K.C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20(4), 1737–1765 (2010). https://doi.org/10.1137/080718206

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Fakultät für Mathematik, TU Dortmund, Vogelpothsweg 87, 44227, Dortmund, Germany

    Christoph Buchheim & Maribel Montenegro

  2. Alpen-Adria-Universität Klagenfurt, Universitätsstr. 65-67, 9020, Klagenfurt, Austria

    Angelika Wiegele

Authors
  1. Christoph Buchheim
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Maribel Montenegro
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Angelika Wiegele
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Christoph Buchheim.

Additional information

This work was partially supported by the Marie Curie Initial Training Network MINO (Mixed-Integer Nonlinear Optimization) funded by the European Union. The first and the second author were partially supported by the DFG under Grant BU 2313/4-2. This paper is based on the PhD thesis [28]; a preliminary version can be found in [13].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Buchheim, C., Montenegro, M. & Wiegele, A. SDP-based branch-and-bound for non-convex quadratic integer optimization. J Glob Optim 73, 485–514 (2019). https://doi.org/10.1007/s10898-018-0717-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-018-0717-z

Keywords

Search

Navigation