Skip to main content
SpringerLink
Log in

Approximation algorithms for indefinite complex quadratic maximization problems

  • Articles
  • Published:
Science China Mathematics Aims and scope Submit manuscript

Abstract

In this paper, we consider the following indefinite complex quadratic maximization problem: maximize z H Qz, subject to z k ∈ ℂ and z m k = 1, k = 1,...,n, where Q is a Hermitian matrix with tr Q = 0, z ∈ ℂn is the decision vector, and m ⩾ 3. An Ω(1/log n) approximation algorithm is presented for such problem. Furthermore, we consider the above problem where the objective matrix Q is in bilinear form, in which case a \( 0.7118\left( {\cos \frac{\pi } {m}} \right)^2 \) approximation algorithm can be constructed. In the context of quadratic optimization, various extensions and connections of the model are discussed.

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.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alon N, Naor A. Approximating the Cut-Norm via Grothendieck’s inequality. SIAM J Comput, 2006, 35: 787–803

    Article  MathSciNet  MATH  Google Scholar 

  2. Andersen H H, Høojbjerre M, Sørensen D, et al. Linear and graphical models for the multivariate complex normal distribution. In: Lecture Notes in Statistics, vol. 101. New York: Springer-Verlag, 1995

    Google Scholar 

  3. Ben-Tal A, Nemirovski A. On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty. SIAM J Optim, 2002, 12: 811–833

    Article  MathSciNet  MATH  Google Scholar 

  4. Ben-Tal A, Nemirovski A, Roos C. Extended matrix cube theorems with applications to μ-theory in control. Math Oper Res, 2003, 28: 497–523

    Article  MathSciNet  MATH  Google Scholar 

  5. Bertsimas D, Ye Y. Semidefinite relaxations, multivariate normal distribution, and order statistics. In: Du D Z, Pardalos P M, eds. Handbook of Combinatorial Optimization, vol. 3. Boston: Kluwer Academic Publishers, 1998, 1–19

    Google Scholar 

  6. Charikar M, Wirth A. Maximizing quadratic programs: extending Grothendieck’s inequality. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS). Rome: IEEE, 2004, 54–60

    Chapter  Google Scholar 

  7. De Maio A, De Nicola S, Huang Y, et al. Design of phase codes for radar performance optimization with a similarity constraint. IEEE Trans Signal Process, 2009, 57: 610–621

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  9. Goemans M X, Williamson D P. Approximation algorithms for Max-3-Cut and other problems via complex semidefinite programming. J Comput System Sci, 2004, 68: 442–470

    Article  MathSciNet  MATH  Google Scholar 

  10. Grothendieck A. Résumé de la théorie métrique des produits tensoriels topologiques. Bol Soc Mat Sao Paulo, 1956, 8: 1–79

    MathSciNet  Google Scholar 

  11. Haagerup U. A new upper bound for the complex Grothendieck constant. Israel J Math, 1987, 60: 199–224

    Article  MathSciNet  MATH  Google Scholar 

  12. Kisialiou M, Luo Z Q. Performance analysis of quasi-maximum-likelihood detector based on semi-definite programming. In: Proceedings of 2005 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP). Philadelphia: IEEE, 2005, 433–436

    Chapter  Google Scholar 

  13. Krivine J L. Sur la constante de Grothendieck. C R Acad Sci Paris Ser A-B, 1977, 284: 445–446

    MathSciNet  MATH  Google Scholar 

  14. Krivine J L. Constantes de Grothendieck et fonctions de type positif sur les sphères. Adv Math, 1979, 31: 16–30

    Article  MathSciNet  MATH  Google Scholar 

  15. Luo Z Q, Luo X D, Kisialiou M. An efficient quasi-maximum likelihood decoder for PSK signals. In: Proceedings of 2003 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP). Hong Kong: IEEE, 2003, 561–564

    Google Scholar 

  16. Luo Z Q, Sidiropoulos N, Tseng P, et al. Approximation bounds for quadratic optimization with homogeneous quadratic constraints. SIAM J Optim, 2007, 18: 1–28

    MathSciNet  MATH  Google Scholar 

  17. Nemirovski A, Roos C, Terlaky T. On maximization of quadratic form over intersection of ellipsoids with common center. Math Program, 1999, 86: 463–473

    Article  MathSciNet  MATH  Google Scholar 

  18. Nesterov Y. Semidefinite relaxation and nonconvex quadratic optimization. Optim Methods Softw, 1998, 9: 141–160

    Article  MathSciNet  MATH  Google Scholar 

  19. Rietz R E. A proof of the Grothendieck inequality. Israel J Math, 1974, 19: 271–276

    Article  MathSciNet  Google Scholar 

  20. Skutella M. Convex quadratic and semidefinite programming relaxations in scheduling. J ACM, 2001, 48: 206–242

    Article  MathSciNet  Google Scholar 

  21. So A, Zhang J, Ye Y. On approximating complex quadratic optimization problems via semidefinite programming relaxations. Math Program Ser B, 2007, 110: 93–110

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  23. Ye Y. Approximating quadratic programming with bound and quadratic constraints. Math Program, 1999, 84: 219–226

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electronic and Computer Engineering, The Hong Kong University of Science and Technology, Kowloon, Hong Kong, China

    Yongwei Huang

  2. Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, Hong Kong, China

    Shuzhong Zhang

Authors
  1. Yongwei Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shuzhong Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yongwei Huang.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Huang, Y., Zhang, S. Approximation algorithms for indefinite complex quadratic maximization problems. Sci. China Math. 53, 2697–2708 (2010). https://doi.org/10.1007/s11425-010-3087-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11425-010-3087-7

Keywords

MSC(2000)

Search

Navigation