線形SDPを解くためのGNNの表現力について

要旨: 半正定値計画法（SDP）は、凸最適化のための強力な枠組みであり、難しい組合せ最適化問題に対する強力な緩和を構築するための手段にもなります。しかし、大規模なSDPを解くことは計算コストが高くなりがちで、そのため高速な計算代替として機械学習モデルを用いることが動機づけられています。この状況において、グラフニューラルネットワーク（GNN）は、疎性を意識できること、そして変数と制約の相互作用をモデル化できることから、自然な候補となります。本研究では、最適なSDP解を復元するのに十分な表現力がどの程度必要かを調べます。まず、標準的なGNNアーキテクチャでは線形SDP解の復元に失敗することを示す否定的結果を証明します。次に、SDPの主要な構造を捉え、特に標準的な一次解法ソルバの更新を模倣できる、より表現力の高いアーキテクチャを特定します。実験的には、さまざまなクラスのSDPに対する合成データおよび\textsc{SdpLib}ベンチマークの両方で、このより表現力の高いアーキテクチャは、理論的により弱いベースラインよりも一貫して予測誤差と目的関数ギャップが低いことを達成します。最後に、学習した高品質な予測を用いて一次解法ソルバをウォームスタートすると、最大80%の実用的な高速化が得られます。