论文部分内容阅读
多项式优化在凸优化,代数几何和图论等领域具有广泛的应用.多项式优化问题可以松弛为基于矩量矩阵的半正定规划问题序列.这个半正定规划问题序列称为矩量矩阵松弛序列。矩量矩阵松弛问题的对偶问题是平方和松弛问题.当可行集有界时,矩量矩阵松弛和平方和松弛问题的最优值收敛到多项式优化问题的最优值.在实代数几何中,基于矩量矩阵的半正定规划方法可以用来计算理想的实根理想。代数几何理论可以用来研究多项式优化问题的代数结构.一些符号算法可以计算多项式优化问题的最优值。然而,对于非负多项式的结构,半代数集表示的复杂性和高效性的相互关系,经典的代数方法面临着挑战.凸性提供了一个新的观点和框架来解决这些问题.这个领域称为凸代数几何.在凸代数几何中,有很多重要的问题被深入研究。例如通过基于矩量矩阵的谱多面体来近似半代数集的闭凸包问题,凸半代数集和谱多面体投影的等价表示问题以及通过代数次数衡量多项式优化问题的代数复杂度问题等。 本文主要研究凸代数几何以及多项式优化中的若干问题。第一个问题是给定实系数多项式环中的理想,如何计算它的实根理想.一个基于准素分解的符号方法可以用来计算它的实根理想.当它的实根理想是零维时,一个基于矩量矩阵松弛的数值算法可以求解它的实根理想.平坦扩张条件是这个算法的终止条件.当它的实根理想是正维时,平坦扩张条件不满足.基于偏微分方程中的对合理论,我们提出一个新的终止条件.当终止条件满足时,算法返回一个介于它和它的实根理想之间的理想的Pommaret基.在一些假设下,算法返回它的实根理想的生成元。第二个问题是给定一个基本闭半代数集,如何计算它的闭凸包。当半代数集有界时,Theta体序列和Lasserre半正定表示序列可以收敛到它的闭凸包.当半代数集无界时,Theta体序列和Lasserre半正定表示序列的收敛性无法保证.我们将半代数集映射到一个高维空间中的半代数集,然后将它投影到这个高维空间的单位球上,进而将无界半代数集的凸包求解问题转换成为有界的情形。构造了推广Theta体序列和推广Lasserre半正定表示序列.假设半代数集在无穷远处是闭的并且它在高维空间中的像所生成的闭凸锥是尖的闭凸锥,我们构造的推广Theta体序列和推广Lasserre半正定表示序列可以收敛到半代数集的闭凸包.这两个假设条件对收敛性是必要的.如果有一个假设条件不满足,收敛性可能不成立。第三个问题是参数化多项式优化问题的求解.在参数化多项式优化问题中,对任意的参数值,相应的多项式优化问题存在一个最优值.利用实代数几何中的Tariski定理可以说明最优值是参数值的半代数函数.这个半代数函数记作最优值函数.如何利用多项式方程来描述最优值函数?当优化问题的可行集不可约,光滑并且有界时,对偶仿射簇可以用来求解最优值函数图像的Zariski闭包.当可行集有界并且不光滑时,我们构造了对偶仿射簇序列.序列中对偶仿射簇的并可以用来包含最优值函数的图像.当可行集光滑,无界并且可行集的闭凸包不包含直线时,通过广义关键值理论,我们仍然可以利用对偶仿射簇来描述最优值函数图像的Zariski闭包.我们设计一个基于极仿射簇的算法的参数化形式.这个参数化算法返回一个多项式序列,使得对任意的参数值,在序列中存在一个多项式可以被约化为非零的单变元多项式并且它的根包含特定化优化问题的最优值。最后一个问题是刻画一个闭凸集的锥举起.我们将凸体的锥举起定理扩展到一般的闭凸集情形.给定一个闭凸集,根据它是否满维,是否是一个锥的平移,是否包含直线,我们定义相应的松弛算子.我们推广了锥举起的定义:闭凸集不仅是一个给定闭凸锥的仿射切片在线性映射下的像.而且它的回收锥是闭凸锥的线性切片在相同线性映射下的像。给定一个闭凸集,我们利用推广松弛算子的锥分解来刻画它的推广锥举起。