Polynomial optimization and its applications

Abstract

The main purposes of this thesis are to solve some polynomial optimization problems and to find their applications. The polynomial optimization problems involved in this thesis include the cubic spherical optimization problems and bi-quadratic optimization problems. The main contributions of this thesis are as follows: In this thesis, we first consider a new model, the truncated generalized diffusion tensor imagine (GDTI) model in medical engineering, which overcomes the drawback that water movement in biological tissues often shows non-Gaussian diffusion behavior. In the GDTI model, polynomial associated with even order tensors reflects the magnitude of the signal, while polynomial associated with odd order tensors reflects the phase of the signal. Moreover, we use the apparent skewness coefficient (ASC) value to measure the phase of non-Gaussian signals. We present some properties of related tensors and propose a direct computation method for calculating the ASC value. We discuss the general cubic spherical optimization problems, which include the cubic one-spherical/two-spherical/three-spherical optimization problems. For these three problems, we present their NP-hardnesses and discuss the complexity results of some special cases. For the NP-hardness cases, some approximation solution methods for them are established. Then we study the bi-quadratic optimization problem over two unit spheres. At first, the problem is equivalently transformed into computing the largest M-eigenvalue of related tensor. Based on the reformulation, power method for computing the largest eigenvalue of a matrix is modified to compute the largest M-eigenvalue of a tensor. To get a good approximation of the largest M-eigenvalue of a tensor, we introduce an initialization technique. The given numerical experiments show that the modified method performs well. Finally, we discuss the bi-quadratic optimization problems with quadratic constraints. First, we generalize the SDP relaxation scheme for approximately solving NP-hard quadratic optimization to solve bi-quadratic optimization problems. Then we show that each r-bound approximation solution of the relaxed bi-linear SDP problems can be used to generate in randomized polynomial time an Ϭ(r)-approximation solution for bi-quadratic optimization problems. Furthermore, we show that when the number of constraints is not larger than two, bi-quadratic optimization problems are equivalent to their corresponding SDP relaxation problems, which generalizes the result in [33]. Then, we present some approximation solutions with some quality bounds for the bi-quadratic maximization model with some assumptions. For bi-quadratic optimization problems with two constraints, some approximation solutions are established. Finally, we extend the results from real cases to complex cases.