On the Exactness of Lasserre Relaxations and Pure States Over Real Closed Fields
On the Exactness of Lasserre Relaxations and Pure States Over Real Closed Fields
复制标题
论实闭域上拉塞尔弛豫和纯态的精确性
DOI：
10.1007/s10208-018-9406-z
复制
发表时间：
2019
影响因子：
3
通讯作者：
M. Schweighofer
中科院分区：
文献类型：
--
作者：
T.-L. Kriel;M. Schweighofer
考虑一个具有解集的非严格多项式不等式有限系统。它的拉塞尔度松弛是原始变量中的一个自然线性矩阵不等式，每个非线性次项最多有一个附加变量。它定义了一个投射到一个包含凸半代数集合的谱面体。在最好的情况下，投影等于s的凸包。我们表明，这是非常常见的情况下，足够高的密实和“向外凸出”的边界上的凸壳。现在我们再给出一个多项式目标函数，即考虑一个多项式优化问题。它的拉瑟尔学位放松现在是一个半确定的计划。在最佳情况下，多项式优化问题的最优值与其松弛性一致。我们证明了这种情况经常发生，如果它是紧的，并且超过了依赖于描述的某些特征的边界，比如它的全局最小值的互距离。
Consider a finite system of non-strict polynomial inequalities with solution set. Its Lasserre relaxation of degreedis a certain natural linear matrix inequality in the original variables and one additional variable for each nonlinear monomial of degree at mostd. It defines a spectrahedron that projects down to a convex semialgebraic set containingS. In the best case, the projection equals the convex hull ofS. We show that this is very often the case for sufficiently highdifSis compact and “bulges outwards” on the boundary of its convex hull. Now let additionally a polynomial objective functionfbe given, i.e., consider a polynomial optimization problem. Its Lasserre relaxation of degreedis now a semidefinite program. In the best case, the optimal values of the polynomial optimization problem and its relaxation agree. We prove that this often happens ifSis compact anddexceeds some bound that depends on the description ofSand certain characteristics offlike the mutual distance of its global minimizers onS.
登录
查看更多内容
DOI：
10.1137/17m1118981
发表时间：
2016-12
期刊：
SIAM J. Appl. Algebra Geom.
影响因子：
--
作者：
C. Scheiderer
通讯作者：
C. Scheiderer
DOI：
10.1137/100801913
发表时间：
2009-11
期刊：
SIAM J. Optim.
影响因子：
--
作者：
J. Gouveia;Tim Netzer
通讯作者：
J. Gouveia;Tim Netzer
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
Sabine Burgdorf;C. Scheiderer;M. Schweighofer
通讯作者：
M. Schweighofer
带插值的偏序阿贝尔群（数学调查和专着 20）
影响因子：
0.9
作者：
F. Jellett
通讯作者：
F. Jellett
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
A. Prestel;Charles N. Delzell
通讯作者：
Charles N. Delzell