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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alon N, Naor A. Approximating the Cut-Norm via Grothendieck’s inequality. SIAM J Comput, 2006, 35: 787–803
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
Ben-Tal A, Nemirovski A. On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty. SIAM J Optim, 2002, 12: 811–833
Ben-Tal A, Nemirovski A, Roos C. Extended matrix cube theorems with applications to μ-theory in control. Math Oper Res, 2003, 28: 497–523
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
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
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
Goemans M X, Williamson D P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM, 1995, 42: 1115–1145
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
Grothendieck A. Résumé de la théorie métrique des produits tensoriels topologiques. Bol Soc Mat Sao Paulo, 1956, 8: 1–79
Haagerup U. A new upper bound for the complex Grothendieck constant. Israel J Math, 1987, 60: 199–224
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
Krivine J L. Sur la constante de Grothendieck. C R Acad Sci Paris Ser A-B, 1977, 284: 445–446
Krivine J L. Constantes de Grothendieck et fonctions de type positif sur les sphères. Adv Math, 1979, 31: 16–30
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
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
Nemirovski A, Roos C, Terlaky T. On maximization of quadratic form over intersection of ellipsoids with common center. Math Program, 1999, 86: 463–473
Nesterov Y. Semidefinite relaxation and nonconvex quadratic optimization. Optim Methods Softw, 1998, 9: 141–160
Rietz R E. A proof of the Grothendieck inequality. Israel J Math, 1974, 19: 271–276
Skutella M. Convex quadratic and semidefinite programming relaxations in scheduling. J ACM, 2001, 48: 206–242
So A, Zhang J, Ye Y. On approximating complex quadratic optimization problems via semidefinite programming relaxations. Math Program Ser B, 2007, 110: 93–110
Sturm J F. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim Methods Softw, 1999, 11–12: 625–653
Ye Y. Approximating quadratic programming with bound and quadratic constraints. Math Program, 1999, 84: 219–226
Zhang S. Quadratic maximization and semidefinite relaxation. Math Program, 2000, 87: 453–465
Zhang S, Huang Y. Complex quadratic optimization and semidefinite programming. SIAM J Optim, 2006, 16: 871–890
Author information
Authors and Affiliations
Corresponding author
Rights 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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11425-010-3087-7
Keywords
- indefinite Hermitian matrix
- randomized algorithms
- approximation ratio
- semidefinite programming relaxation