Conjugate Complex Polynomial And Its Tensor Representation:Theory And Algorithm

Polynomial optimization has attracted increasingly more attention in the past decade due to its enormous applications such as signal processing,control theory,speech recognition,investment sceience.In particular,arising from real-life applications including quantum physics,radar wave design and electricity transmission networks,complex polynomial optimization plays a more important role in mathematical optimization.As we all know,similar to the relation between Hermitian matrices and Hermitian quadratic functions,there also exsits one-to-one correspondence between the complex tensors and conjugate complex polynomials.This leads to the study of tensor related problems.In this thesis,we study optimization of real-valued conjugate complex polynomials and theory of their tensor representations.We first study conjugate partial-symmetric tensors and focus on algebraic structures,rank-one decompositions approximations,as well as their applications.We prove constructly that any conjugate partial-symmetric tensor can be decomposed into a sum of rank-one conjugate partial-symmetric tensors.This gives an alternative definition of conjugate partial-symmetric tensors via real linear combinations of rank-one conjugate partial-symmetric tensors.We also define different types of ranks and study the rank-one approximations and matricizations of conjugate partial-symmetric tensors.Rank-one equivalence of matricization enables us to develop new convex models and methods to find the best rank-one apporximation of conjugate partial-symmetric tensors.We test the new methods by conducting the numerical experiments including real engineering problems and simulated data.Excellent performances justify the capablity of our methods.We then proceed to studying the decomposition for a subclass of conjugate partialsymmetric tensors,unitarily decomposable conjugate partial-symmetric tensors.We propose the successive partial-symmetric rank-one approximation algorithm.This approximation algorithm not only exactly recovers the unitary decomposition of unitarily decomposable conjugate partial-symmetric tensors,it also recovers the decomposition robustly in the presence of perturbation.Finally,we study the optimization of real-valued 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.All the problems under consideration are NP-hard in general,so we foucs on polynomial-time approximation algorithms with worst case ratios.We prove the first approximation algorithms for these general conjugate polynomial problems.The algorithms are based on random sampling and tensor relaxation and the novel technique involved in the algorithm are set of probability lower bounds for random sampling over various constraints and polarization formula linking complex multilinear polynomials and general conjugate polynomials.The general conjugate polynomial optimization can handle broader problems.Our approximation ratios also improve the previous results when restricting our problems to some special classes of complex polynomial optimization.