Effect of constraint relaxation on the minimum vertex cover problem in random graphs
Aki Dote and Koji Hukushima,
“Effect of constraint relaxation on the minimum vertex cover problem in random graphs”,
Phys. Rev. E 109, 044304 – Published 5 April 2024
https://doi.org/10.1103/PhysRevE.109.044304
これは、この３月に卒業した土手さんの研究成果です。例によって周辺解説をします。
最適化問題は統計力学から見ると絶対零度極限に相当するので、熱力学極限での最適化問題の性質はFu-Anderson以来多くの統計力学的研究があります(こういうところにも出てくるP.W.Andersonはすごい）。Kirkpatrick-Selmanがランダム化された制約充足問題であるrandom SAT問題に相転移が起きることを見つけると、レプリカ法などのランダム系の統計力学の手法を用いて、ランダム化された様々な制約充足問題・最適化問題が研究されました。その中に、ここで議論するVertex Cover問題もWeigt-Hartmanによって同様にレプリカ法で解析されています。当初は、SAT-UNSAT転移のように解のあるなし相転移でしたが、やがてその近傍にレプリカ対称性の破れる転移と典型的な問題のeasy-hard転移のような関係性があるのではないかと考えられ、アルゴリズムの解析も含めて研究が進みました。
さて、富士通から来られた社会人博士の土手さんは社会実装の現場で数多くの最適化問題の応用例をみてきて、現場の問題では拘束条件の取り扱いの難しさを身にしみて知っていました。一般に最適化問題は最小化するコスト関数f(x)と拘束条件g(x)>0からなります。
$$
\min f(x)\\
\mathrm{subject\ to\ } g(x)>0
$$
拘束条件のない最適化問題は上だけ、SATやcoloring問題など制約充足問題は下だけで、通常の問題はこの両方を含みます。実際の非線形なf(x)に対する解法では、拘束条件は何か別の罰金項としてコスト関数に埋め込むことが多いです。特に、イジングマシーンを用いて解くときの標準形であるQUBOに必ず埋め込みます。罰金項は罰金係数付きの付加項としてコスト関数f(x)に加えますので、罰金係数が十分大きいときには制約条件は満たされますが、そこは求解が難しい。一方で、係数が小さいときには制約条件は満たされませんので、適当にコスト関数を小さくしてしまえばよいので、解くのは簡単になりそうです。どうやら経験的にはできるだけ制約係数を小さくした方がよく、ただし小さくしすぎて望まない解にはならない、そんなぎりぎりを攻めたいようです。ところが、制約を満たすために必要な罰金係数は問題に依存して決まるために事前にわかっていることは少ないです。つまり、罰金係数はどこに設定すればよいかは一般の問題ではよくわからないことになります。そこで、罰金項付きの最適化問題の性質を調べてみようということになりました。
この設定になるミニマルで非自明な問題はvertex cover問題だろうということで、この研究がはじまります。まあ、いろいろありましたねー。例えば、鞍点方程式が普通に収束しないとか。そんなのダンピングでなんとかなるだろうとかいってもなんともならないし、ちゃんと固有値解析しようとなって、Fredholmの方法とか勉強し直したり、いろいろ面白かった。絶対零度極限には悪魔の階段的なのが現れたり、めちゃくちゃ渋くて、もう上に書いたような罰金係数の…みたいのはそっちのけで調べまくってました、土手さんが。絶対零度で罰金係数に対して非解析的な数値結果が出てきたときには、「いやーそんなのはバグだよね」って思ってました。絶対零度極限はぎりあってもいいかもしれないけど、いかにも不自然なジャンプがあるなんて変だと思いますよ。ただ、ここからの粘りがすごくて、結局絶対零度の極限を正しく取れていないということになって、エバネッセント補正（この名前は何かの先行研究に従っているけど意味はわからない）の必要性に気づくわけです、土手さんが。その項はWeigt-Hartmanの結果と異なる結果を導くので、ややビビるわけです。彼らの結果はレプリカ対称性を仮定していて、我々もそのレベルでは同じです。彼らの結果は厳密な下限評価（first moment bound)を破ってしまうので、レプリカ対称性の仮定が間違いであることを認めざるを得なくなるわけですが、我々の結果はその下限を破らないので、その意味は？？となります。
先日の物理学会で土手さんがその話を発表しました。そこで、樺島さんから「それは結局正しくRS解を計算したってことですよね」と言われて、いやーまったくその通りなんだけど、これまで正しく解いてなかったわけだし、正しく解いていないからRSが間違いだと気づいたわけだし…正しい理解に到達したので意義はあるわけですよ。BPでも素朴にこの項を無視すると、半整数状態の縮退が解けないので正解に到達できなくなるだろうから、縮退を解くためにも役に立つかもしれない項ではある。BPにどのように埋め込むのかはまだわからない。とまあ、あんなこんなでいろいろ面白いことがわかった土手さんの力作論文でした。
元に戻ると、罰金項が問題を簡単にしている様子は転移温度の減少など間接的な結果しか得られていないです。今見えてる転移はレプリカ対称性の破れる相転移なので、罰金項を弱くしていくとレプリカ対称性は破れることはなくなるので、問題は簡単になって、制約条件を破って安易な解に行ってしまうということだと思います。Parisi-Franzポテンシャルなどを計算してみるともう少し解空間の構造がわかるかもしれない。それは今後の課題なのかな。