实代数几何方法及其在多项式优化中的应用

本项目旨在通过实代数几何中有效方法, 处理非线性的优化和多目标优化问题，其中目标函数为实多项式（或有理）函数，且可行区域为半代数子集。现存的一些算法，在最优解存在的假定下只能给出其逼近值，并不能有效地判定最优解的存在性。本项目将研究多元多项式和有理函数的全局下确界和全局最小值，提出精确地计算全局下确界的算法，并在下确界为有限的情况下判定该下确界能否达到。在此基础上，我们将进一步研究多项式和有理函数在约束条件下的下确界和最小值。同时，我们将考虑多项式多目标优化问题，期望获得一个有效方法，以判定非控解（Pareto最优解）的存在性。此外，我们将处理其他有关问题，比如计算有理函数的半正定区间和捕获半代数集的每个半代数连通分支中至少一点。.本项目将基于著名的吴方法，建立相关的有效算法。我们将采用所谓的"区间表示法"和"有理单元表示"分别精确地表示下确界（与最小值）和最小值点（与非控解）。

本项目的任务是通过实代数几何中一些有效方法, 处理实多元多项式和实多元有理函数的优化问题。在资助期间，我们共撰写了20篇学术论文，其中15篇正式发表，其余5篇已投稿于有关学术刊物。. 本项目完成的主要研究工作如下: 提出了半代数集的“局部临界点”以及多项式与多项式升链的“修正结式”的新概念，并在理论方面建立了相关结果；提出了一些计算多元多项式和多元有理函数的全局下确界精确值的新算法，并在全局下确界为有限的情况下，给出了一个判定其可达性的方法。研究了由多项式函数的最小值点所组成的半代数连通分支，由此证明了我们的算法可在每个半代数连通分支上寻求到至少一个最小值点；研究了实多元多项式在由多项式等式所构成的约束条件下的极小化问题，提出了一个有效的算法，无需任何假定可获得有限个单元多项式, 使得受约束的下确界为某个多项式的根；随后获得相关算法，使得可求出受约束的精确下确界，判定其可达性，并在可达时求出一个最小值点；通过把不等式转化成等式，研究了实多元多项式在由多项式不等式所构成的约束条件下的极小化问题。通过捕获局部临界点，获得了一个可有效地判定给出的实多元有理函数在分母零点处是否存在极限的有效方法，并通过实赋值理论获得有关有理函数极限的进一步结果；通过多项式的正则链，提出了一个判定多项式半正定性的新方法；建立了计算等式约束下多项式在闭或开长方体上的最小值的有关算法。此外，我们研究了与实代数几何有关的一些其它问题。. 多项式和有理函数的优化是一个NP-难问题。现存的一些方法，比如半正定松弛法，未涉及可达性与求优化点，而需附加某些条件，且计算出的优化值往往是近似的。通过计算机代数系统Maple和软件Wsolve，我们的算法已编制成处理实例的通用程序。