制約付き最大化問題

パラメータの値が与えられたときに、その値のもとで定まる制約集合と目的関数から制約付き最大化問題と呼ばれる問題を定義します。また、それに関連して、価値関数や最適選択対応、選択子などの概念を定義します。
次のページ >

制約付き最大化問題

集合\(A,B\)には位相が導入されているものとします。具体的には、距離空間やユークリッド空間などを想定してください。その上で、実数値関数\(f:A\times B\rightarrow \mathbb{R} \)と対応\(g:A\twoheadrightarrow B\)がそれぞれ与えられているものとします。点\(a\in A\)を任意に選ぶと、それを関数\(f\)に代入して得られる関数\(f:\left( a,\cdot \right) :B\rightarrow \mathbb{R} \)と、対応\(g\)が定める像\(g\left( a\right) \)がそれぞれ得られます。\(g\left( a\right) \)は\(B\)の部分集合であるため、\(g\left( a\right) \)に属する点の中でも\(f\left( a,\cdot \right) \)の値を最大化するようなものを特定する制約付き最大化問題\begin{equation*}
\sup_{b\in B}f\left( a,b\right) \quad \text{s.t.}\quad b\in g\left( a\right)
\end{equation*}すなわち、\begin{equation*}
\sup_{b\in g\left( a\right) }f\left( a,b\right)
\end{equation*}を構成できます。

対応\(g:A\twoheadrightarrow B\)のグラフは、\begin{equation*}
G\left( g\right) =\left\{ \left( a,b\right) \in A\times B\ |\ b\in g\left(
a\right) \right\}
\end{equation*}と定義されるため、順序対\(\left( a,b\right) \in A\times B\)を任意に選んだとき、\begin{equation*}
\left( a,b\right) \in G\left( g\right) \Leftrightarrow b\in g\left( a\right)
\end{equation*}という関係が成り立ちます。この事実を踏まえると、先の制約付き最大化問題を、\begin{equation*}
\sup_{b\in B}f\left( a,b\right) \quad \text{s.t.}\quad \left( a,b\right) \in
G\left( g\right)
\end{equation*}と言い換えることも可能です。したがって、このような制約付き最大化問題について考える際には、関数\(f\)は必ずしも\(A\times B\)上の任意の点において定義されている必要はなく、その部分集合である\(G\left( g\right) \)上において定義されていれば十分です。そこで以降では、関数\(f\)の定義域を縮小して、\begin{equation*}
f:G\left( g\right) \rightarrow \mathbb{R} \end{equation*}とします。\(f\)が\(G\left( g\right) \)上において定義されていれば、\(a\in A\)を任意に選んだとき、\(f\)は\(g\left( a\right) \)上の任意の点において定義されていることが保証されるため、先の制約付き最大化問題を考える上で問題は発生しません。

このモデルにおいて\(a\in A\)はパラメータ(外生変数)です。つまり、\(a\)の値が外生的に与えられると、それに応じて関数\(f\left( a,\cdot \right) :B\rightarrow \mathbb{R} \)と変数\(b\)が満たすべき条件\(b\in g\left( a\right) \)がそれぞれ定まり、その結果として、与えられた\(a\)の値に対応する制約付き最大化問題\(\sup\limits_{b\in g\left( a\right) }f\left( a,b\right) \)が得られます。言い換えると、\(a\)の値が変わればそれに対応する制約付き最大化問題も異なるものになるということです。このような事情を踏まえた上で、\(A\)をパラメータ集合(parameter space)と呼び、対応\(g\)を制約対応(constraint correspondence)と呼びます。また、パラメータの値\(a\)のもとで変数\(b\)がとり得る値の集合\(g\left( a\right) \)を\(a\)のもとでの制約集合(constraint set)と呼び、最大化の対象となる関数\(f\left( a,\cdot \right) \)を\(a\)のもとでの目的関数(objective function)と呼びます。外生的に与えられたパラメータの値\(a\)から制約付き最大化問題\(\sup\limits_{b\in g\left( a\right) }f\left( a,b\right) \)が構成され、その解として変数\(b\)の最適値が定まるという意味において、\(b\)はモデルの内生変数です。

