最近、劣モジュラ最適化と機械学習という本を買いました。その2章まで読んだので、劣モジュラ関数の最小化を試してみます。ちなみに2章は最小化、3章は最大化がテーマです。 劣モジュラ 集合を入力とする関数f()が劣モジュラ性(Sub modular)を持つのは以下の不等式を満たすときです。 $$ \begin{equation} f(S)+f(T)\geq f(S \cup T)+f(S \cap T) (\forall S,T \subseteq V) \end{equation} $$ ここでVはとりうる最大の集合で、V={1}とか{1,2}とか{1,2,3}とかです。SとTはそれに含まれる集合なのでV={1,2,3}のときS={1,2}などがあり得ます。具体的な意味は[3]がわかりやすいです。イメージとしては大きな集合を入力したときほど、新たな要素を追加しても変化が小さい関数が劣モジュラ関
![劣モジュラ関数最小化のお勉強(Minimum Norm Point) - wildpieの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/9df855d4eba3ba8ae61acdbfe77af336a7b0a36a/height=288;version=1;width=512/http%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fw%2Fwildpie%2F20160131%2F20160131182547.jpg)