Semidefinite programming relaxations for semialgebraic problems
Semidefinite programming relaxations for semialgebraic problems
复制标题
DOI：
10.1007/s10107-003-0387-5
复制
发表时间：
2003-05-01
影响因子：
2.7
通讯作者：
Parrilo, PA
中科院分区：
文献类型：
--
作者：
Parrilo, PA
引入了半代数问题的凸松弛层次结构。对于可归结为有限个多项式等式和不等式的问题，展示了如何构建一个完整的多项式规模的半定规划条件族来证明不可行性。所使用的主要工具是多元多项式平方和分解的半定规划公式，以及实代数几何的一些结果。这些技术为寻找正性定理的有界次数解提供了一种建设性方法，并通过来自不同应用领域的例子进行了说明。
A hierarchy of convex relaxations for semialgebraic problems is introduced. For questions reducible to a finite number of polynomial equalities and inequalities, it is shown how to construct a complete family of polynomially sized semidefinite programming conditions that prove infeasibility. The main tools employed are a semidefinite programming formulation of the sum of squares decomposition for multivariate polynomials, and some results from real algebraic geometry. The techniques provide a constructive approach for finding bounded degree solutions to the Positivstellensatz, and are illustrated with examples from diverse application fields.