繰り返しになりますが、パラメータ\(a\)の値が変化すればそれに応じて制約条件\(b\in g\left( a\right) \)や目的関数\(f\left( a,\cdot \right) :B\rightarrow \mathbb{R} \)はそれぞれ変化するため、制約付き最大化問題\(\sup\limits_{b\in g\left( a\right) }f\left( a,b\right) \)そのものも異なるものになります。以降では、パラメータ\(a\)の値が変化してもなお最大化問題\(\sup\limits_{b\in g\left( a\right) }f\left( a,b\right) \)に解が存在するための条件や、\(a\)の値を変化させたときの最大化問題の解集合がどのように変化するか、また、解のもとで実現する目的関数の最大値がどのように変化するかを分析します。

例(制約付き最大化問題)
関数\(f:\mathbb{R} _{+}^{2}\times \mathbb{R} _{+}\rightarrow \mathbb{R} \)はそれぞれの\(\left( a_{1},a_{2},b\right) \in \mathbb{R} _{+}^{2}\times \mathbb{R} _{+}\)に対して、\begin{equation*}
f\left( a_{1},a_{2},b\right) =b^{2}
\end{equation*}を定めるものとします。つまり、\(f\)は\(a_{1},a_{2}\)の値に依存せず、\(b\)のみを変数として持つ関数です。さらに対応\(g:\mathbb{R} _{+}^{2}\rightarrow \mathbb{R} _{+}\)はそれぞれの\(\left( a_{1},a_{2}\right) \in \mathbb{R} _{+}^{2}\)に対して、\begin{equation*}
g\left( a_{1},a_{2}\right) =\left\{ b\in \mathbb{R} _{+}\ |\ a_{1}b\leq a_{2}\right\}
\end{equation*}を定めるものとします。このとき、\(\left( a_{1},a_{2}\right) \in \mathbb{R} _{+}^{2}\)のもとでの制約付き最大化問題は、\begin{equation*}
\sup_{b\in \mathbb{R} _{+}}f\left( a_{1},a_{2},b\right) \quad \text{s.t.}\quad b\in g\left(
a_{1},a_{2}\right)
\end{equation*}すなわち、
$$\begin{array}{cl}
\sup\limits_{b} & b^{2} \\
s.t. & a_{1}b\leq a_{2} \\
& b\geq 0\end{array}$$

となります。具体的には、\(\left( a_{1},a_{2}\right) =\left( 1,2\right) \)に対応する最大化問題は、
$$\begin{array}{cl}
\sup\limits_{b} & b^{2} \\
s.t. & b\leq 2 \\
& b\geq 0\end{array}$$
であり、\(\left( a_{1},a_{2}\right) =\left( 3,8\right) \)に対応する最大化問題は、
$$\begin{array}{cl}
\sup\limits_{b} & b^{2} \\
s.t. & 3b\leq 8 \\
& b\geq 0\end{array}$$
となります。

