Making Non-Negative Polynomials into Sums of Squares

技術要約：非負多項式を平方和へと変換する

問題設定
本論文は、閉集合 $K \subseteq \mathbb{R}^n$ に対する非負多項式の集合 $\text{Pos}(K)$ を、平方和（SOS）の錐 $\Sigma \mathbb{R}[x_1, \dots, x_n]^2$ へと変換するという課題に取り組んでいる。非負多項式およびモーメント列は広く研究されているが、すべての非負多項式が平方和であるとは限らず（Motzkin, 1967）、すべての平方正な汎関数がモーメント汎関数であるとも限らないため（Scheiderer, 1979）、これらを扱うことは計算上困難である。著者は、$\text{Pos}(K)$ を SOS 錐へと写す線形作用素 $T: \mathbb{R}[x_1, \dots, x_n] \to \mathbb{R}[x_1, \dots, x_n]$ を調査しており、これは非負多項式の集合をより扱いやすい形式へと「前処理」することを目的としている。この研究は、ある汎関数を集合 $S$ 上で最小化する問題を $TS$ 上の最小化問題へと変換することで、数値的安定性を向上させたり、SOS ベースのソルバーの使用を可能にしたりできるという最適化への応用から動機付けられている。

手法
核心となる手法は、**正則なフレシェ・リー群（regular Fréchet Lie groups）**の理論と、それに関連する多項式空間上で作用するリー代数に基づいている。

1. 作用素半群（Operator Semigroups）: 著者は、$T_t = e^{tA}$ という形式の作用素（ここで $A$ は線形生成元）を研究している。これらの生成子の集合 $\mathfrak{g}$ は、$e^{tA}$ がすべての $t \in \mathbb{R}$ に対して多項式を多項式へ写すという性質によって特徴付けられる。
2. 標準表現（Canonical Representation）: 線形作用素の標準表現 $T = \sum q_\alpha \cdot \partial^\alpha$ を利用して、論文は $K$-正値性を保存する作用素と $K$-モーメント列との関係を定理 1.1 (dD25より) を通じて結びつけている。
3. 有限次元不変部分空間: 重要な技術的ツールは定理 3.3 であり、これは任意の $A \in \mathfrak{g}$ に対して、多項式環を覆う有限次元不変部分空間のフィルトレーション $V_i$ が存在することを確立している。これにより、無限次元の作用素指数を、これらの有限部分空間上の行列指数の極限として計算することが可能になる。
4. 特定の作用素構成: 非負多項式を SOS へ写すために、著者は $Ap = \ell(p) \cdot f$ で定義される特定のランク1作用素 $A$ を構成している。ここで $\ell$ は錐に対して正な線形汎関数であり、$f$ は対象となる SOS 錐の内部点である。

主要な貢献と結果

• 生成子の特徴付け ($\mathfrak{g}$): 本論文は、多項式環上でウェルデファインドな群となる生成子 $\mathfrak{g}$ の集合を完全に特徴付けている。$\mathfrak{g}$ は錐であるが、ベクトル空間ではない（一般に加法や乗法に対して閉じているわけではない）ことが示されている。しかし、共通の有限次元不変部分空間を共有する $\mathfrak{g}$ の部分集合は、正則なフレシェ・リー代数を形成する。
• Stochel の定理（三線定理による証明）: 著者は、ある数列が $K$-モーメント列であるための必要十分条件は、その切断（truncations）が切断 $K$-モーメント列であることであるという Stochel の定理 (2001) の簡潔な証明を提供している。この証明は、多項式と数列の双対性および Haviland の定理に依拠している。
• $K$-正値性保存半群の生成元: 定理 6.3 は、$K$-正値性を保存する生成子 $A \in \mathfrak{g}$ のレゾルベント記述を提供している。これは先行研究を一般化したものであり、抽象的ではあるが完全な特徴付けを与える。
• 平方和への変換 (定理 7.1): 中心的な結果は、固定された次数境界 $d$ に対して、任意の非負多項式の集合 $S \subseteq \text{Pos}(K)_{\le 2d}$ を SOS 錐 $\Sigma \mathbb{R}[x_1, \dots, x_n]^2_{\le d}$ へ写す線形作用素 $T = e^{\tau A}$ が存在することを示している。
• 計算効率: 論文は、構成された作用素 $T$ の特定の構造（恒等作用素へのランク1更新）が、極めて高い計算効率をもたらすことを強調している：
  • メモリ: 作用素行列 $\tilde{T}$ の格納には $2N + 1$ 個のスカラーのみが必要であり（ここで $N = \dim \mathbb{R}[x]_{\le 2d}$）、ストレージを $O(N^2)$ から $O(N)$ へ削減している。
  • 計算量: 行列とベクトルの積 ($Tv$) は最大$4N + 1$回の演算を要し、行列と行列の積 ($\tilde{T}M$) は最大$4N^2 + 1$ 回の演算を要する。
  • 逆行列: 逆作用素 $\tilde{T}^{-1}$ の計算には、わずか一回の演算（除算）しか必要としない。これは、標準的な行列反転の $O(N^3)$ 以上の計算量とは対照的である。
• 不可能性の結果 (定理 7.5): 本論文は、コンパクトな $K$ に対して、次数境界なしに無限次元の錐 $\text{Pos}(K)$ 全体を SOS 錐へと写す単射線形作用素 $T$ は存在しないことを証明している。これは、主定理における次数制約の必要性を浮き彫りにしている。
• 非マルコフ的例: セクション 8 では、Burgers 方程式を用いた例を提示し、斉次マルコフ過程ではない時間発展を示しており、これにより $e^{tA}$ の理論がすべての可能な多項式発展をカバーしているわけではないことを示している。

意義と主張
本論文は、開発された理論が、非負多項式を平方和へと変換するための計算可能な手法を提供すると主張している。非負性と SOS の間には乖離があるため、このタスクは一般に困難である。その意義は、提案された変換のアルゴリズム的効率性にある。正則なフレシェ・リー群の特定の構造的特性を持つ作用素を利用することで、著者は行列演算の自明な下限（$O(N^2)$）を満たし、逆演算を単一の演算へと削減することに成功している。

著者は、変換 $T$ およびその逆変換は効率的に計算できるものの、このアプローチは固定された次数境界に限定されることを明示している。本論文は、すべての非負多項式を SOS として表す一般的な問題を解決しようとするものではなく（それは不可能である）、最適化や数値的安定性の目的で、特定の非負多項数の部分集合を SOS 錐へと移動させるためのツールを提供している。本研究は、無限次元リー群の抽象理論と、実用的な計算代数幾何学との架け橋となるものである。