【作者】 孙杨；

【导师】 白峰杉；

【作者基本信息】 清华大学 ， 数学， 2008， 博士

【摘要】 多项式优化是全局优化中的一个基本而重要的研究对象,很多源于控制理论、信号处理、计算机模拟等领域的问题都可以归结为多项式优化问题。数值算法和符号算法是两类求解多项式优化问题的方法。符号算法处理的对象是抽象的数学符号与代数概念,计算是基于整数运算的,因此没有误差。但也正是因为没有舍入,方法的计算量特别是存储量很大,导致对于大规模的问题有本质性的困难。数值算法能够求解规模较大的问题,但是也面临着数值稳定性等棘手的问题。为了能够有效的发挥数值算法和符号算法各自的优点,数值-符号混合算法是受到关注的研究热点之一。Hanzon和Jibetean提出了一类求解多项式优化问题的混合算法,称之为矩阵算法。对于优化目标多项式,通过一阶条件将优化问题转化为多项式方程组并加入高次的项作为扰动,从而很容易计算出相应的Gr(o|¨)bner基,任何多项式均可以由这组基线性表示。这里线性表示的系数矩阵称为相伴矩阵,进而将问题转化为求解相伴矩阵的特征值和特征向量的问题。在Hanzon-Jibetean算法中,相伴矩阵起到了核心的作用,但通常矩阵的规模非常大。本文提出了一类针对相伴矩阵的混合算法–改进矩阵算法。我们在一阶条件引出的多项式方程组与加入的高次扰动项之间建立匹配模型,通过优化两者之间的匹配关系,获得规模最小化的相伴矩阵,使得算法中相伴矩阵的规模明显降低,从而有效提升了算法的效率。在此基础之上,本文又针对求解多项式优化驻点的一阶条件,给出了一类矩阵收缩算法,即加入一个新的变量和一个新的多项式方程,从而使得算法只需计算对应于新增添变量的特征值,即可求得该多项式的驻点。这一改进对于多项式优化问题提供了更进一步的支撑,使得运算效率得到大幅度的提高。最后,本文给出了上述改进矩阵算法的一个应用,将其应用于多项式同伦系统,这一应用在一定程度上使得同伦跟踪系统的奇异解得以减少,也使得整个同伦跟踪算法更加有效。更多还原

【Abstract】 The multivariate polynomial optimization is an important problem in the globaloptimization. It has applications in many areas of science and engineering, such ascontrol theory and signal processing. Numerical algorithm and symbolic algorithm arethe fundamental approaches for this problem.Symbolic algorithm deals with mathematical symbols and algebra objects withouterror. However, this kind of method often leads to heavy duty of computation when thescale of the problem is large. Numerical algorithm, on the other hand, can solve largerproblem in general. It also faces problems, such as stability. Therefore numerical-symbolic hybrid method would be a natural consideration in order to take the advan-tages of both these two methods. Hanzon and Jibetean proposed matrix method, whichtransforms the optimization of multivariate polynomial to a polynomial system of equa-tions through the first order condition. The method can easily generate the Gr(o|¨)bnerbasis by adding high order leading terms, so that any polynomial can be represented bythese basis. Here the representing coefficient matrix is called associated matrix. Thenone can get the critical points of the objective polynomial through computing eigenval-ues and eigenvectors of the associated matrix.Associated matrix plays an important role in Hanzon-Jibetean method. However,the scale of associated matrix is often large. In this dissertation we propose a newhybrid method, which is named as improved matrix method. We establish a matchingmodel between the added high order leading terms and polynomial equations arisingfrom the first order conditions. By optimizing this matching, we can get the minimalscale of the associated matrix, which would make the scale of the associated matrixsmaller and the algorithm more efficient.At the same time, we propose a new matrix contractive algorithm by adding a newvariable and a new equation to the original first order conditions. In this method, weget the critical points of the objective polynomial through computing the eigenvalue ofthe new added variable only once. By this improvement, we can make the polynomialoptimization much faster. As an application, we apply the improved matrix methods to constructing the startsystem for the homotopy method. Numerical results show that our new start systemsreduce the number of singular solutions in the homotopy continuation procedure.更多还原