⚡ electrical engineering

Disjunctive Sum of Squares

本論文は、多項式の非負性を複数の並列な代数恒等式を通じて証明する手法である「離散和の二乗」の概念を導入し、固定サイズの半正定値制約を有する収束する最適化階層の構築と最適化不要の代替手法を可能にしつつ、多項式最適化、コポジティブ最適化、および組合せ最適化における実用的な応用を実証する。

原著者： Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, Bartolomeo Stellato

公開日 2026-05-28

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, Bartolomeo Stellato

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたが探偵だと想像してください。謎めいた複雑な機械（数学的多項式）が、決して負の数を生成しないことを証明しようとしています。数学の世界では、これを「非負性」の証明と呼びます。

長年にわたり、この謎を解く標準的な方法は、魔法の鍵のようなたった一つの完璧な代数方程式を見つけることでした。機械の出力を平方和（例えば $A^2 + B^2 + C^2$ のような形）として記述できれば、それは決して負になり得ないことが確実になります。なぜなら、平方数は常に正だからです。

しかし、この「単一の鍵」アプローチには重大な欠陥があります。その一つの方程式を機能させるために、信じられないほど複雑で高次の数を用いなければならない場合があるのです。まるで、単純なドアを開けるために、50 フィートもの巨大な骨格鍵を使おうとしているようなものです。それは機能しますが、重く、構築に費用がかかり、多くの現実世界のシナリオでは計算的に使用不可能です。

新しいアイデア：小さな鍵のチーム

この論文は、「選言平方和（Disjunctive Sum of Squares）」と呼ばれる新しい戦略を導入します。巨大で複雑な鍵を一つ探すのではなく、著者たちはより小さく単純な鍵のチームを使用することを提案します。

ここが核心的な概念です：

世界の分割：考えられる入力という宇宙を大きな部屋だと想像してください。機械が部屋全体に対して安全であることを一度に証明するのではなく、部屋を管理可能な小さな領域（ピザをスライスに分割するようなもの）に分けます。
局所的な証明：各領域において、機械が安全であることを証明するために必要なのは、単純で低次の方程式だけです。
「または」の論理：すべてをカバーする一つの方程式は必要ありません。必要なのは、「領域 A にいるなら機械は安全である、または領域 B にいるなら機械は安全である、または領域 C にいるなら……」と証明することです。部屋のすべての可能な点が、これらの安全な領域の少なくとも一つに属する限り、機械全体が安全であると証明されたことになります。

なぜこれがゲームチェンジャーなのか？

単純さ：各領域で使用される「鍵」（代数恒等式）は、旧来の方法が要求する巨大な鍵よりもはるかに単純で小さくなります。
並列処理：各領域は独立しているため、すべてを同時にチェックすることができます。まるで、一人の探偵が建物全体を一人でチェックしようとするのではなく、探偵のチームが異なる部屋を同時にチェックしているようなものです。
効率性：著者は数学的に、機械がどれだけ複雑であっても、常にこれらの単純で低次の証明を見つけられることを証明しています。方程式をより複雑にする必要はありません。領域を追加するだけでよいのです。

論文で言及されている現実世界への応用

著者たちは、この「鍵のチーム」アプローチをいくつかの困難な問題でテストしました：

「モツキンス」パズル：彼らはこの手法を用いて、旧来の方法が苦戦していた有名な数学的パズル（モツキンス多項式）の安全性を証明しました。彼らは、旧来の方法では不可能なほど複雑化しなければ見つけられなかった証明を、単純な方程式を用いて発見しました。
行列のコポジティブ性：これは数値のグリッド（行列）に関する特定の問題です。著者たちは、この問題をより小さな幾何学的な形状（三角形や円錐）に分解して、これらの行列が安全であることを証明する方法を示しました。これは最適化や経済学において有用です。
「クリーク」の発見：グラフ理論（点と線のネットワーク）において、「クリーク」とは、すべての点が互いに接続されている点のグループです。最大のクリークを見つけることは、 notorious に難しい問題として知られています。著者たちは、この手法を用いて問題を小さな断片に分解し、いくつかのランダムなネットワークにおいて最大のグループの正確なサイズを成功裏に見つけ出しました。