例(制約付き最大化問題)
関数\(f:\mathbb{R} _{+}^{3}\times \mathbb{R} _{+}^{2}\rightarrow \mathbb{R} \)はそれぞれの\(\left( a_{1},a_{2},a_{3},b_{1},b_{2}\right) \in \mathbb{R} _{+}^{3}\times \mathbb{R} _{+}^{2}\)に対して、\begin{equation*}
f\left( a_{1},a_{2},a_{3},b_{1},b_{2}\right) =b_{1}^{\frac{1}{2}}b_{2}^{\frac{1}{2}}
\end{equation*}を定めるものとします。つまり、\(f\)は\(a_{1},a_{2},a_{3}\)の値に依存せず、\(b_{1}\)と\(b_{2}\)のみを変数として持つ関数です。さらに対応\(g:\mathbb{R} _{+}^{3}\rightarrow \mathbb{R} _{+}^{2}\)はそれぞれの\(\left( a_{1},a_{2},a_{3}\right) \in \mathbb{R} _{+}^{3}\)に対して、\begin{equation*}
g\left( a_{1},a_{2},a_{3}\right) =\left\{ \left( b_{1},b_{2}\right) \in \mathbb{R} _{+}^{2}\ |\ a_{1}b_{1}+a_{2}b_{2}\leq a_{3}\right\}
\end{equation*}を定めるものとします。このとき、\(\left( a_{1},a_{2},a_{3}\right) \in \mathbb{R} _{+}^{3}\)のもとでの制約付き最大化問題は、\begin{equation*}
\sup_{\left( b_{1},b_{2}\right) \in \mathbb{R} _{+}^{2}}f\left( a_{1},a_{2},a_{3},b_{1},b_{2}\right) \quad \text{s.t.}\quad
\left( b_{1},b_{2}\right) \in g\left( a_{1},a_{2},a_{3}\right)
\end{equation*}すなわち、
$$\begin{array}{cl}
\sup\limits_{\left( b_{1},b_{2}\right) } & b_{1}^{\frac{1}{2}}b_{2}^{\frac{1}{2}} \\
s.t. & a_{1}b_{1}+a_{2}b_{2}\leq a_{3} \\
& b_{1}\geq 0 \\
& b_{2}\geq 0\end{array}$$

となります。具体的には、\(\left( a_{1},a_{2},a_{3}\right) =\left( 1,2,8\right) \)に対応する最大化問題は、
$$\begin{array}{cl}
\sup\limits_{\left( b_{1},b_{2}\right) } & b_{1}^{\frac{1}{2}}b_{2}^{\frac{1}{2}} \\
s.t. & b_{1}+2b_{2}\leq 8 \\
& b_{1}\geq 0 \\
& b_{2}\geq 0\end{array}$$
であり、\(\left( a_{1},a_{2},a_{3}\right) =\left( \frac{1}{2},3,10\right) \)に対応する最大化問題は、
$$\begin{array}{cl}
\sup\limits_{\left( b_{1},b_{2}\right) } & b_{1}^{\frac{1}{2}}b_{2}^{\frac{1}{2}} \\
s.t. & \frac{b_{1}}{2}+3b_{2}\leq 10 \\
& b_{1}\geq 0 \\
& b_{2}\geq 0\end{array}$$となります。

 

価値関数

実数値関数\(f:A\times B\rightarrow \mathbb{R} \)と対応\(g:A\twoheadrightarrow B\)がそれぞれ与えられたとき、パラメータのそれぞれの値\(a\in A\)に対して制約付き最大化問題\(\sup\limits_{b\in g\left( a\right) }f\left( a,b\right) \)を構成できますが、\(a\)の値に応じてこの最大化問題も変化し得るため、最大化問題の解や、さらにはその解のもとで実現する目的関数\(f\left( a,\cdot \right) \)の最大値もまた\(a\)の値に応じて変化します。そこで、目的関数\(f\left( a,\cdot \right) \)の最大値そのものを\(a\)を変数として持つ関数とみなした上で、そのような関数を価値関数(value function)や包絡面関数(envelope plane function)などと呼びます。より正確には、価値関数とは、パラメータのそれぞれの値\(a\in A\)に対して、\begin{equation*}
V\left( a\right) =\sup \left\{ f\left( a,b\right) \in \mathbb{R} \ |\ b\in g\left( a\right) \right\}
\end{equation*}を像として定める拡大実数値関数\begin{equation*}
V:A\rightarrow \mathbb{R} ^{\ast }
\end{equation*}として定義されます。

