Schmüdgenの定理(Schmüdgen's theorem)とは、多項式の不等式で定まる $\mathbb R^n$ のコンパクトな集合 $K$ の上で正の多項式が、定義の多項式たちの積に平方の和を掛けたものの和として書ける、という実代数幾何学の表示定理である。Putinarの定理は、生成される 2 次加群が Archimedes 性をもてば、積を使わず各定義多項式に平方の和を掛けた和で書けるとする定理である。2 次加群の上で $0$ 以上の線形汎関数は、掛け算作用素のスペクトルを通じて $K$ の上の測度で表される。応用として、多項式の最小値を半正定値計画の列で近似する Lasserre の方法が収束する。
前提知識: 実代数幾何学, Hahn–Banachの定理, GNS構成, 可換Gelfand–Naimark定理, Riesz–Markov–角谷の表現定理
Schmüdgenの定理(Schmüdgen's theorem)とは、多項式の不等式 $g_1\ge0,\dots,g_m\ge0$ で定まる $\mathbb R^n$ の集合 $K$ がコンパクトなとき、$K$ の上で正の多項式 $p$ は
$$
p=\sum_{I\subset\{1,\dots,m\}}\sigma_I\prod_{j\in I}g_j\qquad(\sigma_I\text{ は多項式の平方の和})
$$
の形に書ける、という定理である(Schmüdgen、Sch91)。右辺の形の多項式は明らかに $K$ の上で $0$ 以上なので、この式は「$p\ge0$ on $K$」の代数的な証明書である。Putinar(Put93)は、$g_j$ の積を使わない $p=\sigma_0+\sum_j\sigma_jg_j$ の形の表示を、生成元に Archimedes 性という条件を課して示した。これが Putinarの定理 である。
この記事では次を証明する。Archimedes 性をもつ 2 次加群の上で $0$ 以上で、$1$ での値が $1$ の線形汎関数は、$K$ の上の確率測度で表される(thm-sch-measure)。これと Hahn–Banach の議論から Putinar の定理が出る(thm-sch-putinar)。$K$ がコンパクトなら積をすべて許した前順序は Archimedes 性をもち(thm-sch-archimedean)、Schmüdgen の定理が従う(thm-sch-main)。応用として、多項式の最小値を 半正定値計画 の列で近似する Lasserre の方法の収束を示す(cor-sch-lasserre)。
Positivstellensatz を含む分野の全体は 実代数幾何学 が扱い、この記事はコンパクトな集合の上の表示に絞る。
$\mathbb R[x]:=\mathbb R[x_1,\dots,x_n]$ とし、多項式の平方の有限和の全体を $\Sigma$ と書く。$g_1,\dots,g_m\in\mathbb R[x]$ を固定し、
$$
K:=\{x\in\mathbb R^n\mid g_1(x)\ge0,\dots,g_m(x)\ge0\}
$$
とおく。$I\subset\{1,\dots,m\}$ について $g_I:=\prod_{j\in I}g_j$($g_\emptyset:=1$)とする。
$\mathbb R[x]$ の部分集合 $M$ が $1\in M$、$M+M\subset M$、すべての $h\in\mathbb R[x]$ と $f\in M$ について $h^2f\in M$ を満たすとき、$M$ を 2 次加群 という。$g_1,\dots,g_m$ の生成する 2 次加群と前順序を
$$
M(g):=\Sigma+\Sigma g_1+\dots+\Sigma g_m,\qquad T(g):=\sum_{I\subset\{1,\dots,m\}}\Sigma g_I
$$
で定める。$T(g)$ は積でも閉じる(前順序)。
$T(g)$ は $2^m$ 個の $g_I$ の生成する 2 次加群であり、$\Sigma\subset M(g)\subset T(g)$ で、それらの元はどれも $K$ の上で $0$ 以上である。
2 次加群 $M$ が Archimedes 性 をもつとは、ある実数 $N$ について $N-(x_1^2+\dots+x_n^2)\in M$ となることをいう。
$M(g)$ が Archimedes 性をもてば $K$ は半径 $\sqrt N$ の閉球に含まれ、コンパクトである。逆は成り立たない(反例の表の 3 行目)。
$M(g)$ が Archimedes 性をもつとする。$K$ の上で $p>0$ となる $p\in\mathbb R[x]$ は $M(g)$ に属する。すなわち $\sigma_0,\dots,\sigma_m\in\Sigma$ によって $p=\sigma_0+\sigma_1g_1+\dots+\sigma_mg_m$ と書ける。
証明は、有界な元の補題と測度による表示を準備したあと、節「Putinar の定理の証明」で行う。
$K$ がコンパクトとする。$K$ の上で $p>0$ となる $p\in\mathbb R[x]$ は $T(g)$ に属する。
Schmüdgen の定理は、$T(g)$ が $g_I$ たちの生成する 2 次加群であることから、「$K$ がコンパクトなら $T(g)$ は Archimedes 性をもつ」(thm-sch-archimedean)と Putinar の定理の議論を合わせて得られる。
$M$ を 2 次加群とし、ある $N$ で $N\pm f\in M$ となる $f$ の全体を $H_M$ とする。
要点:$N-f^2\in M$ なら $f\in H_M$、$N\pm f\in M$ なら $N^2-f^2\in M$ を恒等式で示し、積を平方の差に直す。
$H_M$ が和と実数倍で閉じ、定数を含むことは定義から明らかである($N\pm f$ と $N'\pm g$ を足す。$-1$ 倍で条件は変わらない。$t>0$ 倍は $tN\pm tf=(\sqrt t)^2(N\pm f)\in M$ による)。
(a) $N-f^2\in M$ なら $f\in H_M$ である。実際 $(f\pm\tfrac12)^2=f^2\pm f+\tfrac14$ なので $N+\tfrac14\pm f=(N-f^2)+(f\pm\tfrac12)^2\in M$ である。
(b) $N>0$ で $N\pm f\in M$ なら $N^2-f^2\in M$ である。恒等式 $N^2-f^2=\frac1{2N}\bigl((N-f)^2(N+f)+(N+f)^2(N-f)\bigr)$ の右辺は平方と $M$ の元の積の和である。
(c) $f\in H_M$ なら $f^2\in H_M$ である。(b) で $N^2-f^2\in M$、また $N^2+f^2\in M$ は明らかである。
1:$f,g\in H_M$ なら $fg=\tfrac12\bigl((f+g)^2-f^2-g^2\bigr)$ で、(c) と $H_M$ が線形空間であることから $fg\in H_M$ である。
2:$N-x_i^2=\bigl(N-\sum_jx_j^2\bigr)+\sum_{j\ne i}x_j^2\in M$ なので、(a) により $x_i\in H_M$ である。1 により $H_M$ は $x_1,\dots,x_n$ と定数を含む環で、$\mathbb R[x]$ 全体である。$\square$
2 次加群 $M$ が $-1$ を含めば $M=\mathbb R[x]$ である。
任意の $f$ について $f=\bigl(\tfrac{f+1}2\bigr)^2+(-1)\bigl(\tfrac{f-1}2\bigr)^2\in M$ である。$\square$
次の定理が議論の中心である。線形汎関数 $L$ が 2 次加群の上で $0$ 以上という代数的な条件から、$K$ の上の測度を作る。
$M\supset M(g)$ を Archimedes 性をもつ 2 次加群とし、線形写像 $L\colon\mathbb R[x]\to\mathbb R$ が $L(1)=1$ と、すべての $f\in M$ について $L(f)\ge0$ を満たすとする。このとき $K$ の上の Borel 確率測度 $\mu$ で、すべての $f\in\mathbb R[x]$ について $L(f)=\int_Kf\,d\mu$ となるものがある。特に $K\ne\emptyset$ である。
Hilbert 空間. $L$ を複素係数の多項式に $L(f+ig):=L(f)+iL(g)$ で延ばし、$\langle f,h\rangle:=L(f\bar h)$ とおく($\bar h$ は係数の複素共役)。$f=a+ib$($a,b$ は実係数)について $f\bar f=a^2+b^2\in\Sigma\subset M$ なので $\langle f,f\rangle\ge0$ である。$\langle\,,\rangle$ は半正定値の Hermite 形式で、Cauchy–Schwarz の不等式により $\mathcal N:=\{f\mid\langle f,f\rangle=0\}$ は部分空間である。$\mathbb C[x]/\mathcal N$ を完備化した Hilbert 空間を $\mathcal H$ とし、$1$ の類を $e$ と書く(GNS構成 と同じ作り方である)。
掛け算作用素. lem-sch-bounded により、ある $C$ ですべての $i$ について $C-x_i^2\in M$ である。$f=a+ib$ について
$$
C\langle f,f\rangle-\langle x_if,x_if\rangle=L\bigl((C-x_i^2)(a^2+b^2)\bigr)\ge0
$$
である。したがって $x_i$ を掛ける写像は $\mathcal N$ を $\mathcal N$ に写し、商の上でノルム $\sqrt C$ 以下の作用素になり、$\mathcal H$ の有界作用素 $X_i$ に延びる。$\langle x_if,h\rangle=L(x_if\bar h)=\langle f,x_ih\rangle$ なので $X_i$ は自己共役で、$X_1,\dots,X_n$ は互いに可換である。多項式 $f$ について $f(X)e$ は $f$ の類で、$\langle f(X)e,e\rangle=L(f)$ である。
測度. $X_1,\dots,X_n$ と恒等作用素の生成する可換 C* 環を $\mathcal A$ とする。可換Gelfand–Naimark定理 により $\mathcal A$ はその指標の空間 $\Omega$ の上の連続関数の環 $C(\Omega)$ と同型である。$\chi\mapsto(\chi(X_1),\dots,\chi(X_n))$ は $\Omega$ からコンパクトな集合 $S\subset\mathbb R^n$ への同相写像で($\mathcal A$ は $X_i$ で生成されるので単射)、$f(X)$ は $S$ の上の関数 $f$ に対応する。$a\mapsto\langle ae,e\rangle$ は $C(S)$ の上の正の線形汎関数なので、Riesz–Markov–角谷の表現定理 により $S$ の上の Borel 測度 $\mu$ で $\langle ae,e\rangle=\int_S\hat a\,d\mu$ となるものがある。多項式に当てて $L(f)=\int_Sf\,d\mu$ を得る。$\mu(S)=L(1)=1$ である。
台は $K$ に入る. $x_0\in S$ で $g_j(x_0)<0$ となる点が $\mu$ の台にあったとする。$x_0$ の近傍で $g_j<-c<0$ となる $c$ と、その近傍に台をもち $\int\varphi\,d\mu>0$ となる連続関数 $0\le\varphi\le1$ をとる。Stone–Weierstrassの定理 により実係数の多項式 $h_k$ で $S$ の上一様に $h_k\to\sqrt\varphi$ となるものがある。$g_jh_k^2\in M$ なので
$$
0\le L(g_jh_k^2)=\int_Sg_jh_k^2\,d\mu\longrightarrow\int_Sg_j\varphi\,d\mu\le-c\int\varphi\,d\mu<0
$$
となり矛盾する。よって $\mu$ の台は $K\cap S$ に含まれ、$\mu$ を $K$ の上の測度とみてよい。$\square$
$M:=M(g)$ とし、$K$ の上で $p>0$ だが $p\notin M$ と仮定して矛盾を導く。lem-sch-minus-one により $-1\notin M$ である。
劣線形汎関数. $f\in\mathbb R[x]$ に対し $\rho(f):=\inf\{\lambda\in\mathbb R\mid\lambda-f\in M\}$ とおく。lem-sch-bounded によりこの集合は空でない。$\rho(f)=-\infty$ なら、$N+f\in M$ となる $N$ と合わせて、すべての $\lambda$ で $\lambda+N\in M$ となり、$-1\in M$ に反する。よって $\rho$ は実数値である。$\lambda-f,\lambda'-f'\in M$ なら $(\lambda+\lambda')-(f+f')\in M$、$t>0$ なら $t\lambda-tf\in M$ なので、$\rho(f+f')\le\rho(f)+\rho(f')$、$\rho(tf)=t\rho(f)$ である。$\lambda<0$ が $M$ に入ると $-1\in M$ となるので、$\rho(0)=0$、$\rho(1)=1$、$\rho(-1)=-1$ である。
汎関数の構成. 直線 $\mathbb Rp$ の上で $L_0(tp):=-t\rho(-p)$ とおく。$t<0$ では $L_0(tp)=\rho(tp)$、$t>0$ では $0=\rho(0)\le\rho(p)+\rho(-p)$ から $L_0(tp)\le t\rho(p)=\rho(tp)$ である。Hahn–Banachの定理(劣線形汎関数による延長の形。$\mathbb R[x]$ に位相は使わない)により、$L_0$ は線形写像 $L\colon\mathbb R[x]\to\mathbb R$ で $L\le\rho$ となるものに延びる。
矛盾. thm-sch-measure により $K$ の上の確率測度 $\mu$ で $L(f)=\int f\,d\mu$ となるものがある。$\mu$ の台はコンパクトで空でなく、$p$ はその上で正なので最小値 $c>0$ をもつ。$L(p)=\int p\,d\mu\ge c>0$ となり、$L(p)\le0$ に反する。$\square$
証明で $M(g)$ の性質として使ったのは「Archimedes 性をもつ 2 次加群で $g_j$ を含む」ことだけである。したがって同じ証明により、$M(g)$ を含む Archimedes 性をもつ任意の 2 次加群 $M$ について、$K$ の上で正の多項式は $M$ に入る。
$T:=T(g)$ と書く。$K$ がコンパクトでも $M(g)$ は Archimedes 性をもつとは限らないが、$T$ はもつ。この節の議論は Wörmann による(Lau10 §4.7)。ここでは Positivstellensatz の系「正値・非負・零の証明書」の 1(等式の条件がない場合)を使う形で書く。その 1 は、$K$ の上で $p>0$ であることが、ある $a,b\in T$ による恒等式 $pb=1+a$ と同値であることを述べる(Positivstellensatz の帰結)。
$K$ がコンパクトなら、$T=T(g)$ は Archimedes 性をもつ。
$K$ はコンパクトなので、$N>0$ を大きくとれば $\ell:=N-\sum_ix_i^2$ は $K$ の上で正である。証明書の形の 1 により、ある $u,q\in T$ で
$$
u\ell=1+q
$$
となる。$T_1:=T+\ell T=\{a+\ell b\mid a,b\in T\}$ とおく。$T_1$ は和で閉じ、$(a+\ell b)(c+\ell d)=ac+\ell(ad+bc)+\ell^2bd$ より積でも閉じ、平方を含む。$\ell\in T_1$ なので $T_1$ は Archimedes 性をもつ 2 次加群であり、lem-sch-bounded により、どの多項式 $f$ にもある実数 $c_f$ で $c_f-f\in T_1$ となる。
$u$ は上から押さえられる. $m\ge1$ を $m-u\in T_1$ ととる。$m-u=a+\ell b$($a,b\in T$)と書くと、
$$
u(m-u)=ua+u\ell b=ua+(1+q)b\in T
$$
である。$m(m-u)=(m-u)^2+u(m-u)$ なので $m-u\in T$ である。
$u$ は下から押さえられる. $Nu-1=(N-\sum_ix_i^2)u+\sum_ix_i^2u-1=q+\sum_ix_i^2u\in T$ である。
$x_i^2$ を押さえる. $c>0$ を $c-x_i^2\in T_1$($i=1,\dots,n$)ととり、$c-x_i^2=a_i+\ell b_i$ と書く。上と同様に $u(c-x_i^2)=ua_i+(1+q)b_i\in T$ である。
$$
Ncm-x_i^2=Nc(m-u)+N\bigl(cu-x_i^2u\bigr)+x_i^2(Nu-1)
$$
の右辺の 3 項はどれも $T$ に入る。よって $nNcm-\sum_ix_i^2\in T$ で、$T$ は Archimedes 性をもつ。$\square$
$T$ は $g_I$($I\subset\{1,\dots,m\}$)の生成する 2 次加群 $M(g_I\colon I)$ であり、定義される集合は $K$ と同じである。thm-sch-archimedean により $T$ は Archimedes 性をもつので、生成元を $g_I$ たちとして thm-sch-putinar を当てれば、$K$ の上で正の $p$ は $T$ に入る。$\square$
Schmüdgen が 1991 年に示したのは、次の測度の形の主張である(Sch91)。モーメント問題 の $K$ の上の版にあたる。
$K$ がコンパクトで、線形写像 $L\colon\mathbb R[x]\to\mathbb R$ がすべての $I$ と $h\in\mathbb R[x]$ について $L(g_Ih^2)\ge0$ を満たすとする。このとき $K$ の上の Borel 測度 $\mu$ で、すべての $f$ について $L(f)=\int_Kf\,d\mu$ となるものがある。
条件は $T$ の上で $L\ge0$ ということである。$L(1)=0$ なら、$T$ が Archimedes 性をもつ(thm-sch-archimedean)ことからすべての $f$ で $c_f\pm f\in T$ となり、$\lvert L(f)\rvert\le c_fL(1)=0$ なので $\mu=0$ でよい。$L(1)>0$ なら $L/L(1)$ に thm-sch-measure を当てる。$\square$
$K\ne\emptyset$ をコンパクトとし、$p_{\min}:=\min_Kp$ とする。整数 $t\ge1$ について、次数を制限した 2 次加群
$$
M_t:=\Bigl\{\sigma_0+\sum_j\sigma_jg_j\Bigm|\sigma_j\in\Sigma,\ \deg\sigma_0\le2t,\ \deg(\sigma_jg_j)\le2t\Bigr\}
$$
をとり、$p^{(t)}:=\sup\{\lambda\in\mathbb R\mid p-\lambda\in M_t\}$ とおく。次数 $2t$ 以下の平方の和は、次数 $t$ 以下の単項式を並べたベクトル $v$ と半正定値行列 $Q$ で $v^{\mathsf T}Qv$ と書ける多項式のことなので、$p^{(t)}$ を求める問題は 半正定値計画 である。
$M(g)$ が Archimedes 性をもつとする。$p^{(1)}\le p^{(2)}\le\dots\le p_{\min}$ で、$t\to\infty$ のとき $p^{(t)}\to p_{\min}$ である。
$M_t\subset M_{t+1}$ から単調性が出る。$p-\lambda\in M_t$ なら $p-\lambda$ は $K$ の上で $0$ 以上なので $\lambda\le p_{\min}$ である。$\varepsilon>0$ について $p-p_{\min}+\varepsilon$ は $K$ の上で正なので、thm-sch-putinar により $M(g)=\bigcup_tM_t$ に入り、ある $t$ で $p^{(t)}\ge p_{\min}-\varepsilon$ である。$\square$
これは Lasserre(Las01)による。$M(g)$ の代わりに $T(g)$ を使えば、$K$ のコンパクト性だけで同じ収束が成り立つ(thm-sch-main)。
$g=1-x^2-y^2$ のとき $K$ は単位円板で、$N=1$ について $N-x^2-y^2=g\in M(g)$ なので $M(g)$ は Archimedes 性をもつ。$K$ の上で $x+1\ge0$ であり、
$$
x+1=\tfrac12(x+1)^2+\tfrac12(1-x^2-y^2)+\tfrac12y^2
$$
は $x+1\in M(g)$ の表示である。$x+1$ は $(-1,0)$ で $0$ になるので、定理の仮定「$p>0$」を満たさない多項式でも $M(g)$ に入ることがある。
1 変数で $g=1-x^2$、$p=x$ とすると $p_{\min}=-1$ で、$x+1=\tfrac12(x+1)^2+\tfrac12(1-x^2)\in M_1$ だから $p^{(1)}\ge-1$、よって $p^{(1)}=p_{\min}$ である。この場合は階層の最初の段で最小値が得られる。
| 外した条件 | 例 | 成り立たなくなること |
|---|---|---|
| $K$ のコンパクト性(thm-sch-main) | $n=2$、生成元なし($K=\mathbb R^2$、$T=\Sigma$)、$p=x^4y^2+x^2y^4-3x^2y^2+2$ | $\mathbb R^2$ で $p\ge1$ だが $p\notin\Sigma$ |
| $p>0$(両方の定理) | $n=1$、$g=(1-x^2)^3$、$p=1-x^2$ | $K=[-1,1]$ はコンパクトで $K$ の上で $p\ge0$ だが $p\notin T(g)$ |
| Archimedes 性(thm-sch-putinar) | $n=2$、$g_1=x-\tfrac12$、$g_2=y-\tfrac12$、$g_3=1-xy$、$p=5-x^2-y^2$ | $K$ はコンパクトで $K$ の上で $p>0$ だが $p\notin M(g)$($p\in T(g)$ ではある) |
2 行目:$1-x^2=s+t(1-x^2)^3$($s,t\in\Sigma$)とする。$x=1$ を代入すると $s(1)=0$ で、$s$ の各平方の項が $x=1$ で $0$ になるので $s$ は $(x-1)^2$ で割り切れる。右辺は $(x-1)^2$ で割り切れるが、左辺 $(1-x)(1+x)$ は割り切れない。1 変数では $T(g)=M(g)=\Sigma+\Sigma g$ である。
1 行目:相加相乗平均により $x^4y^2+x^2y^4+1\ge3x^2y^2$ なので $p\ge1$ である($p-1$ は Motzkin の多項式)。$p=\sum_kq_k^2$ とすると $\deg q_k\le3$ である。$x^6$ の係数 $0$ から $q_k$ に $x^3$ の項はなく、同様に $y^3$ もない。次に $x^4$、$y^4$ の係数から $x^2$、$y^2$ の項がなく、$x^2$、$y^2$ の係数から $x$、$y$ の項がない(いずれも、その単項式の平方が他の積で打ち消されない最高の項になる)。よって $q_k=a_k+b_kxy+c_kx^2y+d_kxy^2$ で、$x^2y^2$ の係数は $\sum_kb_k^2\ge0$ となり、$-3$ に等しくない。
3 行目:$K$ では $x,y\ge\tfrac12$、$xy\le1$ から $x,y\le2$ で、$x^2+y^2$ の最大値は $(2,\tfrac12)$ などでの $\tfrac{17}4<5$ である。よって $K$ はコンパクトで、$K$ の上で $p>0$ であり、thm-sch-main により $p\in T(g)$ である。$M(g)$ に入らないことを示す。辞書式順序($x>y$)で多項式の先頭項 $c\,x^\alpha y^\beta$ を考え、$0$ と、先頭項が「$(\alpha,\beta)\not\equiv(1,1)\pmod2$ かつ $c>0$」または「$(\alpha,\beta)\equiv(1,1)\pmod2$ かつ $c<0$」となる多項式の全体を $M'$ とする。2 つの元の先頭の単項式が違えば和の先頭項は大きい方の項、同じなら係数の符号が同じなので打ち消さない。よって $M'+M'\subset M'$ である。$h^2f$ の先頭項は $h$ の先頭項の平方と $f$ の先頭項の積で、指数の偶奇も係数の符号も $f$ と同じなので $h^2f\in M'$ である。$1\in M'$ なので $M'$ は 2 次加群である。$g_1,g_2$ の先頭項は $x$、$y$ で係数は正、$g_3$ の先頭項は $-xy$ なので、$g_j\in M'$ で $M(g)\subset M'$ である。$N-x^2-y^2$ の先頭項は $-x^2$ で、$(2,0)\not\equiv(1,1)$ なのに係数が負だから $M'$ に入らない。これは $p$($N=5$)が $M(g)$ に入らないことを示し、どの $N$ でも $N-x^2-y^2\notin M(g)$、すなわち $M(g)$ は Archimedes 性をもたない。
Schmüdgen の定理は Sch91、Putinar の定理は Put93 による。主張の整理は Lau10 の Theorem 3.16(p. 37)、Definition 3.18 と Theorem 3.20(pp. 38–39)に、Putinar の定理の証明は §3.7(pp. 47–49)に、$T$ の Archimedes 性の Wörmann による証明は §4.7 の Theorem 4.22(p. 66)とその前後にある。3 行目の反例は Lau10 の Example 3.19(p. 39)による。最適化への応用は Lasserre(Las01)による(Lau10 Theorem 6.8、p. 93)。この記事の証明は書き下ろしで、thm-sch-measure は掛け算作用素のスペクトルによる議論、thm-sch-archimedean は Positivstellensatz の証明書から直接に示した。
$K$ の上で $0$ 以上の多項式が $T(g)$ に入るとは限らない(反例の表の 2 行目)。Lau10(p. 37)によれば、$n\ge3$ で $K$ が内点をもつときなどには、$\mathbb R^n$ 全体で $0$ 以上なのに $T(g)$ に入らない多項式がある。cor-sch-lasserre の証明が最小値の近くの $p-p_{\min}+\varepsilon$ に定理を当てるのは、$p-p_{\min}$ 自身は $K$ の上で $0$ になり、定理の仮定を満たさないからである。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する