Complex polynomial optimization has recently gained more and more attention
in both theory and practice. In this paper, we study the optimization of a
real-valued general conjugate complex form over various popular constraint sets
including the m-th roots of complex unity, the complex unit circle, and the
complex unit sphere. A real-valued general conjugate complex form is a
homogenous polynomial function of complex variables as well as their
conjugates, and always takes real values. General conjugate form optimization
is a wide class of complex polynomial optimization models, which include many
homogenous polynomial optimization in the real domain with either discrete or
continuous variables, and Hermitian quadratic form optimization as well as its
higher degree extensions. All the problems under consideration are NP-hard in
general and we focus on polynomial-time approximation algorithms with
worst-case performance ratios. These approximation ratios improve previous
results when restricting our problems to some special classes of complex
polynomial optimization, and improve or equate previous results when
restricting our problems to some special classes of polynomial optimization in
the real domain. These algorithms are based on tensor relaxation and random
sampling. Our novel technical contributions are to establish the first set of
probability lower bounds for random sampling over the m-th root of unity, the
complex unit circle, and the complex unit sphere, and propose the first
polarization formula linking general conjugate forms and complex multilinear
forms.