価値関数\(V\)の終集合を実数空間\(\mathbb{R} \)ではなく拡大実数系\(\mathbb{R} ^{\ast }=\mathbb{R} \cup \left\{ \pm \infty \right\} \)としている理由は以下の通りです。対応\(g:A\twoheadrightarrow B\)は定義域の値\(a\in A\)に対して空集合を像として定めることがありますが、その場合、\(a\)に対応する最大化問題の制約集合\(g\left( a\right) \)が空集合になってしまいます。つまり、そのような\(a\)に対応する制約付き最大化問題は、\begin{equation*}
\sup_{b\in \phi }f\left( a,b\right)
\end{equation*}となり、価値関数\(V\)がそのような\(a\)に対して定める値は、\begin{equation*}
V\left( a\right) =\sup \left\{ f\left( a,b\right) \in \mathbb{R} \ |\ b\in \phi \right\}
\end{equation*}となってしまいます。このような場合、\begin{equation*}
V\left( a\right) =-\infty
\end{equation*}と定めるものとします。このような事情を踏まえた上で、価値関数\(V\)の終集合を拡大実数系\(\mathbb{R} ^{\ast }\)としています。

例(価値関数)
関数\(f:\mathbb{R} _{+}^{2}\times \mathbb{R} _{+}\rightarrow \mathbb{R} \)はそれぞれの\(\left( a_{1},a_{2},b\right) \in \mathbb{R} _{+}^{2}\times \mathbb{R} _{+}\)に対して、\begin{equation*}
f\left( a_{1},a_{2},b\right) =b^{2}
\end{equation*}を定め、対応\(g:\mathbb{R} _{+}^{2}\rightarrow \mathbb{R} _{+}\)はそれぞれの\(\left( a_{1},a_{2}\right) \in \mathbb{R} _{+}^{2}\)に対して、\begin{equation*}
g\left( a_{1},a_{2}\right) =\left\{ b\in \mathbb{R} _{+}\ |\ a_{1}b\leq a_{2}\right\}
\end{equation*}を定めるものとします。このとき、\(\left( a_{1},a_{2}\right) \in \mathbb{R} _{+}^{2}\)のもとでの制約付き最大化問題は、\begin{equation*}
\sup_{b\in \mathbb{R} }f\left( a_{1},a_{2},b\right) \quad \text{s.t.}\quad b\in g\left(
a_{1},a_{2}\right)
\end{equation*}すなわち、
$$\begin{array}{cl}
\sup\limits_{b} & b^{2} \\
s.t. & a_{1}b\leq a_{2} \\
& b\geq 0\end{array}$$
となります。この最大化問題の解は\(b=\frac{a_{2}}{a_{1}}\)であり、この解において目的関数\(b^{2}\)は最大値\(\left( \frac{a_{2}}{a_{1}}\right) ^{2}\)をとります。つまり、価値関数\(V:\mathbb{R} _{+}^{2}\rightarrow \mathbb{R} ^{\ast }\)はそれぞれの\(\left( a_{1},a_{2}\right) \in \mathbb{R} _{+}^{2}\)に対して、\begin{equation*}
V\left( a_{1},a_{2}\right) =\left( \frac{a_{2}}{a_{1}}\right) ^{2}
\end{equation*}を定めるということです。具体的な数値例を利用して検証すると、\(\left( a_{1},a_{2}\right) =\left( 1,2\right) \)に対応する最大化問題は、

$$\begin{array}{cl}
\sup\limits_{b} & b^{2} \\
s.t. & b\leq 2 \\
& b\geq 0\end{array}$$
ですが、この最大化問題の解は\(b=2\)であり、この解において目的関数\(b^{2}\)は最大値\(4\)です。実際、先に導出した価値関数\(V\)のもとでは、\begin{equation*}
V\left( 1,2\right) =\left( \frac{2}{1}\right) ^{2}=4
\end{equation*}となります。

 

最適選択対応

