First Order GPU実装

大変、参考になる論文が出ました。 

2311.12180

PDLPは、諦めていたのですが、GPU実装を使えば、可能性があることが示されています。最近のGurobiもGPUを使い始めたのは知りませんでした。

Simplex、内点法、FirstOrderの比較考証もされています。Simplexのマルチスレッド化は、LU分解のパラレル化が困難でした。Julian Hall教授の実装もありますが、CPUキャッシュに収まりきれないと性能が出ない問題があります。また、従来IPMにしてもスパースコルスキー分解を上手くGPUに載せるのは、難しいと考えられてきました。

ここにきて、FirstOrderは、激しく性能向上争いが続いていて、ADMMを用いた方法も注目しています。

An Enhanced Alternating Direction Method of Multipliers-Based Interior Point Method for Linear and Conic Optimization | INFORMS Journal on Computing

以上のトレンドを鑑みて、GPUによる実装を検討してみようと思います。（あくまで記録更新用なので、一般の実装には影響しません。ABIP+にせよPDLPにせよ、ユーザにとっては、精度と速度が出れば何でもよいです。）

＜Simplexは必要ないか？＞

依然として必要です。なぜなら、HotStart（WarmStart）によく駆動は、Simplexによるからです。INRC2規模では、Simplexのhoststartによる方が速いのでSimplexは欠かせません。一方、超大規模、SchedulingBenchmarksのInstance23/24規模になると、SimplexはHotstartを使っても無力です。この場合、内点法かFirstOrderによる方法となります。（FirstOrderによるHotStartは、Starandmarkさんの論文にあるのですが、大して効果がなかったような印象が残っています。）

上記論文で使われているGPUは、とんでもなく高価なものですが、上のような背景の私の用途としては、普通の世代落ちしたもので十分効果があるだろう、と見ています。

CUDAが使えるＧＰＵは、以下のページで分かります。

CUDA GPUs - Compute Capability | NVIDIA Developer

とりあえず、GPUを購入して勉強・評価して、COPTを使用するかどうかを判断したいと思います。

AIの流行により、一気に花開いたGPUですが、アークテクチャを見ると、ハードウェアとソフトウェア（コンパイラ技術）の見事なバランス感覚で成り立っており、両分野に精通した人の設計なんだろうな、と思います。CPUでマルチスレッドにするとキャッシュメモリがボトルネックとなり、その部分を分離できるという意味においても一時の流行に終わることがなく、今後も汎用化が加速していくのでないかと推測します。