wiisメモ（凸集合～対応）
前回の続き
mathjax
- コピペ用ゼロ幅空白｢｣
凸集合
- 凸結合（convex combination）: 線形結合の一種で、すべてのスカラーが非負で総和が1であるもの、つまり
$$\displaylines{
\begin{align}
&(a) \forall i \in \{1, \dots, k\}: \lambda_{i} \geq 0 \\
&(b) \sum_{i=1}^{k} \lambda_{i} = 1
\end{align}
}$$
- 凸集合（convex set）: 対象のユークリッド空間の部分集合Aのどの2点をとっても、その2点間の要素がすべてその部分集合に含まれること、つまり
$$ \forall x_{1} \in A, \forall x_{2} \in A, \forall \lambda \in [0,1]: \lambda x_{1} + (1-\lambda)x_{2} \in A $$
- ↑は図形的に言えば、凹になってる部分がないこと
- 狭義凸結合（strictly convex combination）: スカラー $\lambda_{i}$ に0を許容しない場合
- 狭義凸集合（strict convex set）: 2つの異なる任意の点の狭義凸結合が内点になること
- 凸集合と狭義凸集合は閉集合と開集合の関係にも似ている
- 閉近傍が狭義凸集合であるのは狭義凸結合のスカラーに0を許容しないため。$[0,1]^{n}$ で $n=1$ のときは同じ理由で狭義凸集合だが、 $n\geq 2$ のときは狭義凸集合でない
- 凸包（convex hull）: 凸集合とは限らない部分空間Aの要素をすべて含む別の集合の中で、凸集合になる最小の部分集合のことで、以下のように書く
$$ \text{Conv}(A) $$
- 凸包は任意個の任意の凸結合の集合で導くことができる、つまり
$$ \text{Conv}(A)= \left\{ \sum_{i=1}^{k} \lambda_{i}x_{i} \mid k \in \mathbb{N} \land \sum_{i=1}^{k} \lambda_{i}=1 \land \forall i \in \{1,\dots,k\}: (\lambda_{i} \geq 0 \land x_{i} \in A) \right\} $$
- 凸集合のスカラー倍は凸集合
- 凸集合のミンコフスキー和も凸集合
- 集合の線形結合を考えることもできて、それが凸集合と同じ条件（スカラーが非負でその総和が1）を満たす場合、凸結合（convex combination）という
- 集合の直積は組み合わせをそのままがっちゃんこして次元がまるごと足される、つまり
$$ A_{1} \times A_{2} = \{(x_{1}, x_{2}) \in \mathbb{R}^{n+m} \mid x_{1} \in A_{1} \land x_{2} \in A_{2}\} $$
- 凸集合の共通部分は凸集合だが、凸集合の和集合は凸集合とは限らない
- 超平面（hyperplane）: aとの内積の結果がcになるベクトルxの集合、つまり
$$ H(a,c)=\{x \in \mathbb{R}^{n} \mid a \cdot x = c\} $$
- ↑は1次元では点、2次元では線、3次元では（直感的な）平面に相当し、4次元以降のn次元ではn-1次元の存在を表すので、対象次元から1次元下のものを一般化した概念
- 点 $x_{1}$ と超平面 $H(a,c)$ のと距離は
$$ {|a \cdot x_{1} - c| \over \|a\|} $$
- ここで、aが単位ベクトルで、x1が原点の場合、結果が $|c|$ になるので、スカラーcがこの条件の距離に相当する
- 上半空間（halfspace above～）: $H^{+}(a,c)=\{x \in \mathbb{R}^{n} \mid a \cdot x \geq c\}$
- 下半空間（halfspace below～）: $H^{-}(a,c)=\{x \in \mathbb{R}^{n} \mid a \cdot x \leq c\}$
- さらに、それぞれ超平面を含まない空間も定義できる
- 上開半空間（open halfspace above～）:$H^{++}(a,c)=\{x \in \mathbb{R}^{n} \mid a \cdot x > c\}$
- 下開半空間（open halfspace below～）:$H^{--}(a,c)=\{x \in \mathbb{R}^{n} \mid a \cdot x < c\}$
- 点xが超平面 $H(a,c)$ に含まれることは、超平面上の点 $x_{0}$ を任意に取り、 $a$ と $x-x_{0}$ のなす角が直角であることと必要十分、つまり
$$ x \in H(a,c) \iff a \cdot (x - x_{0}) = 0 $$
- ↑は等号を置き換えることで各種半空間に対応した命題になる
- 集合Xと点yが狭義分離される（strictly separated）とは、片方が上開半平面、もう片方が下開半平面に属すること
狭義分離超平面定理（strictly separating hyperplane theorem）: Xが凸集合で、yがXの外点ならば、狭義分離する超平面が必ず存在する、つまり $$ y \in H^{++}(a,c) \land X \subset H^{--}(a,c) $$ と $$ a \cdot y > c \land (\forall x \in X: a \cdot x < c) $$ を満たすa,cが必ず存在する
↑の式をまとめると、 $\forall x \in X: a \cdot x < a \cdot y$ つまり $\forall x \in X: a \cdot (x-y) = 0$ となり、これはyからxへのベクトルと鋭角をなすベクトルaが必ず存在することを意味する
- 狭義分離超平面定理のなかで、aとcを-1倍しても同じ超平面が得られる。ただし、上半空間と下半空間は逆転する
- 支持超平面（supporting hyperplane）: 超平面で分割された片方の半平面に部分集合Xがすべて含まれていて、そのXの境界点が超平面上にある場合をいう
- Xが凸集合の場合、その任意の境界点yでXを支持する超平面が必ず存在する
- ↑を式でいうと $$a \cdot y = \forall x \in X : a \cdot x \leq c$$ で、まとめると $$\forall x \in X: a \cdot x \leq a \cdot y$$ つまり $$\forall x \in X: a \cdot (x-y)\leq 0$$ となり、これはyからxへのベクトルと直角or鈍角になるベクトルaの存在が保証されることを意味する
- 分離超平面定理（separating hyperplane theorem）: 狭義分離超平面定理の $>$ を $\geq$ にしたもの
- 分離超平面定理（separating hyperplane theorem）or ミンコフスキーの定理（Minkowski’s theorem）: 2つの重複のない凸集合を分離する超平面が必ず存在する。式でいうと
$$ \forall x \in X, \forall y \in Y: a \cdot x \leq c \leq a \cdot y $$
凸関数
- 凸関数（convex function）: 定義域のどの2点を結んでも、その線が実際のグラフと同じかそれより上にくること、式で表すと
$$ \forall x_{1}, x_{2} \in I, \forall \lambda \in [0,1]: \lambda f(x_{1}) + (1-\lambda) f(x_{2}) \geq f(\lambda x_{1} + (1-\lambda) x_{2}) $$
- ↑は下に凸な関数（convex downward function）ともいう
- $y=x^{2}$ などは典型例だが、それ以外にも $y=x$ のような直線の式も凸関数の定義に合致する
- 絶対値関数など、凸関数であってもすべての点で微分可能とは限らない
- 凹関数（concave function）: 凸関数の不等号を逆にしたもの
- ↑は別名、上に凸な関数（convex upward function）
- 関数をnegateすることで凸関数と凹関数は相互変換可能
- 凸関数が微分可能な場合、定義域の接線が常に下になる、つまり $f(x_{2}) \geq f'(x_{1})(x_{2}-x_{1}) + f(x_{1})$
- 同時に、凸関数が微分可能な場合は導関数が単調増加関数であり、逆も成り立つ
- さらに、凸関数が2階微分可能な場合、 $\forall x \in I: f''(x) \geq 0$ が成り立つ
- 凹関数の場合はここまでの話を符号を反転させれば成り立つ
- エピグラフ（epigraph）: 関数のグラフ $G(f)$ の上部 $\text{epi}(f)=\{(x,y) \in I \times \mathbb{R} \mid y \geq f(x) \}$
- エピグラフが凸集合であることと、関数が凸関数であることは必要十分（関数に微分不可能な点があるときに有用）
- ハイポグラフ（hypograph）: エピグラフの逆 $\text{hyp}(f)=\{(x,y) \in I \times \mathbb{R} \mid y \leq f(x) \}$
- ハイポグラフが凸集合であることと、凹関数であることは必要十分
- 狭義凸関数（strictly convex function）: 凸関数の定義で、区間の端点が一致しないことと区間の端点を定義に含めないバージョン
$$ \forall x_{1} \in I, \forall x_{2} \in I \setminus \{x_{1}\}, \forall \lambda (0,1): \lambda f(x_{1}) + (1-\lambda)f(x_{2}) > f(\lambda x_{1} + (1-\lambda)x_{2}) $$
- ↑は直線は含まなくなる
- 狭義凹関数（strictly concavefunction）も同様
- 微分による狭義凸関数判定も、不等号を狭義不等号にすれば成り立つ
- エピグラフ・ハイポグラフによる狭義凸関数判定も、凸集合であることという条件を狭義凸集合であることに置き換えれば成り立つ
- 以上の議論は多変数関数（vec 2 scalar）でも同様
- 多変数関数の場合、ある関数が凸関数であることはその関数の成分関数全てが凸関数であることと必要十分
- 微分を用いた凸関数の判定は、微分の代わりに偏微分を用いる、つまり
$$ \forall x, y \in X : f(Y) \geq \nabla f(x) \cdot (y-x) +f(x) $$
ただし、↑は $C^{1}$ 級の場合で、 $C^{2}$ 級の場合はヘッセ行列が半正定値（固有値がすべて非負）であること、つまり以下と必要十分と判別してもよい $$ \forall x \in X, \forall h \in \mathbb{R}^{n} \setminus \{0\}: h^{t} H_{f}(x) h \geq 0 $$ ここで、$H_{f}(x)$ は $$ H_{f}(x)= \left( \begin{array}. f''_{x_{1}x_{1}}(x) & f''_{x_{1}x_{2}}(x) & \dots & f''_{x_{1}x_{n}}(x) \\
f''_{x_{2}x_{1}}(x) & f''_{x_{2}x_{2}}(x) & \dots & f''_{x_{2}x_{n}}(x) \\
\vdots & \vdots & \ddots & \vdots \\
f''_{x_{n}x_{1}}(x) & f''_{x_{n}x_{2}}(x) & \dots & f''_{x_{n}x_{n}}(x) \\
\end{array} \right) $$また、半正定値であることを確認する代わりに、すべての首座小行列（行列の左上からk行k列までを取り出したもの）の行列式が非負であることを確認してもよい、つまり $$ \forall x \in X, \forall k \in \{1,\dots,n\}: \det (A_{k}(x)) \geq 0 $$ ただし、 $A_{k}(x)$ は、k次の首座小行列
凸関数は定数倍しても凸関数。ただし0倍だけは狭義凸関数の要件を失う
- 凸関数と単調増加関数の合成関数も凸関数、凹関数と単調増加関数の合成関数も凹関数。
- 一方で単調減少関数との合成関数は凹凸が逆転する
- 単調増加な凸関数の逆関数は凹関数だが、単調減少な凸関数の逆関数は凸関数のまま
- 凹関数も同様に、単調増加なら逆関数は逆転して凸関数になるが、単調減少なら逆関数も凹関数
- 2つの関数が凸関数なら、その最大値(max)を取る関数も凸関数
- 2つの関数が凹関数なら、その最小値(min)を取る関数も凹関数
- 1次関数は凸関数かつ凹関数
- 指数関数は狭義凸関数
劣勾配（subgradient）: （凸関数の場合）ある点での関数より下で取れる傾きすべての集合。微分可能な点ではそのような傾きは一意に定まって通常の微分係数と同じ値になり（少しでもずれると関数の上側を通ってしまうから）、微分不可能点では区間になる。（なので微分係数の一般化ともみなせる） 式でいうと $$ \forall x \in I : f(x) - f(x_{0}) \geq c (x - x_{0}) $$ を満たすcのこと
↑は凹関数でも上下反転させて同様の定義が可能
- 劣勾配全体の集合を劣微分（subdifferential）といい、 $\partial f(x)$ と書く
- たとえば、関数 $y=|x|$ での劣微分は
$$
\begin{eqnarray}
\partial f(x)=
\begin{cases}
\{1\} & (x>0) \\
[-1,1] & (x=0) \\
\{-1\} & (x<0)
\end{cases}
\end{eqnarray}
$$
正の無限大を含む拡大実数値関数 $f: \mathbb{R}^{n} \to \mathbb{R} \cup \{+\infty\}$ の有効領域（effective domain）を無限大でない領域、つまり $$ \text{dom}(f)=\{x \in \mathbb{R}^{n} \mid f(x) < +\infty \} $$ とすると、凸関数の有効領域は凸集合であるということができる
定義域を $\text{dom}(f)$ に制限した関数が凸関数であることと、元の関数が凸関数であることは必要十分
- 以上の議論は多変数関数でも可能で、「微分可能なら微分に一致する」の部分は「全微分可能なら全微分に一致する」に読み替える
準凸関数
- 準凸関数（quasi-convex function）: 2点間のどの値も2点の最大値を超えない関数、つまり
$$ \forall x_{1}, x_{2} \in I, \forall \lambda \in [0,1]: f(\lambda x_{1} + (1-\lambda)x_{2}) \leq \max\{f(x_{1}), f(x_{2})\} $$
- 準凸関数は上に凸も下に凸もあり得る
- 準凹関数（quasi-concave function）も同様に定義可能
$$ \forall x_{1}, x_{2} \in I, \forall \lambda \in [0,1]: f(\lambda x_{1} + (1-\lambda)x_{2}) \geq \min\{f(x_{1}), f(x_{2})\} $$
- 準線型関数（quasi linear function）: 準凸かつ準凹であること、つまり
$$ \forall x_{1}, x_{2} \in I, \forall \lambda \in [0,1]: \min\{f(x_{1}), f(x_{2}) \leq f(\lambda x_{1} + (1-\lambda)x_{2}) \leq \max\{f(x_{1}), f(x_{2}) \} $$
- ちなみに思い出すと、線型関数は1次関数のこと、なので準線型関数は準1次関数と言ってもいいかも
- 準線型関数の例： $f(x)=\ln{(x)}$、1次関数、単調関数など
- $C^{1}$ 級である場合、2点を取って、「上の点から下の点へのベクトル」と「上の点の接線」とが直角または鈍角をなすことは、準凸関数であることと必要十分、つまり
$$ \forall x_{1}, x_{2} \in I: [f(x_{1}) \leq f(x_{2}) \implies (x_{1} - x_{2}) \cdot f'(x_{2}) \leq 0] $$
- 準凹関数は↑で直角または鋭角であることと必要十分
- 下位集合（lower level set）or 劣位集合（sublevel set）: f(x)の値が一定値以下であるxの集合
$$ L(x)=\{x \in I \mid f(x) \leq c\} $$
- 下位集合が凸集合であることは、準凸関数であることと必要十分
- 上位集合が凸集合であることは、準凹関数であることと必要十分
- 狭義準凸関数・狭義準凹関数は、定義の $\leq, \geq$ をそれぞれ $<,>$ にする
- 狭義準凸関数の判定も、微分、上位集合による手法が流用できる
- 多変数関数の場合の準凸関数の判定法
- $C^{1}$ 級である場合、2点を取って、「上の点から下の点へのベクトル」と「上の点の接線」とが直角または鈍角をなすことは、準凸関数であることと必要十分、つまり $$ \forall x,y \in I: [f(x) \leq f(y) \implies (x-y) \cdot \nabla f(x) \leq 0] $$
- $C^{2}$ 級の場合、全微分と垂直なベクトルhを使うと、ヘッセ行列が半正定値になること、つまり $$ \forall x \in X, \forall h \in \mathbb{R}^{n} \setminus \{0\}: [\nabla f(x) \cdot h = 0 \implies h^{t}H_{f}(x)h\geq 0] $$
- また↑の言い換えで、縁付きヘッセ行列の任意の首座小行列の行列式が非負であることと必要十分、つまり $$ \forall x \in X, \forall k \in \{1,\dots,n\}: \det(A_{k}(x)) \geq 0 $$
- （※↑で縁付きになる理由は？あと数式間違ってない？）
- 縁付きヘッセ行列 or 境界つきヘッセ行列 (bordered Hessian) : 関数fの2階偏微分の微分係数を列挙した行列であるヘッセ行列の左上サイドに新たに関数gの1階微分の係数を追加したもの、つまり
$$
D_{f}(x)=
\left(
\begin{array}.
0 & {\partial g \over \partial x_{1}} & {\partial g \over \partial x_{2}} & \dots & {\partial g \over \partial x_{n}} \\
{\partial g \over \partial x_{1}} & {\partial f \over \partial x_{1}^{2}} & {\partial f \over \partial x_{1}x_{2}} & \dots & {\partial f \over \partial x_{1}x_{n}} \\
{\partial g \over \partial x_{2}} & {\partial f \over \partial x_{2}x_{1}} & {\partial f \over \partial x_{2}^{2}} & \dots & {\partial f \over \partial x_{2}x_{n}} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
{\partial g \over \partial x_{n}} & {\partial f \over \partial x_{n}x_{1}} & {\partial f \over \partial x_{n}^{2}} & \dots & {\partial f \over \partial x_{n}x_{n}} \\
\end{array}
\right)
$$
- ↑でfとgは一致してもよく、また追加する行・列は2段以上でもよい
- 準凹関数の判定では、角とヘッセ行列は不等号の判定で、行列式判定の場合は行列式の値に $(-1)^{k}$ をかけて不等号はそのまま、つまり $$ \forall x \in X, \forall k \in \{1,\dots,n\}: (-1)^{k}\det(A_{k}(x)) \geq 0 $$
- 開集合が凸集合なら準凸関数、という条件は多変数関数でも同じ
凸最適化
- fのXにおける最小点からなる集合を以下のように書く
$$ \text{argmin}_{x \in X}f(x)= \left\{ a \in X \mid f(a)=\min_{x \in X}f(x) \right\} $$
凸最適化（convex optimization）or 凸計画問題（convex programming）: 関数の値域を凸集合Cに制限した場合の最小化問題、つまり $$ \text{argmin}_{x \in C}f(x) $$ を特定する問題で、以下のように書く $$\displaylines{ \min & f(x) \\
\text{s.t.} & x \in C }$$↑のとき、Cを制約集合（constraint set）、fを目的関数（objective function）という
- 逆に、最大値を求める問題は凹最適化（concave optimization）という
- $x_{0}$ が最小化問題の解なら、劣微分が0、つまり $0 \in \partial f(x_{0})$ で、逆も成り立つ（劣微分が0なら最小化問題の解である）
- Cがすべての点で微分可能なら、劣微分を使わず通常の微分でもよい
- 多変数関数の場合でも劣微分を用いて解決可能で、全微分可能なら全微分でもよい
対応
- 対応（correspondence）: 写像が1つの要素に対して1つの要素を定める規則なのに対し、対応は1つの要素に対して1つの部分集合を定める規則で、 $f:A \twoheadrightarrow B$ と書く
- 対応は別名、多価関数（multivalued function）ともいう。複数の要素を定めるものとみなすことで
- また更に、集合関数（set function）ともいう。 $f:A \twoheadrightarrow B$ が $f:A \to 2^{B}$ と同一視できることから
- 対応は直積の部分集合でもある
- 見た目的には、xyグラフ上では写像が線、対応が中身の詰まった何らかの図形
- 上逆像（upper inverse image）or 強逆像（strong inverse image）: 対応 $f:A \twoheadrightarrow B$ があるとき、対応の結果がBの部分集合Yに含まれるようなAの要素、つまり終集合をYに限った逆像。式でいうと
$$ f^{+}(Y)=\{a \in A \mid f(a) \subset Y\} $$
- （一般の逆像は $f^{-1}(B)$ のように表記しているが上逆像の表記は逆像要素がパっと見消えている。 $f^{-1+}(Y)$ とか $f^{-1\cap}(Y)$ とかにしたほうが明示的な気もするが、それはまあ。）
- ただし、↑は1つの要素が上逆像に該当するためには、その対応の結果すべてがYに含まれていなければならない、図形的に言えばはみ出してはならない
- 下逆像（lower inverse image）or 弱逆像（weak inverse image）: 上逆像とは異なり、わずかでも部分集合Yに含まれる要素の集合、つまり
$$ f^{-}(Y)=\{a \in A \mid f(a) \cap Y \neq \phi \} $$
- Bの部分集合をB自身にしたとき、始集合・定義域・上逆像・下逆像はすべて一致する、つまり
$$ A=D(f)=f^{+}(B)=f^{-}(B) $$
- f(a)が空集合でないときは $f^{+}(Y) \subset f^{-}(Y)$ が成り立つが、対応の結果が空集合なものを含む場合、それは上逆像には該当する一方で下逆像には該当しなくなってしまうので、先の式が成り立たなくなる
- 逆対応（inverse correspondene）: 対応における逆写像の概念 $f^{-1}:B \twoheadrightarrow A$ でその像は $f^{-1}(b)=\{a \in A \mid b \in f(a) \}$
- 逆対応は常に定義可能。逆写像の場合は値が空集合になることは許されなかったが、対応の場合は値が部分集合として定義され、空集合は任意の部分集合の要素であるため、たとえ逆対応の結果が空集合になったとしても定義上支障がない
- 対応のグラフと逆対応のグラフは、それぞれa,bを入れ替えて得られるものと一致する、つまり $G(f^{-1})=\{(b,a) \in B \times A \mid (a,b) \in G(f)\}$
- 定義域は値域の逆像に一致し、定義期の逆像は値域と一致する、つまり
$$\displaylines{
D(f)=R(f^{-1}) \\
D(f^{-1})=R(f)
}$$
- 対応の連続性...関数の連続性の一般化。上半連続性と下半連続性にわかれる
- 上半連続（upper hemi-continuous）: $f:A \twoheadrightarrow B$ があるとき、Aの点aを考える。f(a)の開近傍UをB上で自由に選択し、さらにaの開近傍Vも選択する。このときVの要素の対応がすべてUの要素になる場合、つまり $f(a) \subset U \subset B$ のときに $\forall v \in V: f(v) \subset U$ が成り立つ場合、対応fは点aにおいて上半連続という
- 下半連続（lower hemi-continuous）: 上半連続と同様にまず、$f:A \twoheadrightarrow B$ があるとき、Aの点aを考える。f(a)と重複部分を持つ開集合UをB上で自由に選択し、さらにaの開近傍Vも選択する。このときVの要素の対応がすべてUとの重複部分を持っている場合、つまり $f(a) \cap U \neq \phi \land U \subset B$ のときに $\forall v \in V: f(v) \cap U \neq \phi$ が成り立つ場合、対応fは点aにおいて下半連続という
- 上半連続かつ下半連続の時、その対応は連続であるという
- 対応fが上半連続であることと、（終集合の部分集合としての）開集合の上逆像が開集合であること、（同じく終集合の部分集合としての）閉集合の下逆像が閉集合であることはそれぞれ必要十分
- 対応fが下半連続であることと、（終集合の部分集合としての）開集合の下逆像が開集合であること、（同じく終集合の部分集合としての）閉集合の上逆像が閉集合であることはそれぞれ必要十分
- 閉グラフ（closed graph）: 閉集合なグラフ
- 対応 $f:A \twoheadrightarrow B$ で、始集合内の数列の極限がAに含まれ、またそれによって定まる終集合内の数列の極限がやはりBに含まれるとき、fは点aにおいて閉じているという
- 対応fが閉じていることと、閉グラフを持つことは必要十分
- 対応fが閉グラフを持ち、終集合Bがコンパクトなら、fは上半連続
- 話はいったん写像に戻って、写像fが連続なら最大値・最小値を持つが、この主張は分割することができて、上半連続なら最大値を、下半連続なら最小値を持つ、という2つの命題に分けることができる
- 関数 $f:X \times A \to \mathbb{R}$ を対応 $g:A \twoheadrightarrow X$ で制限した制約付き最大化問題を考えると、これは $$ \sup_{x \in X} f(a,x) \quad \text{s.t.} \quad x \in g(a)$$ と表記できるが、ここでfに渡すxはgによって定義されるので、Xは任意の点で定義されている必要はなく、gの定義域さえカバーしていればそれでいい。さらに、gに渡すaもg自身によって制限されているので、Aも任意の点において定義されている必要はなく、結局fの定義域はgのグラフと同一になる、つまり $f: G(g) \to \mathbb{R}$ と表記できる
- ここでAをパラメータ集合（parameter space）、gを制約対応（constraint correspondence）、g(a)を制約集合（constraint set）、f(a,x)を目的関数（objective function）と呼ぶ
- 価値関数（value function）or 包絡面関数（envelope plane function）: aによって変化する最大値の集合自体を関数にしたもの、つまり $$V(a)=\sup\{f(a,x) \in \mathbb{R} \mid x \in g(a) \}$$
- ただしここで、価値関数Vの終集合は拡大実数系 $\mathbb{R}^{*}=\mathbb{R} \cup \{\pm\infty\}$ とする。制約集合が空集合だった場合の値を $-\infty$ と定めたいので。
- 最適選択対応（optimal choice correspondence）: 最大化問題の解からなる集合を定める対応 $$X^{*}(a) =\{x \in g(a) \mid f(a,x)=V(a) \}$$
- 最適選択対応の中でも解をもつaを集めた集合を $A^{*}=\{ a \in A \mid X^{*}(a) \neq \phi \}$ と書く
- 選択子（selection）: $A^{*}$ の中から解を選び取る写像、つまり $x^{*}(a) \in X^{*}(a)$ を定める $x^{*}: A^{*} \to X$
- まとめると、以下が成り立つ $$\forall a \in A^{*}: f(x^{*}(a),a) = V(a)$$
- 目的関数fが上半連続で、制約対応gが非空値かつコンパクト値を取る場合、価値関数V(a)は実数値関数となり、最適選択対応X*も非空値かつコンパクト値を取る
- ↑に追加して、gも上半連続である場合、価値関数V(a)も上半連続となる
- 一方で、V(a)が下半連続であるためには、fとgが下半連続であればよい（コンパクトである必要はない）
- ベルジュの最大値定理（Berge maximum theorem）: fが連続、gも連続で非空値かつコンパクト値を取る場合、Vは連続となり、X*も非空値かつコンパクト値を取る連続対応になることが保証される