実数値関数\(f:A\times B\rightarrow \mathbb{R} \)と対応\(g:A\twoheadrightarrow B\)がそれぞれ与えられたとき、パラメータのそれぞれの値\(a\in A\)に対して制約付き最大化問題\(\sup\limits_{b\in g\left( a\right) }f\left( a,b\right) \)を構成できますが、\(a\)の値に応じてこの最大化問題も変化し得るため、最大化問題の解からなる集合もまた\(a\)の値に応じて変化します。そこで、最大化問題の解からなる集合そのものを\(a\)を変数として持つ対応とみなした上で、そのような対応を最適選択対応(optimal choice correspondence )と呼びます。より正確には、価値関数とは、パラメータのそれぞれの値\(a\in A\)に対して、\begin{equation*}
X^{\ast }\left( a\right) =\left\{ b\in g\left( a\right) \ |\ f\left(
b,a\right) =V\left( a\right) \right\}
\end{equation*}を像として定める対応\(X^{\ast }:A\twoheadrightarrow B\)として定義されます。ただし、\(V:A\rightarrow \mathbb{R} ^{\ast }\)は価値関数です。

パラメータの値\(a\in A\)が与えられたとき、それに対応する制約付き最大化問題\(\sup\limits_{b\in g\left( a\right) }f\left( a,b\right) \)には解は存在するとは限りません。解が存在しない場合には\(X^{\ast }\left( a\right) \not=\phi \)となります。また、パラメータの値\(a\)に対応する制約付き最大化問題に解が存在する場合、解は1つだけであるとは限りません。その場合、\(X^{\ast }\left( a\right) \)には複数の要素が含まれます。最適選択対応を写像ではなく対応として定義する理由には以上のような事情があります。

最適選択対応\(X^{\ast }:A\twoheadrightarrow B\)が与えられたとき、\(X^{\ast }\left( a\right) \not=\phi \)を満たす\(a\in A\)からなる集合を、\begin{equation*}
A^{\ast }=\left\{ a\in A\ |\ X^{\ast }\left( a\right) \not=\phi \right\}
\end{equation*}と表記します。つまり、\(A^{\ast }\)の要素\(a\)を任意に選んだとき、\(a\)のもとでの制約付き最大化問題には解が存在するということです。この場合、それぞれの\(a\in A^{\ast }\)に対して、\begin{equation*}
x^{\ast }\left( a\right) \in X^{\ast }\left( a\right)
\end{equation*}を満たす\(x^{\ast }\left( a\right) \in B\)を像として定める写像\begin{equation*}
x^{\ast }:A^{\ast }\rightarrow B
\end{equation*}が定義可能です。つまり、\(x^{\ast }\)はパラメータのそれぞれの値\(a\)に対して、それに対応する制約付き最大化問題の解を1つずつ選び取る写像です。このような写像を\(X^{\ast }\)からの選択子(selection)と呼びます。

パラメータのそれぞれの値\(a\in A\)に対して最適選択対応が定める解集合\(X^{\ast }\left( a\right) \)が複数の点を要素として持つ可能性を考慮すると、選択子\(x^{\ast }\)は一意的に定まるとは限りません。ただ、どのような選択子\(x^{\ast }\)を選んだ場合においても、\(x^{\ast }\)がそれぞれの\(a\)に対して定める\(x^{\ast }\left( a\right) \)が最適化問題の解であることを踏まえると、\begin{equation*}
\forall a\in A^{\ast }:f\left( x^{\ast }\left( a\right) ,a\right) =V\left(
a\right)
\end{equation*}という関係が常に成り立ちます。ただし、\(V:A\rightarrow \mathbb{R} ^{\ast }\)は価値関数です。

例(最適選択対応)
関数\(f:\mathbb{R} _{+}^{2}\times \mathbb{R} _{+}\rightarrow \mathbb{R} \)はそれぞれの\(\left( a_{1},a_{2},b\right) \in \mathbb{R} _{+}^{2}\times \mathbb{R} _{+}\)に対して、\begin{equation*}
f\left( a_{1},a_{2},b\right) =b^{2}
\end{equation*}を定め、対応\(g:\mathbb{R} _{+}^{2}\rightarrow \mathbb{R} _{+}\)はそれぞれの\(\left( a_{1},a_{2}\right) \in \mathbb{R} _{+}^{2}\)に対して、\begin{equation*}
g\left( a_{1},a_{2}\right) =\left\{ b\in \mathbb{R} _{+}\ |\ a_{1}b\leq a_{2}\right\}
\end{equation*}を定めるものとします。このとき、\(\left( a_{1},a_{2}\right) \in \mathbb{R} _{+}^{2}\)のもとでの制約付き最大化問題は、\begin{equation*}
\sup_{b\in \mathbb{R} }f\left( a_{1},a_{2},b\right) \quad \text{s.t.}\quad b\in g\left(
a_{1},a_{2}\right)
\end{equation*}すなわち、

