離散凸解析

前に何かで知って気になってたので勉強してみた。

離散凸解析の考えかた 最適化における離散と連続の数理

簡単に言うと
が下に凸ならば「が最小値 <-> 」
などの連続関数に関する定理の離散関数版を考えるとかいった話。

んで, 離散関数にもいろいろあるらしく凸関数とか凸関数とか沢山でてきてはっきりいって全然理解できていないわけだけども, 連続世界と離散世界を自由自在に行ったり来たりできるスキルを身につけられたら面白いだろうなぁと感じた。

特に, 面白そうだと思ったのは最小費用流問題の項で, この本には詳しく書いていなかったのだけれども, フロー <-> 電流, テンション <-> 電圧, コスト <-> エネルギーといった対応により最小費用流問題は非線形抵抗からなる電気回路の問題と対応させることができるのだとか。そしたら, 今度は回路に関して成立する他の定理を離散化する事で, 最小費用流問題に関する別の解釈を自然に得る事ができるんだろう。

当然, コンパイラでの最適化に使えないか考えるわけですが, 例えばデータフロー方程式は直感的に何らかの保存則(流量保存則)に対応するだろうと思えます。するとデータフロー方程式を利用する種々の最適化は, 何らかの保存則が成り立つ一つの系の上での何らかの物理量の最小化問題に対応させて統一的に理解できるのではないかと思うわけです。

つまり

• A最適化 <-> 系Xでの物理量Pの最小化
• B最適化 <-> 系Xでの物理量Qの最小化

みたいに異なる最適化を一つの同じ系X上の問題とみなすことができるはずだと...。
例えば帰納変数除去とか共通部分式除去を部分冗長性除去が内包しているという事実も, 上のような見方ですっきり理解できそうな気がする。

それから例えばレジスタ割り当てはグラフカラーリング問題と同じわけでNP完全なのだけれども,
凸関数じゃないものに対しては離散凸解析は無力なのだろうか。あとNP完全であることと凸関数でないということは同値ではないのだと思うのだけど, よく分からなかった。

とりあえずもうちょっと勉強してみたいと思った。どうするのがいいだろう。
てか離散凸解析より前に凸解析を勉強すべきか。