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