A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem | Journal of Global Optimization
Skip to main content
Springer Nature Link
Log in

A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem

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

Abstract

In this paper, we propose a semidefinite relaxation based branch-and-bound algorithm to the unit-modulus constrained complex quadratic programming problem, which has broad applications in signal processing and wireless communications. Our research is motivated from the potential application of the magnitude least-square problem, which possesses the so-called block-arrow sparsity pattern. We discuss how to reduce the worst-case complexity of the proposed branch-and-bound algorithm by exploiting this special sparsity pattern. Numerical results are presented to show the effectiveness of the proposed algorithm.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

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

Similar content being viewed by others

Notes

  1. In general, an angle \(\tau \) can be any real number, without the requirement of \(\tau \in (-\pi ,\pi ]\).

  2. Each edge in the graph \(\mathcal {F}\) has a length of one, and the length of a path equals the number of edges in the path.

References

  1. Arora, A., Tsinos, C.G., Bhavani Shankar, M.R., Chatinotas, S., Ottersten, B.: Efficient algorithms for constant-modulus analog beamforming. IEEE Trans. Signal Process. 70, 756–771 (2022)

    Article  MathSciNet  Google Scholar 

  2. Azuma, G., Fukuda, M., Kim, S., Yamashita, M.: Exact SDP relaxations of quadratically constrained quadratic programs with forest structures. J. Glob. Optim. 82, 243–262 (2022)

    Article  MathSciNet  Google Scholar 

  3. Azuma, G., Fukuda, M., Kim, S., Yamashita, M.: Exact SDP relaxations for quadratic programs with bipartite graph structures. J. Glob. Optim. 2022, 1–21 (2022)

    Google Scholar 

  4. Bandeira, A.S., Boumal, N., Singer, A.: Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Math. Program. 163(1–2), 145–167 (2017)

    Article  MathSciNet  Google Scholar 

  5. Boumal, N.: Nonconvex phase synchronization. SIAM J. Optim. 26(4), 2355–2377 (2016)

    Article  MathSciNet  Google Scholar 

  6. Chen, C., Atamtürk, A., Oren, S.S.: A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables. Math. Program. 165(2), 549–577 (2017)

    Article  MathSciNet  Google Scholar 

  7. Fukuda, M., Kojima, M., Murota, K., Nakata, K.: Exploiting sparsity in semidefinite programming via matrix completion I: general framework. SIAM J. Optim. 11(3), 647–674 (2001)

    Article  MathSciNet  Google Scholar 

  8. Jaldén, J., Martin, C., Ottersten, B.: Semidefinite programming for detection in linear systems–Optimality conditions and space-time decoding. In: Proceedings 2003 IEEE international conference on acoustics, speech, and signal processing (ICASSP), pp. 9–12 (2003)

  9. Kassakian, P.W.: Convex approximation and optimization with applications in magnitude filter design and radiation pattern analysis. PhD Dissertation, Department of EECS, University of California, Berkeley (2006)

  10. Kim, S., Kojima, M., Mevissen, M., Yamashita, M.: Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion. Math. Program. 129(1), 33–68 (2001)

    Article  MathSciNet  Google Scholar 

  11. Kocvara, M.: Decomposition of arrow type positive semidefinite matrices with application to topology optimization. Math. Program. 190(1–2), 105–134 (2021)

    Article  MathSciNet  Google Scholar 

  12. Lu, C., Deng, Z., Zhang, W.Q., Fang, S.C.: Argument division based branch-and-bound algorithm for unit-modulus constrained complex quadratic programming. J. Glob. Optim. 70(1), 171–187 (2018)

    Article  MathSciNet  Google Scholar 

  13. Lu, C., Liu, Y.F.: An efficient global algorithm for single-group multicast beamforming. IEEE Trans. Signal Process. 65(14), 3761–3774 (2017)

    Article  MathSciNet  Google Scholar 

  14. Ma, W.K., Ching, P.C., Ding, Z.: Semidefinite relaxation based multiuser detection for \(M\)-ary PSK multiuser systems. IEEE Trans. Signal Process. 52(10), 2862–2872 (2004)

    Article  Google Scholar 

  15. Maio, A.D., Huang, Y., Piezzo, M., Zhang, S., Farina, A.: Design of optimized radar codes with a peak to average power ratio constraint. IEEE Trans. Signal Process. 59(6), 2683–2697 (2011)

    Article  MathSciNet  Google Scholar 

  16. Maio, A.D., Nicola, S.D., Huang, Y., Luo, Z.Q., Zhang, S.: Design of phase codes for radar performance optimization with a similarity constraint. IEEE Trans. Signal Process. 57(2), 610–621 (2009)

    Article  MathSciNet  Google Scholar 

  17. Mosek: Mosek ApS. http://www.mosek.com (2020)

  18. Nakata, K., Fujisawa, K., Fukuda, M., Kojima, M., Murota, K.: Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical results. Math. Program. 95(2), 303–327 (2003)

    Article  MathSciNet  Google Scholar 

  19. Singer, A.: Angular synchronization by eigenvectors and semidefinite programming. Appl. Comput. Harmon. Anal. 30(1), 20–36 (2011)

    Article  MathSciNet  Google Scholar 

  20. So, A.M.C.: Probabilistic analysis of the semidefinite relaxation detector in digital communications. In: Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms (SODA’10), pp. 698–711 (2010)

  21. Sojoudi, S., Lavaei, J.: Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure. SIAM J. Optim. 24(4), 1746–1778 (2014)

    Article  MathSciNet  Google Scholar 

  22. Soltanalian, M., Stoica, P.: Designing unimodular codes via quadratic optimization. IEEE Trans. Signal Process. 62(5), 1221–1234 (2014)

    Article  MathSciNet  Google Scholar 

  23. Tan, P.H., Rasmussen, L.K.: The application of semidefinite programming for detection in CDMA. IEEE J. Sel. Areas Commun. 19(8), 1442–1449 (2001)

    Article  Google Scholar 

  24. Tranter, J., Sidiropoulos, N.D., Fu, X., Swami, A.: Fast unit-modulus least squares with applications in beamforming. IEEE Trans. Signal Process. 65(11), 2875–2887 (2017)

    Article  MathSciNet  Google Scholar 

  25. Vandenberghe, L., Andersen, M.: Chordal graphs and semidefinite optimization. Found. Trends Optim. 1(4), 241–433 (2015)

    Article  Google Scholar 

  26. Waldspurger, I., d’Aspremont, A., Mallat, S.: Phase recovery, MaxCut and complex semidefinite programming. Math. Program. 149(1–2), 47–81 (2015)

    Article  MathSciNet  Google Scholar 

  27. Zhang, R.Y., Lavaei, J.: Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion. Math. Program. 188(1), 351–393 (2021)

    Article  MathSciNet  Google Scholar 

  28. Zhang, S., Huang, Y.: Complex quadratic optimization and semidefinite programming. SIAM J. Optim. 16(3), 871–890 (2006)

    Article  MathSciNet  Google Scholar 

  29. Zheng, Y., Fantuuzzi, G., Papachristodoulou, A., Goulart, P., Wynn, A.: Chordal decomposition in operator-splitting methods for sparse semidefinite programs. Math. Program. 180(1–2), 489–532 (2020)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Economics and Management, North China Electric Power University, Beijing, 102206, China

    Cheng Lu & Jitao Ma

  2. MOE Social Science Laboratory of Digital Economic Forecasts and Policy Simulation at UCAS, School of Economics and Management, University of Chinese Academy of Sciences, Beijing, 100190, China

    Zhibin Deng

  3. Department of Mathematical Sciences, Tsinghua University, Beijing, 100084, China

    Wenxun Xing

Authors
  1. Cheng Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jitao Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhibin Deng
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wenxun Xing
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhibin Deng.

Additional information

Publisher's Note

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

Lu’s research has been supported by National Natural Science Foundation of China Grant No. 12171151. Deng’s research has been supported by the National Natural Science Foundation of China Grant No. T2293774, by the Fundamental Research Funds for the Central Universities E2ET0808X2, and by the grant from MOE Social Science Laboratory of Digital Economic Forecast and Policy Simulation at UCAS. Xing’s research has been supported by National Natural Science Foundation of China Grant No. 11771243.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lu, C., Ma, J., Deng, Z. et al. A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem. J Glob Optim 88, 115–137 (2024). https://doi.org/10.1007/s10898-023-01305-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-023-01305-9

Keywords

Search

Navigation