凸最適化 first-orderに注目

OR学会誌　6月号で、一次法の特集が組まれています。タイムリーな特集です。一次法の逆襲という的を得たタイトルです。

線形目的関数の世界では、Simplexと内点法が幅を利かせていますが、大規模な制約の場合、例えば、NSPで言うと6ヶ月とか1年とかになってくると、Simplexでは苦しくなってきます。そこで内点法の出番ですが、商用ソルバーはともかく手に入る実装では、やはり厳しいものがあります。そこで最近、注目しているのが、first-orderです。

http://www.orsj.or.jp/archive2/or64-6/or64_6_314.pdf
http://www.orsj.or.jp/archive2/or64-6/or64_6_316.pdf
http://www.orsj.or.jp/archive2/or64-6/or64_6_335.pdf

画像解析、機械学習で注目されていますが、NSPでは、未だ論文が発表されていません。

現在、SC3 algorithm4は、未完成です。汎用化まであと一歩なのですが、殆どの実用的な問題ではalrogithm1に負けます。優勢なのは、ほぼ学会ベンチマークのみです。しかし、実務問題の中でも大規模かつ複雑な最適化問題でalgorithm4は,より厳密解に近い解を得られる可能性があると見ています。実用的な意味で、algorithm1が最適なことは変わりありません。しかし、エラー数が多種、多様、多数ある場合、つまり探索時間が一桁・二桁余計にかかるような問題では、数理的なアプローチが有利になってくる、ということだと理解しています。

数理的なアプローチとしては、線形ソルバーを使うことになる訳ですが、今までは、Simplex・内点法のアプローチしか考えられなかったのですが、first orderソルバーも可能性が出てきた、ということです。