結論

この論文は、数学的な真実を証明するために、単一の巨大で複雑な解決策を強制する必要はないと主張しています。代わりに、問題をより小さく重なり合う部分に分割し、それぞれの部分を単純なツールで解決することで、全体が真であることをはるかに速く、効率的に証明できます。それは、巨大なレバー一つで岩を持ち上げようとするのと、小さな単純なレバーを持つ人々のチームが協力して持ち上げるのとでは、全く異なるのです。

技術的概要：選言平方和

問題定義

本論文は、多項式の非負性を証明する根本的な問題に取り組んでいる。多項式 $p$ がすべての $x \in \mathbb{R}^n$ に対して $p(x) \geq 0$ である場合、 $p$ は非負であるが、この性質を決定することは一般的に NP 困難である。標準的なアプローチである平方和（SOS）法は、 $p$ を単一の代数恒等式 $p(x) = \sum q_i^2(x)$ として表現することで非負性を証明する。しかし、すべての非負多項式が SOS であるわけではない（これはヒルベルトによって確立された事実であり）、SOS ではない多項式の非負性を証明するには、通常、 $p$ に高次の SOS 多項式を乗じる必要がある（例えば、ヒルベルトの第 17 問題に対するアルティンの解決策を通じて）。その結果、元の多項式の次数よりもはるかに高い次数を持つ代数恒等式が生じ、サイズが指数関数的に増大し計算的に処理不可能になる半定数計画問題（SDP）が導かれる。

この研究を動機づける中心的な問いは、多項式の非負性に関する SOS ベースの証明の複雑さを、単一の恒等式の代わりに複数の代数恒等式を構築することで低減できるか？ である。

手法

著者らは、**選言平方和（Disjunctive SOS）**という概念を導入する。単一のグローバルな恒等式の代わりに、非負性は、領域の特定の部分領域ごとに有効な代数恒等式の集合によって証明される。これらの部分領域は、代数選言によって定義され、空間の分割（または被覆）を形成する。

核心的な定義

代数選言: 領域 $\Omega_k = \{x \mid q_{k,j}(x) \geq 0, \forall j\}$ の和集合が $\mathbb{R}^n$ を被覆するような多項式の集合 $\mathcal{D} = \{\{q_{k,j}\}\}$ 。
選言 SOS 証明: 多項式 $p$ が $\mathcal{D}$ に関する選言 SOS であるとは、各領域 $\Omega_k$ に対して、SOS 多項式 $s_{k,j}$ が存在し、次式が成り立つことを意味する：
$p(x) = s_{k,0}(x) + \sum_{j=1}^{n_k} s_{k,j}(x)q_{k,j}(x) \quad \text{for all } x \in \Omega_k.$
重要なのは、グローバルな SOS 証明では次数が増加しなければならないのに対し、SOS 多項式 $s_{k,j}$ の次数は低く保つことができる（具体的には $p$ の次数以下に制限される）ことである。

理論的枠組み

本論文は、**選言ポジティブステルレンツァーツ（Disjunctive Positivstellensätze）**と呼ばれる 2 つの主要な理論的結果を確立している。

SDP ベースの選言ポジティブステルレンツァーツ（定理 1）:
次数 $d$ の任意の正定値形式 $p$ に対して、（球面帽を介して構築された）代数選言の明示的な族が存在し、 $p$ は SOS 乗数の次数が最大で $d$ となる選言 SOS 証明を許容する。これにより、固定サイズ（階層レベルに依存しない）の SDP を用いて、単位球面上での多項式最小化に対する収束する下限の階層が可能となる。
最適化不要の選言ポジティブステルレンツァーツ（定理 8）:
より強力な結果として、任意の正定値形式に対して、単体選言（多面体錐）の族が存在し、各錐内での線形座標変換後の係数が非負であることを確認するだけで、 $p$ の非負性を証明できることが示される。このアプローチには最適化ソルバーは不要（線形計画法または直接的な係数チェックのみで可能）であるが、SDP アプローチに比べてより多くの領域を必要とする可能性がある。

