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

A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

We consider a non-convex quadratic program (QP) with linear and convex quadratic constraints that arises from a broad range of applications and is known to be NP-hard. In this paper, we first prove that the alternative direction method converges to a local solution of the underlying QP problem. We then propose a new branch-and-cut algorithm that finds a globally optimal solution to the underlying QP problem within a pre-specified 𝜖-tolerance by integrating the alternative direction method with semidefinite relaxation and disjunctive cut techniques. We establish the global convergence of the algorithm and estimate its complexity. Preliminary numerical results demonstrate that the proposed algorithm can effectively find a globally optimal solution to medium-scale QP instances in which the number of negative eigenvalues of the Hessian matrix in the objective function is less than or equals 20.

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

Similar content being viewed by others

Notes

  1. All the data used in Section 4 can be downloaded at https://github.com/hezhiluo/QP.

  2. In our numerical experiments, the SDP subproblem in BB-SDR is solved by the SDP solver SeDuMi [36].

References

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

    Article  MathSciNet  Google Scholar 

  2. Anstreicher, K., Burer, S.: Computable representations for convex hulls of lowdimensional quadratic forms. Math. Program. (Ser. B) 124, 33–43 (2010)

    Article  Google Scholar 

  3. Burer, S., Dong, H.: Representing quadratically constrained quadratic programs as generalized copositive programs. Oper. Res. Lett. 40(3), 203–206 (2012)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  5. 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  Google Scholar 

  6. Cambini, R., Salvi, F.: A branch and reduce approach for solving a class of low rank D.C. programs. J. Comput. Appl. Math. 233, 492–501 (2009)

    Article  MathSciNet  Google Scholar 

  7. Cambini, R., Salvi, F.: Solving a class of low rank D.C. programs via a branch and bound approach: A computational experience. Oper. Res. Lett. 38 (5), 354–357 (2010)

    Article  MathSciNet  Google Scholar 

  8. Cambini, R., Sodini, C.: A finite algorithm for a particular D.C. quadratic programming problem. Ann. Oper. Res. 117(1), 33–49 (2002)

    Article  MathSciNet  Google Scholar 

  9. Chen, J., Burer, S.: Globally solving nonconvex quadratic programming problems via completely positive programming. Math. Program. Comput. 4, 33–52 (2012)

    Article  MathSciNet  Google Scholar 

  10. Floudas, C.A., Visweswaran, V.: Quadratic optimization. In: Horst, R., Pardalos, P.M. (eds.) Handbook of Global Optimization, pp 217–270. Kluwer Academic Publishers, Amsterdam (1994)

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

    Article  MathSciNet  Google Scholar 

  12. Gould, N.I.M., Toint, P.L.: Numerical methods for large-scale non-convex quadratic programming. In: Trends in Industrial and Applied Mathematics (Amritsar, 2001). Appl. Optim. , vol. 72, pp 149–179 (2002)

  13. Grant, M., Boyd, S., Ye, Y.: CVX: Matlab software for disciplined convex programming. avialable at http://www.stanford.edu/boyd/cvx

  14. IBM ILOG CPLEX: IBM ILOG CPLEX 12.3 User’s manual for CPLEX 89 (2011)

  15. Kim, S., Kojima, M.: Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations. Comput. Optim. Appl. 26, 143–154 (2003)

    Article  MathSciNet  Google Scholar 

  16. Konno, H.: A cutting plane algorithm for solving bilinear programs. Math. Program. 11, 14–27 (1976)

    Article  MathSciNet  Google Scholar 

  17. Konno, H., Kuno, T.: Multiplicative programming problems. In: Horst, R., Pardalos, P.M. (eds.) Handbook of Global Optimization, pp 369–405. Kluwer Academic Publishers, Dordrecht (1995)

  18. Le Thi, H.A.: An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints. Math. Program., Ser. A 87(3), 401–426 (2000)

    Article  MathSciNet  Google Scholar 

  19. Le Thi, H.A., Pham Dinh, T.: Solving a class of linearly constrained indefinite quadratic problems by D.C. algorithms. J. Global 11, 253–285 (1997)

    MathSciNet  MATH  Google Scholar 

  20. Le Thi, H.A., Pham Dinh, T.: A branch and bound method via D.C. algorithms and ellipsoidal technique for box constrained nonconvex quadratic problems. J. Global Optim. 13, 171–206 (1998)

    Article  MathSciNet  Google Scholar 

  21. Lu, C., Deng, Z.Z., Jin, Q.: An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints. J. Global Optim. 67(3), 475–493 (2017)

    Article  MathSciNet  Google Scholar 

  22. Luo, H.Z., Bai, X.D., Lim, G., Peng, J.M.: New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation. Math. Program. Comput. 11(1), 119–171 (2019)

    Article  MathSciNet  Google Scholar 

  23. Luo, H.Z., Bai, X.D., Peng, J.M.: Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods. J. Optim. Theory Appl. 180(3), 964–992 (2019)

    Article  MathSciNet  Google Scholar 

  24. Matsui, T.: NP-hardness of linear multiplicative programming and related problems. J. Global Optim. 9(2), 113–119 (1996)

    Article  MathSciNet  Google Scholar 

  25. Nesterov, Y.: Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Softw. 9, 140–160 (1998)

    Article  MathSciNet  Google Scholar 

  26. Palacios-Gomez, F., Lasdon, L., Enquist, M.: Nonlinear optimization by successive linear programming. Management Sci. 28(10), 1106–1120 (1982)

    Article  Google Scholar 

  27. Pardalos, P.M., Schnitger, G.: Checking local optimality in constrained quadratic programming is NP-hard. Oper. Res. Lett. 7(1), 33–35 (1988)

    Article  MathSciNet  Google Scholar 

  28. Pardalos, P.M., Vavasis, S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim. 1, 15–22 (1991)

    Article  MathSciNet  Google Scholar 

  29. Parrilo, P.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2), 293–320 (2003)

    Article  MathSciNet  Google Scholar 

  30. Peng, J.M., Tao, Z., Luo, H.Z., Toh, K.K.: Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting. Comput. Optim. Appl. 60(1), 171–198 (2015)

    Article  MathSciNet  Google Scholar 

  31. Pham Dinh, T., Le Thi, H.A.: Recent Advances in DC Programming and DCA. In: Transactions on Computational Intelligence XIII, pp 1–37. Springer, Berlin (2014)

  32. Saxena, A., Bonami, P., Lee, J.: Convex relaxation of non-convex mixed integer quadratically constrained programs: Extended formulations. Math. Program. Ser. B 124, 383–411 (2010)

    Article  MathSciNet  Google Scholar 

  33. Saxena, A., Bonami, P., Lee, J.: Convex relaxation of nonconvex mixed integer quadratically constrained programs: Projected formulations. Math. Program. Ser. A 130, 359–413 (2011)

    Article  Google Scholar 

  34. Shen, P.P., Huang, B.: Global algorithm for solving linear multiplicative programming problems. Optim. Lett., https://doi.org/10.1007/s11590-018-1378-z(2019)

  35. Sherali, H., Adams, W.: A reformulation-linearization technique for solving discrete and continuous nonconvex problems. Kluwer (1998)

  36. Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11, 625–653 (1999)

    Article  MathSciNet  Google Scholar 

  37. Toh, K.K., Todd, M., Tutuncu, R.: SDPT3: Matlab software package for semidefinite programming. Optim. Methods Softw. 11(12), 545–581 (1999)

    Article  MathSciNet  Google Scholar 

  38. Vandenbussche, D., Nemhauser, G.: A branch-and-cut algorithm for nonconvex quadratic programming with box constraints. Math. Program. 102, 559–575 (2005)

    Article  MathSciNet  Google Scholar 

  39. Vandenbussche, V., Nemhauser, G.G.: A polyhedral study of nonconvex quadratic programs with box constraints. Math. Program. 102(3), 531–557 (2005)

    Article  MathSciNet  Google Scholar 

  40. Vavasis, S.A.: Approximation algorithms for indefinite quadratic programming. Math. Program. 57, 279–311 (1992)

    Article  MathSciNet  Google Scholar 

  41. Visweswaran, V., Floudas, C.: New properties and computational improvement of the GOP algorithm for problems with quadratic objective function and constraints. J. Global Optim. 3(3), 439–462 (1993)

    Article  MathSciNet  Google Scholar 

  42. Wang, C., Bai, Y., Shen, P.: A practicable branch-and-bound algorithm for globally solving multiplicative programming. optimization. Optimization 66(3), 397–405 (2017)

    Article  MathSciNet  Google Scholar 

  43. Ye, Y.: On the complexity of approximating a KKT point of quadratic programming. Math. Program. 80, 195–211 (1998)

    Article  MathSciNet  Google Scholar 

  44. Ye, Y.: Approximating quadratic programming with bound and quadratic constraints. Math. Program. 84(2), 219–226 (1999)

    Article  MathSciNet  Google Scholar 

  45. Zhang, S.: Quadratic maximization and semidefinite relaxation. Math. Program. 87, 453–465 (2000)

    Article  MathSciNet  Google Scholar 

  46. Zhang, Y., So, A.-C.: Optimal spectrum sharing in mimo cognitive radio networks via semidefinite programming. IEEE J. Sel. Areas Commun. 29, 362–373 (2011)

    Article  Google Scholar 

  47. Zheng, X., Sun, X., Li, D.: Convex relaxations for nonconvex quadratically constrained quadratic programming: Matrix cone decomposition and polyhedral approximation. Math. Program. (Ser. B) 129, 301–329 (2011)

    Article  MathSciNet  Google Scholar 

  48. Zheng, X., Sun, X., Li, D.: Nonconvex quadratically constrained quadratic programming: Best D.C. decompositions and their SDP representations. J. Global Optim. 50, 695–712 (2011)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

The authors would like to thank the Associate Editor and the two anonymous referees for the detailed comments and valuable suggestions, which have improved the final presentation of the paper.

Funding

The work is supported by the NSFC grants 11871433 and 11371324 and the Zhejiang Provincial NSFC grants LY18A010011 and LZ21A010003.

Author information

Authors and Affiliations

  1. Department of Mathematics, College of Science, Zhejiang Sci-Tech University, Hangzhou, Zhejiang, 310018, China

    Hezhi Luo

  2. Department of Applied Mathematics, College of Science, Zhejiang University of Technology, Hangzhou, Zhejiang, 310032, China

    Sikai Chen

  3. Department of Mathematics, College of Science, Hangzhou Dianzi University, Hangzhou, Zhejiang, 310018, China

    Huixian Wu

Authors
  1. Hezhi Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sikai Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Huixian Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hezhi Luo.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Luo, H., Chen, S. & Wu, H. A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation. Numer Algor 88, 993–1024 (2021). https://doi.org/10.1007/s11075-020-01065-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-020-01065-7

Keywords

Mathematics Subject Classification (2010)

Search

Navigation