Polynomial optimization: structures, algorithms, and engineering applications

Loading...

View/Download File

Jiang_umn_0130E_14236.pdf (1.56 MB)

Persistent link to this item

https://hdl.handle.net/11299/159747

Statistics

View Statistics

Journal Title

Journal ISSN

Volume Title

Title

Polynomial optimization: structures, algorithms, and engineering applications

Authors

Jiang, Bo

Published Date

2013-08

Publisher

Type

Thesis or Dissertation

Abstract

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 \mapsto 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.

Keywords

Approximation algorithms

Low-rank

Polynomial optimization

Tensor optimization

Description

University of Minnesota Ph.D. dissertation. August 2013. Major: Industrial and Systems Engineering. Advisor:Shuzhong Zhang. 1 computer file (PDF); x, 211 pages.

Related to

Replaces

License

Collections

Dissertations

Series/Report Number

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Suggested citation

Jiang, Bo. (2013). Polynomial optimization: structures, algorithms, and engineering applications. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/159747.

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.