最大最小不等式

最大最小不等式

数学における最大最小不等式（英: max-min inequality）は、2つの集合$Z$と$W$上の実数値関数$f: Z \times W \to \mathbb{R}$に対して常に成り立つ基本的な関係を示すものです。特に、関数が取る値の上限（supremum, $\sup$）と下限（infimum, $\inf$）を考える際に重要となります。

不等式の定義

空でない集合$Z$および$W$上の任意の関数$f: Z \times W \to \mathbb{R}$に対し、次の不等式が成り立ちます。

$$ \sup_{z\in Z}\inf_{w\in W}f(z,w) \leq \inf_{w\in W}\sup_{z\in Z}f(z,w) $$

ここで、$\sup_{z\in Z}$は集合$Z$に関する上限、$\inf_{w\in W}$は集合$W$に関する下限を表します。左辺は「まず各$z$について$w$に関する$f(z,w)$の下限を取り、次にその結果を$z$について上限をとった値」です。一方、右辺は「まず各$w$について$z$に関する$f(z,w)$の上限を取り、次にその結果を$w$について下限をとった値」を表しています。

不等式の意味

この不等式は、上限と下限をとる操作の順序が結果に影響する可能性があることを示唆しています。左辺は「まず内側の下限を計算し、次いでその上限を計算する」操作であり、右辺は「まず内側の上限を計算し、次いでその下限を計算する」操作です。この不等式は、常に前者（$\sup \inf$）が後者（$\inf \sup$）以下になることを保証しています。直感的には、内側で「最も悪い状況（下限）」を考慮した上で「最も良い結果（上限）」を目指す場合と、内側で「最も良い状況（上限）」を想定した上で「最も悪い結果（下限）」を避ける場合とを対比させることができます。最大最小不等式は、前者のアプローチが後者のアプローチよりも不利にならない（または同等である）という一般的な性質を示しています。

証明

最大最小不等式は以下の手順で証明できます。

1. 各$z \in Z$に対して、$g(z) = \inf_{w\in W}f(z,w)$と定義します。これは、$z$を固定したときの関数$f(z, \cdot)$の下限です。
2. 下限の定義から、任意の$z \in Z$および任意の$w \in W$に対して、$g(z) \leq f(z,w)$が成り立ちます。これは、$g(z)$が$f(z,w)$の下界であることを意味します。
3. この不等式$g(z) \leq f(z,w)$の両辺について、$z$に関する上限をとります。任意の固定された$w \in W$に対し、上限の性質より、$\sup_{z\in Z}g(z) \leq \sup_{z\in Z}f(z,w)$が得られます。
4. ここで、$g(z)$の定義を代入すると、$\sup_{z\in Z}(\inf_{w\in W}f(z,w)) \leq \sup_{z\in Z}f(z,w)$となります。この不等式は任意の$w \in W$に対して成立します。
5. 左辺$\sup_{z\in Z}(\inf_{w\in W}f(z,w))$は$w$に依存しない定数です。この定数が、任意の$w \in W$に対する値$\sup_{z\in Z}f(z,w)$の集合の下界になっていることがステップ4で示されました。集合の下界の中でも最大の値である下限（infimum）は、その集合の任意の下界以上であるという下限の定義から、左辺は右辺の$w$に関する下限以下でなければなりません。したがって、$\sup_{z\in Z}(\inf_{w\in W}f(z,w)) \leq \inf_{w\in W}(\sup_{z\in Z}f(z,w))$が成り立ちます。$\square$

強最大最小性（鞍点性）

最大最小不等式において等号、すなわち

$$ \sup_{z\in Z}\inf_{w\in W}f(z,w) = \inf_{w\in W}\sup_{z\in Z}f(z,w) $$

が成り立つ場合、関数$f$および集合$Z, W$は強最大最小性、または鞍点性を満たすと言われます。この等号が成り立つ状況は、ゲーム理論における均衡点や、最適化問題における強力な双対性など、多くの応用分野で重要な意味を持ちます。

関連項目

最小最大定理 (ミニマックス定理)

参考文献

Boyd, Stephen; Vandenberghe, Lieven (2004), Convex Optimization, Cambridge University Press
* "Max Min of function less than Min max of function", Math StackExchange

もう一度検索