悠闲数学娱乐论坛(第2版) » Mathematica » 将多项式表为SOS

hbghlyj 发表于 2021-5-15 00:21

将多项式表为SOS

[i=s] 本帖最后由 hbghlyj 于 2021-5-28 15:55 编辑 [/i]

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

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

conversionMatrix[polys_, vars_] :=
Module[{aa, coords, pmat, len = Length[polys], newpolys, mgb, gb,
   convmat, fvar, rvars}, coords = Array[aa, len + 1];
  fvar = First[coords];
  rvars = Rest[coords];
  pmat = Transpose[Join[{polys}, IdentityMatrix[len]]];
  newpolys = pmat.coords;
  mgb = moduleGroebnerBasis[newpolys, vars, coords];
  gb = mgb /. Join[{fvar -> 1}, Thread[rvars -> 0]] /. 0 :> Sequence[];
  convmat = Select[mgb, ! FreeQ[#, fvar] &] /. fvar -> 0;
  {gb, convmat /.
    Thread[rvars -> Table[UnitVector[len, j], {j, len}]]}]
vars = Variables[ee];
diffsq = Flatten[
   Table[(vars[[j]] - vars[[i]])^2, {j, 2, Length[vars]}, {i, 1,
     j - 1}]];
{gb, cmat} = conversionMatrix[diffsq, vars];
{vec, rem} = PolynomialReduce[ee, gb, vars];
gvec = vec.cmat;
gvec.diffsq[/code]-------
对于三元情况,我们把代码中间的两行修改为
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表示呢?
----------------------
[url=https://math.stackexchange.com/questions/2244565/sos-proof-of-the-am-gm-inequality?noredirect=1&lq=1]sos-proof-of-the-am-gm-inequality[/url]

青青子衿 发表于 2021-5-15 09:09

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=39328&ptid=7879]1#[/url] [i]hbghlyj[/i] [/b]

好神奇，马克一下{:lol:}

hbghlyj 发表于 2021-5-28 15:03

[i=s] 本帖最后由 hbghlyj 于 2021-5-28 15:53 编辑 [/i]

[url]https://sums-of-squares.github.io/sos/index.html#python[/url]
[url=https://people.cs.clemson.edu/~goddard/MINI/2011/Powers.pdf]Certificates of Positivity[/url]
我用python测试成功了:
例如$$ f(x, y):=x^{4}+4 y^{4}-4 x y^{2}+2 x^{2} y-x^{2}+y^{2}-2 y+1 $$
[attach]9737[/attach]$$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的下界。
[attach]9738[/attach]
奇怪的是MMA认为最小值是0
[attach]9739[/attach]

hbghlyj 发表于 2021-5-28 15:52

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=39492&ptid=7879]3#[/url] [i]hbghlyj[/i] [/b]
这是怎么回事呢?
这个python程序是错的吗
但是这是官网上给出的实例啊

hbghlyj 发表于 2021-7-19 19:09

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

查看完整版本: 将多项式表为SOS