Complex polynomial optimization problems arise from real-life applications including radar code design, MIMO beamforming, and quantum mechanics. In this paper, we study complex polynomial optimization models where the objective function takes one of the following three forms: (1) multilinear; (2) homogeneous polynomial; (3) symmetric conjugate form. On the constraint side, the decision variables belong to one of the following three sets: (1) the m -th roots of complex unity; (2) the complex unity; (3) the Euclidean sphere. We first discuss the multilinear objective function. Polynomial-time approximation algorithms are proposed for such problems with assured worst-case performance ratios, which depend only on the dimensions of the model. Then we introduce complex homogenous polynomial functions and establish key linkages between complex multilinear forms and the complex polynomial functions. Approximation algorithms for the above-mentioned complex polynomial optimization models with worst-case performance ratios are presented. Numerical results are reported to illustrate the effectiveness of the proposed approximation algorithms.
Bibliographical noteFunding Information:
Acknowledgments This research was partially supported by National Science Foundation of USA [Grant CMMI-1161242], Natural Science Foundation of China [Grant 11371242], Natural Science Foundation of Shanghai [Grant 12ZR1410100], and Ph.D. Programs Foundation of Chinese Ministry of Education [Grant 20123108120002].
- Approximation algorithm
- Complex programming
- Complex tensor
- Polynomial optimization
- Tensor relaxation