Perfect Copositive Matrices

技術要約：完全コポジティブ行列

問題提起
本論文は、コポジティブ最適化の文脈における古典的な完全正定値行列の一般化である「完全コポジティブ行列（perfect copositive matrices）」の系統的な研究を扱う。主な動機は、完全正値（completely positive, CP）行列に対する有理的な証明書を見つけるためのアルゴリズム的解決策である。行列 $Q$ が完全正値であるとは、$Q = \sum \alpha_i x_i x_i^\top$ （$\alpha_i$ は非負の係数、$x_i$ はベクトル）と分解できることを指す。行列が $CP_n$ 錐に属するかどうかの判定は困難であるが、双対理論によれば、$Q \notin CP_n$ であることの証明書は、$\langle B, Q \rangle < 0$ を満たすコポジティブ行列 $B$ である。著者らは、コポジティブ行列の空間を横断して、そのような証明書やCP分解を見つけるためのアルゴリズム（具体的にはボロノイ型の単体型アルゴリズム）を促進するために、完全コポジティブ行列の構造を調査している。

手法
著者らは、正定値行列のリシュコフ・ポリヘドロン（Ryshkov polyhedron）の多面体構造を分析する古典的なボロノイの減少理論を、コポジティブ行列の錐（$COP_n$）へと拡張している。

1. 定義: 彼らは、対称行列 $B$ の「コポジティブ最小値（copositive minimum）」を $\min_{COP} B = \inf \{ B[v] : v \in \mathbb{Z}^n_{\geq 0} \setminus \{0\} \}$ と定義する。厳密なコポジティブ行列は、そのコポジティブ最小値と、その最小値を達成する整数非負ベクトルの集合によって一意に決定される場合に、「完全コポジティブ」と呼ばれる。
2. 多面体構造: 彼らは、コポジティブ・リシュコフ・ポリヘドロン（$R_{COP}$）を、$B[v] \geq 1$ （すべての非ゼロ $v \in \mathbb{Z}^n_{\geq 0}$ に対して）を満たす行列の集合として定義する。$R_{COP}$ の頂点は、完全コポジティブ行列に対応する。
3. グラフ探索: 研究には、これらの頂点の近傍グラフの分析が含まれる。隣接する完全コポジティブ行列は、コポジティブ・ボロノイ錐の双対の極端レイ（extreme ray）に沿って移動することによって見出される。
4. 次元解析: 論文では、低次元（$n=2$ および $n=3$）における詳細な構造解析を行い、古典的な理論との類似点と相違点を特定し、その後 $n \geq 3$ へと一般化を行っている。
5. リフティング手法: 著者らは、特定の性質（ランクやコポジティブ最小値など）を保持しながら、低次元の完全コポジティブ行列から高次元の完全コポジティブ行列を構成するための「リフティング（lifting）」操作（補題 5.1）を用いている。

主要な貢献および結果

• 古典的理論との相違点 ($n \geq 3$):

  • 古典的なケースでは完全行列は正定値であるが、完全コポジティブ行列は**不定（indefinite）または半正定値（positive semidefinite）**であり、ランクが $n$ よりも厳密に小さい場合がある。
  • $n \geq 3$ の場合、例外的なコポジティブ行列（$COP_n \setminus (S^n_{\geq 0} + N^n)$）を含む、コポジティブ錐のすべての成分に完全コポジティブ行列が存在する（ただし、例外的な行列は $n \geq 5$ でのみ存在する）。
  • ある完全コポジティブ行列からの特定の方向が、隣接する完全行列ではなく、$R_{COP}$ の極端レイにつながるという、古典的理論には見られない新しい現象が特定されている。
  • $n=2$ の場合、完全コポジティブ行列は、負の非対角成分を持つ古典的な完全行列と一致する。

• 古典的理論の埋め込み:

  • 本論文は、すべての古典的な完全正定値行列が、完全コポジティブ行列と算術的に等価であることを証明している（定理 6.1）。これは、任意の古典的な完全行列に対して、その最小ベクトルを（符号を除いて）非負直交錐へと写す単模変換が存在することを示すことで達成される。

• 多面体分解と特徴付け:

  • 著者らは、コポジティブ・リシュコフ・ポリヘドロン $R_{COP}$ の多面体的表現を確立した。古典的なケースとは異なり、$R_{COP}$ は単に頂点の凸包であるだけでなく、非有界な方向を考慮するために行列 $E_{ij}$ （$i \neq j$）によって生成される錐を加える必要がある（定理 7.1）。
  • また、完全コポジティブ行列のコポジティブ・ボロノイ錐の和集合が、完全正値錐 $CP_n$ の多面体分解を形成することを証明している。

• $CP_n$ の新しい特徴付け:

  • 完全正値行列の錐に関する重要な結果として、新しい特徴付けが示されている。本論文は、$CP_n$ が、すべての完全コポジティブ行列と非負の内積を持つ非負行列の集合であると実証している（系 7.7）。これは、$COP_n$ が $CP_n$ の双対であるのと同様に、$CP_n$ の双対的な記述を提供するものである。

意義および主張
本論文は、完全コポジティブ行列に関する「最初の系統的な研究」を提供すると主張している。その意義は、古典的な数論的減少理論と現代のコポジティブ最適化を橋渡しすることにある。$R_{COP}$ の多面体構造と、コポジティブ錐の様々な成分における完全コポジティブ行列の存在を確立することで、著者らは、彼らの先行研究 [10] で述べられたアルゴリズム的アプローチの理論的基礎を築いている。具体的には、これらの結果は、完全コポジティブ行列の近傍グラフを用いて、CP分解の有理的な証明書を生成したり、$CP_n$ への非所属を証明したりする手法の実現可能性を支持している。著者らは、完全コポジティブ行列が（同値を除いても）無限に存在することを発見しているものの、分類問題は古典的なケースと同様に、高次元においては未解決のままであると謙虚に述べている。