| As a fundamental model in Operations Research, polynomial optimization has been receiving increasingly more attention in the recent years, due to its versatile modern applications in engineering such as biomedical engineering, signal processing, material science, speech recognition, and so on. In this thesis, we present a systematic study of polynomial optimization. First, we study the structures of various polynomial functions, based on which efficient algorithms will consequently be developed. The newly developed solution methods will be tested on a variety of engineering applications. Specifically, we first study the class of nonnegative polynomials. Six fundamentally important types of nonnegative quartic functions coagulating into a chain in decreasing order will be presented. This structure is useful in understanding the nature of quartic polynomials. We further consider the polynomial sized representation of a very specific nonnegative polynomial, and this representation enables us to address an open question asserting that the computation of the matrix 2 → 4 norm is NP-hard in general. Then we proceed to studying polynomial function in random variables and establish a series of fundamental probability inequalities. Similar to the relationship between the symmetric matrices and the quadratic functions, there also exists a one-to-one correspondence between the super-symmetric tensors and the homogeneous polynomials, and this leads to the knowledge of tensor related problems. We then proceed to a new notion of matrix-rank for the even order tensors. Unlike the CP-rank of tensors, the matrix-rank is easy to compute. On the computational side, the afore-mentioned probability inequalities lead to new approximation algorithms with better approximation ratios than the ones known in the literature. We also propose approximation algorithms for polynomial optimization in complex variables. At the same time, we consider first order algorithms such as the alternating direction method of multipliers (ADMM), and the maximum block improvement algorithms (MBI). Finally, we test the new algorithms by solving real engineering problems including the tensor PCA problem, the tensor recovery problem in computer vision and the radar waveform design problem. Excellent performances of the proposed methods have been confirmed by our numerical results. |
