凸代数几何中的若干问题研究

批准号:
11571350
项目类别:
面上项目
资助金额:
45.0 万元
负责人:
支丽红
依托单位:
学科分类:
A0410.算法复杂性与近似算法
结题年份:
2019
批准年份:
2015
项目状态:
已结题
项目参与者:
郭峰、王础、郝志伟、杨志红、姜文嵘
国基评审专家1V1指导 中标率高出同行96.8%
结合最新热点,提供专业选题建议
深度指导申报书撰写,确保创新可行
指导项目中标800+,快速提高中标率
微信扫码咨询
中文摘要
本项目主要运用凸分析、半定规划和实代数几何中的关键理论和工具研究基本半代数集的凸包的谱多面体表示或近似、基本半代数集上的参数化优化问题、凸集的提升和锥分解以及(半)代数系统求解。 当所考虑的集合紧致和光滑时, 前三个问题的解决主要是基于正零点定理、半正定松弛、KKT条件和凸集的极点表示等。而在非紧致或非光滑情形,正零点定理、KKT条件等可能不成立。本项目将重点研究如何应用提升、投影和分解等技巧以及凸分析和实代数几何中的关键理论和技术将紧致光滑情形下上述问题的相关结论推广到一般情形。当(半)代数系统有无穷多实解时,给出其矩量矩阵半定松弛的终止准则并得到系统相应实根理想的一组基。
英文摘要
The project will focus on studying some problems in convex algebraic geometry using convex analysis, semidefinite programming and real algebraic geometry. We work on problems: spectrahedral representations of convex hulls of basic semalgebraic sets; optimizing a parameteric function over a (semi)-algebraic set; lifting of convex sets and cone factorizations; certificates for semidefinite relaxations in computing positive-dimensional real radical ideals. For the first three problems, when the considered set is smooth and compact, some important results have already been obtained via Positivstellensatz, semidefinite relaxations, KKT conditions and representations of convex sets by extreme points. However, when the considered set is nonsmooth or not compact then the Positivstellensatz and KKT condition might be invalid. This project will apply lifting, projection and decomposition techniques and known results in convex analysis and real algebraic geometry to extend results obtained in smooth and compact case to general case. For a (semi)algebraic system with infinitely many real solutions, we will work on practical termination criteria of its moment relaxations and compute a basis of the real radical ideal corresponding to the input system.
本项目主要运用凸分析、半定规划和实代数几何中的关键理论和工具研究基本半代数集的凸包的谱多面体表示或近似、基本半代数集上的参数化优化问题、凸集的提升和锥分解以及(半)代数系统求解。 当所考虑的集合紧致和光滑时, 前三个问题的解决主要是基于正零点定理、半正定松弛、KKT条件和凸集的极点表示等。而在非紧致或非光滑情形,正零点定理、KKT条件等可能不成立。本项目重点研究了如何应用提升、投影和分解等技巧以及凸分析和实代数几何中的关键理论和技术将紧致光滑情形下上述问题的相关结论推广到一般情形。 我们给出了非紧致基本半代数集凸包具有谱多面体表示或逼近的充要条件。我们将凸体的锥举起定理扩展到一般的闭凸集情形. 应用相应的松弛算子来刻画它的推广锥举起。我们研究了实代数簇上线性函数的优化问题,证明了如果光滑的不可约实代数簇的凸闭包的径向锥是有向的,则其相应对偶代数簇的定义的不可约多项式也是优化问题的最优值函数。相应的结论也推广到了非光滑的情形。我们研究了多项式函数的退化关键点类型的判定问题,通过定义和计算相应的可信半径,将此问题转化为零维系统的实根孤立问题,从而给出了符号的判定方法;对于线性半无限多项式规划问题,基于正零点定理,我们分别给出问题的线性规划和半定规划松弛方法,对于更广义的凸半无限多项式规划问题,我们给出了其可行域的近似半定表示方法,并进一步给出了该类问题的半定规划松弛方法。我们通过将几何对合理论与半正定矩量矩阵的性质相结合,提出了正维情形下半正定松弛方法终止的判定准则。我们还给出一个概率算法计算理想的实根理想的所有极小素理想的生成元,算法的复杂度关于变元个数是单指数的。对于一般的情形,我们给出一个概率算法计算实根理想的所有素理想的有理参数化表示,算法的复杂度关于理想的维数是双指数的,但对于变量是单指数的。相应的算法也被推广到一般半代数集情形。
期刊论文列表
专著列表
科研奖励列表
会议论文列表
专利列表
On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems
关于凸多项式不等式的半无限系统和多项式优化问题
DOI:--
发表时间:--
期刊:Computational Optimization and Applications
影响因子:2.2
作者:Feng Guo;Xiaoxia Sun
通讯作者:Xiaoxia Sun
Semidefinite programming relaxations for linear semi-infinite polynomial programming
线性半无限多项式规划的半定规划松弛
DOI:--
发表时间:2015-09
期刊:Pacific Journal of Optimization
影响因子:0.2
作者:Feng Guo;Xiaoxia Sun
通讯作者:Xiaoxia Sun
DOI:10.1145/3208976.3209002
发表时间:2018
期刊:Proceedings of the 2018 ACM on International Symposium on Symbolic and Algebraic Computation
影响因子:--
作者:Mohab Safey El Din;Zhi Hong Yang;Lihong Zhi
通讯作者:Lihong Zhi
Polynomial Time Interactive Proofs for Linear Algebra with Exponential Matrix Dimensions and Scalars Given by Polynomial Time Circuits
具有由多项式时间电路给出的指数矩阵维数和标量的线性代数的多项式时间交互式证明
DOI:10.1145/3087604.3087640
发表时间:2017-07
期刊:Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation
影响因子:--
作者:Jean-Guillaume Dumas;Erich L. Kaltofen;Gilles Villard;Lihong Zhi
通讯作者:Lihong Zhi
Computing real radicals and S-radicals of polynomial systems
计算多项式系统的实根式和 S 根式
DOI:10.1016/j.jsc.2019.10.018
发表时间:2021-01
期刊:Journal of Symbolic Computation
影响因子:0.7
作者:Mohab Safey El Din;Zhihong Yang;Lihong Zhi
通讯作者:Lihong Zhi
非线性解析系统孤立奇异根的隔离和近似重根的精化
- 批准号:--
- 项目类别:面上项目
- 资助金额:52万元
- 批准年份:2020
- 负责人:支丽红
- 依托单位:
基于符号-数值混合计算的误差可控算法及应用
- 批准号:91118001
- 项目类别:重大研究计划
- 资助金额:260.0万元
- 批准年份:2011
- 负责人:支丽红
- 依托单位:
符号和数值混合方法求解多项式方程组
- 批准号:10871194
- 项目类别:面上项目
- 资助金额:21.0万元
- 批准年份:2008
- 负责人:支丽红
- 依托单位:
符号和数值混合计算
- 批准号:10401035
- 项目类别:青年科学基金项目
- 资助金额:11.0万元
- 批准年份:2004
- 负责人:支丽红
- 依托单位:
国内基金
海外基金
