第 1章 引言
1.1 选题背景及意义
在现实世界中，有大量源于控制理论、信号处理、计算机模拟等领域的问题都可以归结为多项式优化问题。也就是对于一个多项式目标函数，我们的目标就是在给定的可行域上获得最优值（最大值或者最小值）。这是一类比较特殊的全局优化问题。
全局优化有很多值得研究的课题，它的理论和算法主要在两个方向上取得进展：一个是设计算法来近似一个函数的最优值，因为这些算法没有利用优化准则的一些信息，所以我们经常称之为黑箱优化算法，比如随机算法，区间算法以及同伦算法等等；另一方面是针对一类特殊问题设计的特殊算法，它们着眼于寻找一些特殊的性质来保证某些比较好的理论结果。例如我们经常提到的一类是凸规划问题，这类问题指的是目标函数和可行域都是凸的。我们知道凸规划有很好的理论性质，即局部最优解就是全局最优解，这就意味着任何一个能找到局部最优解的算法就能够得到全局最优解。对于凸规划的问题，已经存在能找到全局最优解的算法，比如说Karmarkar在1984年首先提出的针对线性规划的内点算法，这个算法在1989年被Nesterov 和Nemirovsky扩展到应用于全部凸非线性规划的问题中。在系统论和控制论领域，一类特殊的凸非线性规划问题找到了很重要的应用，这些优化问题是定义在半正定对称矩阵上的，也就是众所周知的线性矩阵不等式问题。除了凸规划问题之外，还有大量的非凸规划问题。实际上，这些非凸规划问题的难度无论是理论上还是实际上都远远高于凸规划问题。对于上述在全局规划中讨论的两类优化算法，我们希望达到如下的目标：第一，算法应当确保一定能找到最优解，目前也有一批算法可以达到这一目的；除此之外，我们关注于算法的复杂性，也就是如果算法可以计算出最优解，那么我们付出的代价究竟有多少。然而，除了针对凸规划的有效算法之外，鲜有几个问题具有很有效率的算法。实际上大部分的问题都被证明是NP难的。无论如何，都可以认为对于大规模的问题，大部分的算法只在理论上有意义，而实际运算过程都非常难以得到好的结果。基于上述原因，我们所考虑的多项式优化问题应该被归结为非凸优化问题。考虑到计算的复杂性，多项式优化问题是一个彻头彻尾的NP难的问题。这就制约了我们的算法，使得我们难以计算大规模的多项式优化问题。不过，我们的目标被定位在设计某些有效的算法来确保找到最优解。
1.3 本文的结构安排
现在我们给出一个具体的多项式优化的定义，令P ∈ K[x1, x2, . . . , xn] 是一个次数大于1的多项式。我们将要计算：
在这里我们采用infimum(inf) 来代替经常被使用的minimum(min) ,或者supremum(sup) 来代替maximum(max) ,意思是最优值可能在实数上无法取到，但是可以被渐近式的趋近。找到一个多项式的下界是一个传统的问题，实际上，一百多年前伟大的德国数学家希尔伯特就提出了通过决定一个多项式是否可以在整个区间上被确定为非负来决定其是否大于零。他的相关工作和假设引出了一个新的数学领域：实代数几何。在本文中，不同的工具和结果都被用来辅助我们所设计的算法。
我们将在第二章给出一些将要被用到的定义和结果：Gr¨obner基理论及其计算、Hanzon-Jibetean算法的原理以及多项式方程组的预处理。
第三章我们在Hanzon-Jibetean方法的基础上，给出一类求解大规模多项式优化的改进矩阵算法。针对原方法在实际计算中产生大规模矩阵这一问题，我们给出了基于匹配模型的算法，从而较大程度的把这类算法从原来的只具有理论意义提高到具有实际计算意义的层次，同时，我们将针对大批计算实例进行比较，可以清晰的看出我们的改进算法所具有的计算优势。
第四章我们在第三章改进矩阵算法的基础上，给出了一类多项式优化的矩阵收缩算法。该类算法将求解多项式方程组的根的问题转化为求解多个线性特征值的问题，由于在这一过程中需要用到求解多项式的一阶条件，对于多变量高次数的多项式问题我们需要求解多个特征值问题，在此我们给出一个新形式的一阶条件，从而把原来需要求解多个特征值的问题转化成只需求解一个特征值的问题，在实际计算中，这一新的算法在很大程度上提高了原算法的效率。
第五章我们给出上述改进矩阵算法的一个应用，也就是将其应用于计算多项式方程组的同伦算法的初始系统的构造。经过我们改造的初始系统能够在一定程度上使得同伦跟踪的奇异解减少，从而使得用于计算多项式方程组的同伦算法更加有效。
第 2章 基本概念和准备知识
2.1 多元多项式理论
交换代数与代数几何是一门利用代数工具研究由多项式方程组定义的几何对象的科学。在它的发展历程中，既出现了作为科学的一般理论，也累计了大量的对于具体对象的详细考证。近二十年来，随着计算机的出现，交换代数与代数几何的研究出现了重大的变化，即计算代数与应用技术达到新的发展阶段，在许多实际问题中展现了可喜的发展前景，如几何设计、组合优化、整数规划、编码理论以及机器人学等应用领域，都可以看到计算代数与应用所发挥的作用，本章的目的就是阐述计算代数与符号算法的基本理论，尤其是其中最重要的基本算法之一：Gr¨obner基算法的理论和应用。
先回顾有关多项式的一些术语，设x1, x2, . . . , xn是n 个变元，这n个变元的任一个乘积形式：
称为这n个变元集上的一个单项式，若K表示一个域，在这里K既可以是 (实数域）,也可以是C(复数域），我们称系数在K中的单项式的有限线性组合，称为多项式。多项式构成的方程叫做多项式方程，多个多项式方程组成的集合叫做多项式方程组，我们在这里要考量的是对于n变量的多项式方程组，方程组的系数来源于域K,也就是Kn的一个子集。
首先，我们回忆一些多项式方程组解集的定义，令K[x1, x2, . . . , xn]表示所有包含自变量x1, x2, . . . , xn并且系数在域K中的多项式。
定义 2.1: 考虑多项式方程组：f1(x1, . . . , xn) = 0, . . . , fs(x1, . . . , xn) = 0的解(a1, . . . , an) ∈ K所 构 成 的 集 合 称 为 由f1, . . . , fs定 义 的 仿 射 簇 ， 记为V(f1, . . . , fs)。Kn中的任意子集V，如果等于多项式方程组的解的集合，称V为仿射簇。有时也简称簇。
2.2多项式方程组的Stetter-M¨oller 方法
这一节我们给出Gr¨obner 基在求解多项式方程组中的一个重要应用,对于多项式方程组这一非线性问题，我们可以通过使用Gr¨obner 基将非线性问题转化为线性问题，也就是将求解多项式方程组的根转化为求解矩阵的特征值，这一转化为我们求解多项式方程组这一难题铺平了的道路，使得我们从数值计算的角度上可以更有效地求解方程组。
对于给定的多项式理想I，我们可以定义一个商空间A = k[x1, . . . , xs]/I,这里k[x1, . . . , xs] 以x1, . . . , xs为自变量的的多项式环，同时I 是由输入多项式组F = {f1, . . . , fm}构成的理想。这里我们假定I是一个有限集合，针对F的Gr¨obner 基G(对于给定的项序）已经可以计算，令lt(f)代表多项式f的首项，把项的集合定义为：
正规集在符号计算当中有着重要的意义，所以我们先给出关于正规集的几条重要的性质：
性质 2.1: (正规集的性质)
1. 正规集的维数就等于多项式方程组根的个数。
2. 对于给定项序，我们可以通过写出所有不能被lt(G)模尽的单项式来得到B = {t1, . . . , tn}的一组基。
. 我们采用”[ ]” 代表算子”mod I ” ,那么对于任何 f ∈ k[x1, . . . , xs],将f与正规
集N中的每个基[ti]相乘，再取模[ ]，我么就得到：
称为关于多项式f的相伴矩阵。很显然，只要知道正规集B的一组基[t1], . . . , [tn]，就可以计算aij(f) 。
第 3章 全局优化中的改进矩阵算法............26
3.1 问题介绍............26
3.2 匹配问题中的匈牙利算法............ 28
3.3 最优既约Gr¨obner 基的匹配构造............29
第 4章 矩阵收缩算法.............. 37
4.1 改进的多项式一阶条件.............. 37
4.2 数值结果.............. 39
第 5章 同伦初始系统的优化与预处理...................................... 43
5.1 准备知识..........................43
5.2 同伦初始系统的构造........................... 45
第 5章 同伦初始系统的优化与预处理
本章中，我们给出一个基于前两章的符号数值混合算法的应用：构造用于求解多项式方程组的同伦算法的初始系统。多年来，同伦算法在处理奇异解的时候存在很多问题，本章的方法的优势就在于能够成功地避免跟踪过程中的奇异解，从而使得同伦跟踪的解得到的更加准确。与此同时，我们的方法也节省了大部分的跟踪路径，从而节省了一定的计算量。数值结果显示，我们的算法与同伦算法平台PHCPACK相比，具有一定的优势。
5.1 准备知识
多项式方程组的求解问题在科学和工程上是一个广泛存在的问题，例如计算机辅助设计，信号处理等等。符号算法和数值算法是两类解决多项式方程组的有效工具，但是，每种方法都有各自的不足：符号算法，比如Gr¨obner 基理论和结式方法[6, 36]，然而有时符号算法计算过程比较复杂，很难计算大规模问题；但是数值方法，比如同伦方法虽然能将计算的问题规模提升，但是在计算过程中也面临着一些实际问题，比如多齐次同伦和混合体积的计算，奇异解的处理等等。
和符号算法相比，数值方法处理规模稍大的问题更有效，我们熟知的一些数值软件，比如PHCPACK和HOMPACK [11, 27]在本领域一直受到极大的关注，但是它们也面临着一些计算难题：跟踪路径失败，奇异解，跟踪参数的设置等等。在诸多困难当中，最难于处理的就是如何来控制和避免奇异解的出现，这也是本文要处理的主要问题。
对于同伦H(x,t) = 0，我们优很多种数值技巧可以被用来跟踪同伦路径，这些法则可以保证在跟踪过程中随着参数t的递增，跟踪曲线不会回返，不会彼此交叉，彼此分离并且具有有限的路径长度。然而，这一跟踪过程中最困难的就是最后的跟踪过程，也就是当t靠近0时，这些跟踪曲线往往会遇到奇异的问题。奇异解往往导致跟踪解的准确性有一定偏差，进而影响孤立解的结构和性质，由此可知，避免奇异性对于同伦方法来说具有极其重要的作用，实际上，如果恰当的同伦系统被构造出来的话，某些奇异解就可以成功地避免，否则，不管跟踪多少步骤，奇异解的准确性仍旧难以接受。
第 6章 结论
论文的主要结论和创新点
本论文的创新点如下：
1. 本文给出一类求解多项式优化问题的有效算法：在Hanzon-Jibetean算法的基础上，我们给出了一类改进矩阵算法，使得在Hanzon-Jibetean算法中所无法避免的大规模相伴矩阵得以化简，从而有效的降低了相伴矩阵的规模，并且更进一步使得算法的计算规模得以提升。在改进的算法中，本文采用匈牙利匹配算法求解辅助多项式的最优匹配，在确保免于计算复杂的Gr¨obner基的同时，将辅助多项式的次数降到最低，从而实现由多项式次数乘积决定的相伴矩阵的规模最小，为后续的计算多项式极值提供了极大的便利。
2. 本文在改进矩阵算法的基础上，给出了一类多项式优化的矩阵收缩算法。该类算法将求解多项式方程组的问题转化为求解线性特征值的问题，由于在这一过程中需用到求解多项式的一阶条件，对于多变量高次数的非线性问题我们需要求解多个特征值问题，在此我们给出一个新形势的一阶条件，从而把原来需要求解多个特征值的问题转化成只需求解一个特征值的问题，在实际计算中，这一新的算法在很大程度上提高了原算法的效率。
3. 针对上述改进矩阵算法，本文最后给出了其在同伦算法的初始系统构造中的应用，这一类新构造的初始系统可以有效的避免奇异解的数量，从而使得同伦算法的跟踪路径减少，算法的效率得以提升。
未来工作展望
对于现有的多项式改进矩阵算法，解的近似程度还需进一步加以刻画，对于系数变化的多项式系统，已经有了一些工作来分析近似解的精确性，但是基于本文给出的改进矩阵算法，由于算法需要增加变量的次数，由此引发的次数变化所导致的近似解的变化还无法深层次的衡量，对于此类变次数的多项式系统的近似解分析将是我们下一步研究的方向。
参考文献（略）