免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
Board logo

标题: 将多项式表为SOS [打印本页]

作者: hbghlyj    时间: 2021-5-15 00:21     标题: 将多项式表为SOS

本帖最后由 hbghlyj 于 2021-5-28 15:55 编辑

n元对称式$f(x_1,x_2,\cdots,x_n)$能表为SOS的必要条件是把$x_3,\cdots,x_n$都替换为$x_2$后能被$(x_1-x_2)^2$整除.

将多项式表为SOS的代码如下(弹出输入框)
  1. ee = Input[]
  2. moduleGroebnerBasis[polys_, vars_, cvars_, opts___] :=
  3. Module[{newpols, rels, len = Length[cvars], gb, j, k, rul},
  4.   rels = Flatten[Table[cvars[[j]]*cvars[[k]], {j, len}, {k, j, len}]];
  5.   newpols = Join[polys, rels];
  6.   gb = GroebnerBasis[newpols, Join[cvars, vars], opts];
  7.   rul = Map[(# :> {}) &, rels];
  8.   gb = Flatten[gb /. rul];
  9.   Collect[gb, cvars]]

  10. conversionMatrix[polys_, vars_] :=
  11. Module[{aa, coords, pmat, len = Length[polys], newpolys, mgb, gb,
  12.    convmat, fvar, rvars}, coords = Array[aa, len + 1];
  13.   fvar = First[coords];
  14.   rvars = Rest[coords];
  15.   pmat = Transpose[Join[{polys}, IdentityMatrix[len]]];
  16.   newpolys = pmat.coords;
  17.   mgb = moduleGroebnerBasis[newpolys, vars, coords];
  18.   gb = mgb /. Join[{fvar -> 1}, Thread[rvars -> 0]] /. 0 :> Sequence[];
  19.   convmat = Select[mgb, ! FreeQ[#, fvar] &] /. fvar -> 0;
  20.   {gb, convmat /.
  21.     Thread[rvars -> Table[UnitVector[len, j], {j, len}]]}]
  22. vars = Variables[ee];
  23. diffsq = Flatten[
  24.    Table[(vars[[j]] - vars[[i]])^2, {j, 2, Length[vars]}, {i, 1,
  25.      j - 1}]];
  26. {gb, cmat} = conversionMatrix[diffsq, vars];
  27. {vec, rem} = PolynomialReduce[ee, gb, vars];
  28. gvec = vec.cmat;
  29. gvec.diffsq
复制代码
-------
对于三元情况,我们把代码中间的两行修改为
vars = {a, b, c};
diffsq = {(b - c)^2, (c - a)^2, (a - b)^2};
检验SOS定理的条件的代码如下:
{Sa,Sb,Sc}=gvec;
AllTrue[{Sb, Sb + Sc, Sb + Sa},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sa, Sa + Sb, Sa + Sc},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sc, Sc + Sb, Sa + Sc},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sa, Sb, Sc},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sa + Sb + Sc, Sa Sb + Sb Sc + Sc Sa},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sa, Sc, Sa + 2 Sb, Sc + 2 Sb},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sb, Sc, Sb + 2 Sa, Sc + 2 Sa},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sb, Sa, Sb + 2 Sc, Sa + 2 Sc},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sc, Sa, a^2 Sb + b^2 Sa},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sb, Sa, b^2 Sa + a^2 Sb},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
-------
注意到恒等式$\sum(a-b)(a-c)(b-c)^2=0$
所以四次或以上多项式的SOS表示都不唯一
这个恒等式可以推广为$\sum(a-b)(a-c)(b-c)^2 g(a,b,c)=0$,如果g(a,b,c)是关于b,c对称的多项式.
另外$S_a(b-c)^2+S_b(c-a)^2=(S_a-k(c-a)^2)(b-c)^2+(S_b+k(b-c)^2)(c-a)^2$①
多项式的SOS表示不唯一的问题可以归结为"把0整理成SOS有多少形式"
若只考虑轮换的话就不存在①这个问题
$g(a,b,c)(b-c)^2+g(b,c,a)(c-a)^2+g(c,a,b)(a-b)^2=0$
待定系数然后解线性方程组得g为齐次二次多项式时的全部解为
$g(a,b,c)=a^2 + k b^2 - k c^2 - (2 k+1) a b +
   b c + ( 2 k-1) a c$