$$\begin{array}{cl}
\sup\limits_{b} & b^{2} \\
s.t. & a_{1}b\leq a_{2} \\
& b\geq 0\end{array}$$
となります。この最大化問題の解は\(b=\frac{a_{2}}{a_{1}}\)であるため、最適選択対応\(X^{\ast }:\mathbb{R} _{+}^{2}\twoheadrightarrow \mathbb{R} _{+}\)はそれぞれの\(\left( a_{1},a_{2}\right) \in \mathbb{R} _{+}^{2}\)に対して、\begin{equation*}
X^{\ast }\left( a_{1},a_{2}\right) =\left\{ \frac{a_{2}}{a_{1}}\right\}
\end{equation*}という1点集合を定めます。したがって、選択\(x^{\ast }:\mathbb{R} _{+}^{2}\rightarrow \mathbb{R} _{+}\)は1つしか存在せず、それはそれぞれの\(\left( a_{1},a_{2}\right) \in \mathbb{R} _{+}^{2}\)に対して、\begin{equation*}
x^{\ast }\left( a_{1},a_{2}\right) =\frac{a_{2}}{a_{1}}
\end{equation*}を像として定めます。これと\(f\)の定義より、\begin{equation*}
f\left( x^{\ast }\left( a_{1},a_{2}\right) ,a_{1},a_{2}\right) =\left( \frac{a_{2}}{a_{1}}\right) ^{2}
\end{equation*}となります。一方、先に求めたように、価値関数\(V:\mathbb{R} _{+}^{2}\rightarrow \mathbb{R} ^{\ast }\)はそれぞれの\(\left( a_{1},a_{2}\right) \in \mathbb{R} _{+}^{2}\)に対して、\begin{equation*}
V\left( a_{1},a_{2}\right) =\left( \frac{a_{2}}{a_{1}}\right) ^{2}
\end{equation*}を定めるため、\begin{equation*}
f\left( x^{\ast }\left( a_{1},a_{2}\right) ,a_{1},a_{2}\right) =V\left(
a_{1},a_{2}\right)
\end{equation*}という関係がたしかに成立しています。

次回はベルジュの最大値定理について解説します。

質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定) 次へ進む
Share on facebook
Share on twitter
Share on email
次のページ >

プレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。プレミアム会員の方は以下からログインしてください。

会員登録 | パスワードを忘れましたか?

有料のプレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

本サイトは MathJax を実装しているため、コメント文中で LaTex コマンドを利用することで美しい数式を入力できます。その際、インライン数式は\(数式\)で、ディスプレイ数式は$$数式$$という形式でそれぞれ入力してください。 例えば、\(ax^{2}+bx+c=0\)と入力すると\(ax^{2}+bx+c=0\)と表示され、$$ax^{2}+bx+c=0$$と入力すると$$ax^{2}+bx+c=0$$と表示されます。MathJax(LaTex)の文法については次のサイト( https://easy-copy-mathjax.xxxx7.com )などを参照してください。 紙に手書きした数式や図をカメラやスマホで撮影した上で、コメント欄に張り付けることもできます。その場合、コメント入力欄にある「ファイルを選択」ボタンをクリックした上で画像をアップロードしてください。アップロード可能な画像フォーマットは jpg, gif, png の 3 種類、ファイルサイズの上限は 5 MB です。PDF ファイルの添付も可能です。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員だけが質問やコメントを投稿・閲覧できます。