多项式优化和凸代数几何中的若干问题研究

来源 :中国科学院大学 | 被引量 : 0次 | 上传用户:luoboge
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
多项式优化在凸优化,代数几何和图论等领域具有广泛的应用.多项式优化问题可以松弛为基于矩量矩阵的半正定规划问题序列.这个半正定规划问题序列称为矩量矩阵松弛序列。矩量矩阵松弛问题的对偶问题是平方和松弛问题.当可行集有界时,矩量矩阵松弛和平方和松弛问题的最优值收敛到多项式优化问题的最优值.在实代数几何中,基于矩量矩阵的半正定规划方法可以用来计算理想的实根理想。代数几何理论可以用来研究多项式优化问题的代数结构.一些符号算法可以计算多项式优化问题的最优值。然而,对于非负多项式的结构,半代数集表示的复杂性和高效性的相互关系,经典的代数方法面临着挑战.凸性提供了一个新的观点和框架来解决这些问题.这个领域称为凸代数几何.在凸代数几何中,有很多重要的问题被深入研究。例如通过基于矩量矩阵的谱多面体来近似半代数集的闭凸包问题,凸半代数集和谱多面体投影的等价表示问题以及通过代数次数衡量多项式优化问题的代数复杂度问题等。  本文主要研究凸代数几何以及多项式优化中的若干问题。第一个问题是给定实系数多项式环中的理想,如何计算它的实根理想.一个基于准素分解的符号方法可以用来计算它的实根理想.当它的实根理想是零维时,一个基于矩量矩阵松弛的数值算法可以求解它的实根理想.平坦扩张条件是这个算法的终止条件.当它的实根理想是正维时,平坦扩张条件不满足.基于偏微分方程中的对合理论,我们提出一个新的终止条件.当终止条件满足时,算法返回一个介于它和它的实根理想之间的理想的Pommaret基.在一些假设下,算法返回它的实根理想的生成元。第二个问题是给定一个基本闭半代数集,如何计算它的闭凸包。当半代数集有界时,Theta体序列和Lasserre半正定表示序列可以收敛到它的闭凸包.当半代数集无界时,Theta体序列和Lasserre半正定表示序列的收敛性无法保证.我们将半代数集映射到一个高维空间中的半代数集,然后将它投影到这个高维空间的单位球上,进而将无界半代数集的凸包求解问题转换成为有界的情形。构造了推广Theta体序列和推广Lasserre半正定表示序列.假设半代数集在无穷远处是闭的并且它在高维空间中的像所生成的闭凸锥是尖的闭凸锥,我们构造的推广Theta体序列和推广Lasserre半正定表示序列可以收敛到半代数集的闭凸包.这两个假设条件对收敛性是必要的.如果有一个假设条件不满足,收敛性可能不成立。第三个问题是参数化多项式优化问题的求解.在参数化多项式优化问题中,对任意的参数值,相应的多项式优化问题存在一个最优值.利用实代数几何中的Tariski定理可以说明最优值是参数值的半代数函数.这个半代数函数记作最优值函数.如何利用多项式方程来描述最优值函数?当优化问题的可行集不可约,光滑并且有界时,对偶仿射簇可以用来求解最优值函数图像的Zariski闭包.当可行集有界并且不光滑时,我们构造了对偶仿射簇序列.序列中对偶仿射簇的并可以用来包含最优值函数的图像.当可行集光滑,无界并且可行集的闭凸包不包含直线时,通过广义关键值理论,我们仍然可以利用对偶仿射簇来描述最优值函数图像的Zariski闭包.我们设计一个基于极仿射簇的算法的参数化形式.这个参数化算法返回一个多项式序列,使得对任意的参数值,在序列中存在一个多项式可以被约化为非零的单变元多项式并且它的根包含特定化优化问题的最优值。最后一个问题是刻画一个闭凸集的锥举起.我们将凸体的锥举起定理扩展到一般的闭凸集情形.给定一个闭凸集,根据它是否满维,是否是一个锥的平移,是否包含直线,我们定义相应的松弛算子.我们推广了锥举起的定义:闭凸集不仅是一个给定闭凸锥的仿射切片在线性映射下的像.而且它的回收锥是闭凸锥的线性切片在相同线性映射下的像。给定一个闭凸集,我们利用推广松弛算子的锥分解来刻画它的推广锥举起。
其他文献
该文针对时间序列搜索算法预测的不足,提出了一种定量的预测算法.利用时序数据的相似性搜索的结果,构造出相应的矩阵,求出相应的比例规则进行预测的算法,从而使预测由定性向
该文利用一种全新的方法证明了如下定理:设G是一个不含三角形的图,如果对G的每一个顶点X,N[x]是优美图,且Hx是不含导出路P的二分图,则G是圈优美的.其中N[x]{y:y~x,y∈V}∪={X
张量是高阶数组,在二阶情形退化为矩阵,在一阶情形退化为向量。众所周知,矩阵的特征值在很多实际问题中有重要的应用.特征值也是张量的基本性质之一,在实际应用问题和研究张量的
五轴数控加工中路径规划是CAM的核心问题之一。如何生成最优路径曲线是一个全局优化问题,一般情况下很难求解全局最优路径。本文基于平底刀提出一种新的路径生成方法。首先对
同一个二维景物,摄像机在不同地点、从不同角度拍摄,得到的图像的几何形状不同.任意两幅图像间的几何变形可用射影变换来描述;当摄像机与景物之间的距离远远地大于景物的尺寸
叶圣陶先生曾经说过:“教是为了不教。”教,一方面是指教师在教学过程中充分发挥主导作用,引导学生学习语文知识;另一方面是教师教给学生求得这些知识的方法,使学生逐渐摆脱
学位
序列密码作为三大密码体制之一,在密码学中有着重要的地位。与分组密码和公钥密码相比,序列密码具有加解密速度快、实现规模小,功耗低等优点。早期序列密码主要被用于部队、政府
该文分为两部分:第一部分是关于组合网格法的研究;第二部分是对非结构化网格自动生成的研究.第一部分的组织结构如下:首先介绍有限元方法的数学理论基础,包括Sobolev空间理论
该文讨论直线上分形的定位及其Hausdorff测度的计算问题.定义了一类Cantor结构,并指出由广义Cantor结构所确定的分形,即广义Cantor集,的s维Hausdorff测度即为该分形直径的s次