例如$\sum (a^2 + b^2 - c^2 - 3 a b + b c + c a) (b -c)^2=0$
g为齐次三次多项式时的全部解为$g(a,b,c)=a^3+ k_1b^3-k_1c^3+k_2a^2 b+ k_3a b^2 - (5 k_1+2 k_2+3 k_3+3)a^2 c+ (5 k_1+k_2+3 k_3+2)a b c+ (5 k_1+k_2+2 k_3+1)a c^2-(3 k_1+k_2+2 k_3+1)b^2 c -(2 k_1+k_3)b c^2 $
g为齐次四次多项式时的全部解为$a^4+ k_1 b^4-k_1 c^4 +a^3 b k_2+a^3 c (-k_2-1)+a b^2 c \left(-\frac{k_1}{2}-k_2-\frac{1}{2}\right)+a b^3 \left(-\frac{3 k_1}{2}-\frac{1}{2}\right)+a b c^2 \left(\frac{k_1}{2}+k_2+\frac{1}{2}\right)+a c^3 \left(\frac{3 k_1}{2}-\frac{1}{2}\right)+b^3 c \left(\frac{k_1}{2}+\frac{1}{2}\right)+b c^3 \left(\frac{1}{2}-\frac{k_1}{2}\right)$
然后考虑非轮换的情形:
例如$(c-a)^{2}\left(\frac{a^{2}}{2}+\frac{a c}{2}-b^{2}\right)+(b-a)^{2}\left(-\frac{a^{2}}{2}-a b+\frac{a c}{2}+c^{2}\right)+(c-b)^{2}\left(-\frac{a^{2}}{2}+a b-\frac{a c}{2}\right)=0$
0的非轮换的多项式SOS表示是否均能通过①的方法化为轮换的多项式SOS表示呢?
----------------------
sos-proof-of-the-am-gm-inequality
作者: 青青子衿    时间: 2021-5-15 09:09

回复 1# hbghlyj

好神奇,马克一下
作者: hbghlyj    时间: 2021-5-28 15:03

本帖最后由 hbghlyj 于 2021-5-28 15:53 编辑

https://sums-of-squares.github.io/sos/index.html#python
Certificates of Positivity
我用python测试成功了:
例如$$ f(x, y):=x^{4}+4 y^{4}-4 x y^{2}+2 x^{2} y-x^{2}+y^{2}-2 y+1 $$
新建位图图像.png
2021-5-28 15:08
$$f(x,y)=1.378 (-0.532 x^2 - 0.266 x y + y^2)^2+2.224 (0.488 x + 0.013 x^2 + 0.007 x y - y^2)^2 +
  1. (1 - 0.772 x^2 - 1. y + 0.114 x y - 0.428 y^2)^2 + 0.86 (-0.133 x + 0.125 x^2 + 0.998 y - x y - 0.499 y^2)^2 $$
实际上$$f(x,y)=\left(-x^2-y+1\right)^2+ \left(x-2y^2\right)^2$$
下面是网页中的Example 3:$p = x^4+x^2-3 x^2 y^2+y^6$
通过寻找最大的t使得p-t是SOS,我们可以找到p的下界。
新建位图图像.png
2021-5-28 15:30

奇怪的是MMA认为最小值是0
新建位图图像.png
2021-5-28 15:42


图片附件: 新建位图图像.png (2021-5-28 15:08, 35.01 KB) / 下载次数 535
http://kuing.orzweb.net/attachment.php?aid=9737&k=a1cf0b97380f87788d6e7b695405d523&t=1711725056&sid=pHPtD8



图片附件: 新建位图图像.png (2021-5-28 15:30, 30.53 KB) / 下载次数 547
http://kuing.orzweb.net/attachment.php?aid=9738&k=ebb4ccd077e4e0250b7185a3e223ca5b&t=1711725056&sid=pHPtD8



图片附件: 新建位图图像.png (2021-5-28 15:42, 7.1 KB) / 下载次数 521
http://kuing.orzweb.net/attachment.php?aid=9739&k=924ab0e4d690eb035e05689c0a930113&t=1711725056&sid=pHPtD8


作者: hbghlyj    时间: 2021-5-28 15:52

回复 3# hbghlyj
这是怎么回事呢?
这个python程序是错的吗
但是这是官网上给出的实例啊
作者: hbghlyj    时间: 2021-7-19 19:09

这个最小值应该是0,MMA是对的




欢迎光临 悠闲数学娱乐论坛(第2版) (http://kuing.orzweb.net/) Powered by Discuz! 7.2