アルゴリズム的枠組み

著者らは、これらの選言証明を適応的に探索するための**空間分枝限定法（SBB）**枠組みを提案する。理論的証明におけるように空間を一様に分割するのではなく、本アルゴリズムは以下の処理を行う：

部分領域（単体錐）のツリーを維持する。
各部分領域において SDP（または線形チェック）を通じて下限を計算する。
射影勾配降下法を通じて上限を計算する。
最小の下限を持つ部分領域の最も長い辺を二等分することで分枝を行う。
この適応的アプローチは、一様な構築に比べて少ない部分領域で証明を見つけることを目指している。

主要な貢献と結果

1. 理論的保証

固定次数: 本論文は、低次数の選言 SOS 証明が常に存在することを証明している。証明内の SOS 多項式の次数は、階層レベルに伴って増加する必要はなく、元の多項式の次数に固定できる。
収束: 著者らは、単位球面上の同次多項式のグローバル最小値に収束する、固定サイズの制約を持つ SDP の階層を構築する。空間分割の解像度に関連する $m$ を用いて、収束速度が $O(1/m)$ であることを確立している。
最適化不要の証明: 2 つ目のポジティブステルレンツァーツは、SDP を解くのではなく、線形変換と係数の非負性チェックに依存して非負性を証明する手法を提供する。

2. 制約付き最適化への応用

多項式最適化: 選言アプローチと [2] からの還元技法を組み合わせることで、コンパクトな基本半代数集合上の一般的な多項式最適化問題（POPs）に対する下限の収束する階層を構築する。
コポジティブ計画法: この手法は、行列のコポジティブ性（ $x \geq 0$ に対して $x^T Q x \geq 0$ を確認すること）を証明するために特化されている。著者らは「選言 P+N」条件を定義しており、非負象限の各単体部分領域において、行列が半正定値行列と非負行列に分解できる場合、その行列はコポジティブであると証明される。これにより、既存の階層（制約サイズがレベルとともに多項式的に増大する）とは対照的に、SDP 制約のサイズが固定（ $n \times n$ ）のままの完全な階層が得られる。

3. 数値実験

著者らは以下の数値実験を提示している：

非 SOS 多項式: SBB 枠組みを用いて、古典的な非 SOS 多項式（Motzkin、Robinson、Choi-Lam、Delzell など）の非負性を、少数の部分領域（多くの場合 20 未満）で正常に証明した。
コポジティブ計画: アルゴリズムは、非凸二次計画問題を解決し、ランダムなインスタンスにおいてグラフのクリーン数を計算した（Motzkin-Straus 定理を通じて）。
パフォーマンス: 結果は、選言アプローチが一様な分割に比べてはるかに少ない部分領域で非負性を証明し、最適化問題を解決できること、および SDP 制約のサイズが管理可能な範囲に留まることを示している。

意義と主張

本論文は、証明の複雑さ（SOS 多項式の次数）と使用される代数恒等式の数を分離することで、従来の SOS 階層に対する実用的な代替手段として選言平方和アプローチを提案している。

計算効率: SOS 多項式の次数を低く固定することで、階層全体を通じて基礎となる SDP のサイズを一定に保ち、標準的な SOS 法における多項式次数の増加に伴う「次元の呪い」を回避する。
柔軟性: この枠組みは、より少ない領域でより tight な境界を得るための SDP ベースの探索と、より高速だが潜在的に粗い証明を得るための最適化不要の探索の両方をサポートする。
完全性: 著者らは、このアプローチが完全であることを証明している。任意の厳密に正の多項式（または厳密にコポジティブな行列）に対して、その枠組み内で証明が存在する。

論文は結論として、理論的構築は一様な分割を使用するが、実用的な SBB アルゴリズムは空間を適応的に洗練させるため、インスタンス固有の選言がさらに必要な領域数を削減できる可能性を示唆している。この研究は、疎性と対称性の利用と選言 SOS を組み合わせる道を開き、またこの枠組みの双対モーメント側を探索する可能性を拓いている。