Polynomial optimization problems
Polynomial optimization problems
复制标题
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Shuzhong Zhang;Zhening Li
中科院分区：
文献类型：
--
作者：
Shuzhong Zhang;Zhening Li
多项式优化问题是指在多项式等式和不等式约束条件下，对一般的多元多项式函数进行优化。这样的问题公式可以追溯到19世纪世纪，当时希尔伯特讨论了非负多项式与平方和之间的关系。多项式优化问题是最优化领域的基本问题之一，在生物医学工程、控制理论、图论、投资科学、材料科学、数值线性代数、量子力学、信号处理、语音识别等领域有着广泛的应用。重点是优化一个高次多项式函数，在一些常见的约束集，如欧几里德球，欧几里德球，相交的同心椭球，二进制超立方体，以及它们的组合。具体地，讨论了五类模型，即，优化具有二次约束的多线性函数、具有二次约束的齐次多项式、具有凸约束的一般多项式、具有二元约束的一般多项式以及具有二元和球面约束的齐次多项式。所有的问题都是NP难的。本论文的主要贡献在于设计和分析保证最坏情况性能比的多项式时间近似算法。这些近似比仅依赖于问题的维数，新的结果改进了文献中的一些现有结果。在每一类优化模型中，讨论了一些应用实例，并给出了数值实验结果，表明所提算法在求解随机生成的测试实例时具有良好的实际性能.
Polynomial optimization problem is to optimize a generic multivariate polynomial function, subject to some suitable polynomial equality and inequality constraints. Such problem formulation dates back to the 19th century, when the relationship between nonnegative polynomials and sum of squares were discussed by Hilbert. Polynomial optimization is one of the fundamental problems in the field of optimization, and has applications in a large range of areas, including biomedical engineering, control theory, graph theory, investment science, material science, numerical linear algebra, quantum mechanics, signal processing, speech recognition, etc. This thesis presents a study of some important subclasses of polynomial optimization problems arising from various applications. The focus is on optimizing a high degree polynomial function, over some commonly encountered constraint sets, such as the Euclidean ball, the Euclidean sphere, the intersection of co-centered ellipsoids, the binary hypercube, as well as a combination of them. Specifically, five classes of models are discussed, i.e., optimizing a multilinear function with quadratic constraints, a homogeneous polynomial with quadratic constraints, a general polynomial with convex constraints, a general polynomial with binary constraints, and a homogeneous polynomial with binary and spherical constraints. All the problems under consideration are NP-hard in general. The main contribution of this thesis is on the design and analysis of polynomial-time approximation algorithms with guaranteed worst-case performance ratios. These approximation ratios are dependent on the problem dimensions only, and the new results improve some of the existing results in the literature. In each class of these optimization models, some application examples are discussed and results of numerical experiments are reported, revealing good practical performance of the proposed algorithms for solving some randomly generated test instances.