技術要約：球面上における多項式最適化のための固有値計算の階層構造

問題設定

本論文は、実同次多項式（形式）$p(x)$ の次数 $D$ のとき、$\mathbb{R}^n$ 内の単位球面上の最小値を求めるという根本的な問題に取り組んでいる：
$$p_{\min} = \min_{x \in \mathbb{R}^n, \|x\|=1} p(x).$$
この問題は、$D \geq 3$ のときNP困難であり、グラフ理論（例：最大安定集合）、計算複雑性、および量子情報（例：$2 \to 4$ ノルムの計算）において重要な応用分野を含んでいる。

標準的なアプローチは、実和形式平方（Real Sum-of-Squares; RSOS）階層であり、これは $p_{\min}$ に収束する一連の下界を提供する。しかし、RSOS階層の各レベルでは、完全な半定値計画問題（SDP）を解く必要がある。問題のサイズ（変数数 $n$ および次数 $D$）が増大するにつれ、SDPのサイズは急速に増大し、大規模なインスタンスに対してはこの手法を計算上実行不可能にする。

手法

著者らは、完全なSDPではなく、一連の最小固有値計算を通じて $p_{\min}$ を近似する、HRSOS（Hermitian Real Sum-of-Squares）と呼ばれる新しい階層を提案している。この手法は、以下の3つのコアコンポーネントに基づいている：

1. エルミート最適化への還元： 著者らは、球面上における実最適化から、複素球面におけるエルミート最適化への還元を確立した。実形式 $p$ に対して、彼らは最大対称グラム演算子 $P = M(p)$ を定義する。彼らは、実形式の最小値 $p_{\min}$ が、関連するエルミート形式 $P_{\min}$ に対して既知の定数因子 $\delta(d)$ を用いて、以下のように抑えられることを証明している：
   $$P_{\min} \leq p_{\min} \leq \frac{P_{\min}}{\delta(d)}.$$
   決定的なことに、この還元は、$p_{\min} > 0$ であることと $P_{\min} > 0$ であることが同値であるという性質を保持している。

2. HSOS階層の利用： エルミート最適化問題は、エルミート和形式平方（Hermitian Sum-of-Squares; HSOS）階層を用いて解かれる。RSOS階層とは異なり、HSOS階層は「スペクトル」階層であり、レベル $k$ における下界は、入力形式から構成される特定のエルミート演算子の最小固有値に過ぎない。HSOS階層の収束性は $O(1/k)$ であることが知られている。

3. HRSOS階層の構築： 還元とHSOS階層を組み合わせることで、著者らは一連の一般化固有値問題を構築している。レベル $k$ における下界 $\eta_k$ は、次のように計算される：
   $$\eta_k = \lambda_{\min}\left( (N^{(d)}_k)^{-1/2} P_k (N^{(d)}_k)^{-1/2} \right),$$
   ここで、$P_k$ と $N^{(d)}_k$ は $p$ とノルム形式 $\|x\|^{2d}$ から導出される演算子である。実際には、これは大きな行列の明示的な逆行列計算を避け、一般化固有値問題 $P_k \psi = \lambda N^{(d)}_k \psi$ として解かれる。

著者らは、このフレームワークを多重同次形式（積球面上の最適化）およびテンソルスペクトルノルムへと拡張し、m-HRSOS 階層を構築している。

主な貢献

• 実最適化のためのスペクトル階層： 本論文は、完全なSDPではなく、固有値計算のみに依存する、球面上における実多項式最適化のための初の収束階層を導入している。
• 収束保証： 著者らは、HRSOS階層が $p_{\min}$ に対して加法的に収束し、その速度が $O(1/k)$ であることを証明している。これは、$D \leq 2n$ の場合のRSOSの最良の既知のレート $O(1/k^2)$ よりは遅いが、$D > 2n$ の場合のRSOSの既知のレート $O(1/k)$ と一致する。
• テンソルスペクトルノルム計算： 本手法は、テンソルの実スペクトルノルムを計算し、双二次形式を最小化するように一般化されており、既存のテンソル分解および最適化手法に対するスペクトルの代替手段を提供する。
• 標準的な構成： 他の「より安価な」代替案（調和階層など）とは異なり、提案された手法は完全に標準的（canonical）であり、求積則やカーネルの恣意的な選択を必要としない。

結果と数値性能

著者らはMATLABでHRSOS階層を実装し、RSOS、DSOS（対角優位SOS）、および調和階層と比較した。

• スケーラビリティ： 主な利点はスケーラビリティである。RSOSは、メモリ制約のため、小さな問題（例：次数4の多項式で変数約25個）に限定されるが、HRSOSは疎な一般化固有値ソルバを利用するため、大幅に大きなインスタンス（例：次数4の多項式で変数90個超）を扱うことができる。
• RSOSとの効率性： RSOSが実行可能な小規模な問題においては、RSOSの方が計算時間あたりの下界の精度が高い。しかし、RSOSが失敗するような大規模な問題においては、HRSOSが唯一実行可能なスペクトルの代替手段となる。
• 他の手法との効率性： 最適化を用いない調和階層と比較して、HRSOSは単位時間あたりの下界の質において優れている。調和階層は、$n$ に対して指数関数的なサイズの求積則上で多項式を最小化する必要があり、$n \geq 10$ では極めて高価になる。HRSOSはこの離散最適化のボトルネックを回避している。
• 収束性： モッツキン多項式やランダムな4次形式を含む数値実験において、HRSOSは一定の時間予算内で、DSOSおよび調和階層よりも一貫して優れた下界の質を示した。

意義と主張

本論文は、HRSOS階層が、エルミート最適化および量子デ・フィネッティ定理からの技術を活用することで、大規模な制約付き実最適化問題を解くための新しい道を切り開くと主張している。

• 実用的影響： この手法は、標準的なSDP手法では現在手に負えない多項式最適化問題の境界計算を可能にする。
• 理論的架け橋： 実最適化とエルミート最適化の間の厳密な関連性を確立しており、他のエルミート・スペクトル技術が実問題に適応できる可能性を示唆している。
• 謙虚な姿勢： 著者らは、収束速度（$O(1/k)$）が低次数における最良のRSOSレートほど速くないことを認めているが、高次元問題における計算の実現可能性により、実用的なツールとして優れているとしている。また、制約付き最適化の場合、実問題とエルミート最小値の間の直接的な等価性は必ずしも成立しないため、二分法や完全なSDPに頼らずに階層を一般の制約に適応させるためのさらなる研究が必要であることも述べている。

本論文は、球面上における大規模な多項式最適化およびテンソルスペクトルノルム計算において、提案された固有値計算階層が、計算の実行可能性と下界の質の間の魅力的なバランスを提供し、既存の非SDP代替案を凌駕すると結論付けている。