WIIS

対応

制約付き最大化問題

目次

Twitter
Mailで保存

制約付き最大化問題

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

対応\(g:A\twoheadrightarrow X\)のグラフは、\begin{equation*}
G\left( g\right) =\left\{ \left( a,x\right) \in A\times X\ |\ x\in g\left(
a\right) \right\}
\end{equation*}と定義されるため、順序対\(\left( a,x\right) \in A\times X\)を任意に選んだとき、\begin{equation*}
\left( a,x\right) \in G\left( g\right) \Leftrightarrow x\in g\left( a\right)
\end{equation*}という関係が成り立ちます。この事実を踏まえると、先の制約付き最大化問題を、与えられた\(a\in A\)のもとでの、\begin{equation*}
\sup_{x\in X}f\left( a,x\right) \quad \text{s.t.}\quad \left( a,x\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\)のグラフ\(G\left( g\right) \)上に定義されていれば、\(a\in A\)を任意に選んだとき、\(f\)は\(g\left( a\right) \)上の任意の点において定義されていることが保証されるため、先の制約付き最大化問題を考える上で問題は発生しません。

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

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

例(制約付き最大化問題)
関数\(f:\mathbb{R}_{+}^{2}\times \mathbb{R}_{+}\rightarrow \mathbb{R}\)はそれぞれの\(\left( a_{1},a_{2},x\right) \in \mathbb{R}_{+}^{2}\times \mathbb{R}_{+}\)に対して、\begin{equation*}
f\left( a_{1},a_{2},x\right) =x^{2}
\end{equation*}を定めるものとします。つまり、\(f\)の形状はパラメータ\(a_{1},a_{2}\)の値に依存せず、これは\(x\)のみを変数として持つ関数です。さらに対応\(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\{ x\in \mathbb{R}_{+}\ |\ a_{1}x\leq a_{2}\right\}
\end{equation*}を定めるものとします。このとき、\(\left( a_{1},a_{2}\right) \in \mathbb{R}_{+}^{2}\)のもとでの制約付き最大化問題は、\begin{equation*}
\sup_{x\in \mathbb{R}_{+}}f\left( a_{1},a_{2},x\right) \quad \text{s.t.}\quad x\in g\left(
a_{1},a_{2}\right)
\end{equation*}すなわち、
$$\begin{array}{cl}
\sup\limits_{x} & x^{2} \\
s.t. & a_{1}x\leq a_{2} \\
& x\geq 0\end{array}$$
となります。具体的には、\(\left( a_{1},a_{2}\right) =\left( 1,2\right) \)に対応する最大化問題は、
$$\begin{array}{cl}
\sup\limits_{x} & x^{2} \\
s.t. & x\leq 2 \\
& x\geq 0\end{array}$$
であり、\(\left( a_{1},a_{2}\right) =\left( 3,8\right) \)に対応する最大化問題は、
$$\begin{array}{cl}
\sup\limits_{x} & x^{2} \\
s.t. & 3x\leq 8 \\
& x\geq 0\end{array}$$となります。
例(制約付き最大化問題)
関数\(f:\mathbb{R}_{+}^{3}\times \mathbb{R}_{+}^{2}\rightarrow \mathbb{R}\)はそれぞれの\(\left( a_{1},a_{2},a_{3},x_{1},x_{2}\right) \in \mathbb{R}_{+}^{3}\times \mathbb{R}_{+}^{2}\)に対して、\begin{equation*}
f\left( a_{1},a_{2},a_{3},x_{1},x_{2}\right) =x_{1}^{\frac{1}{2}}y_{2}^{\frac{1}{2}}
\end{equation*}を定めるものとします。つまり、\(f\)の形状はパラ―メータ\(a_{1},a_{2},a_{3}\)の値に依存せず、これは\(x_{1}\)と\(x_{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( x_{1},x_{2}\right) \in \mathbb{R}_{+}^{2}\ |\ a_{1}x_{1}+a_{2}x_{2}\leq a_{3}\right\}
\end{equation*}を定めるものとします。このとき、\(\left( a_{1},a_{2},a_{3}\right) \in \mathbb{R}_{+}^{3}\)のもとでの制約付き最大化問題は、\begin{equation*}
\sup_{\left( x_{1},x_{2}\right) \in \mathbb{R}_{+}^{2}}f\left( a_{1},a_{2},a_{3},x_{1},x_{2}\right) \quad \text{s.t.}\quad
\left( x_{1},x_{2}\right) \in g\left( a_{1},a_{2},a_{3}\right)
\end{equation*}すなわち、
$$\begin{array}{cl}
\sup\limits_{\left( x_{1},x_{2}\right) } & x_{1}^{\frac{1}{2}}x_{2}^{\frac{1}{2}} \\
s.t. & a_{1}x_{1}+a_{2}x_{2}\leq a_{3} \\
& x_{1}\geq 0 \\
& x_{2}\geq 0\end{array}$$
となります。具体的には、\(\left( a_{1},a_{2},a_{3}\right) =\left( 1,2,8\right) \)に対応する最大化問題は、
$$\begin{array}{cl}
\sup\limits_{\left( x_{1},x_{2}\right) } & x_{1}^{\frac{1}{2}}x_{2}^{\frac{1}{2}} \\
s.t. & x_{1}+2x_{2}\leq 8 \\
& x_{1}\geq 0 \\
& x_{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( x_{1},x_{2}\right) } & x_{1}^{\frac{1}{2}}x_{2}^{\frac{1}{2}} \\
s.t. & \frac{x_{1}}{2}+3x_{2}\leq 10 \\
& x_{1}\geq 0 \\
& x_{2}\geq 0\end{array}$$
となります。

 

価値関数

実数値関数\(f:A\times X\rightarrow \mathbb{R}\)と対応\(g:A\twoheadrightarrow X\)がそれぞれ与えられたとき、パラメータのそれぞれの値\(a\in A\)に対して制約付き最大化問題\begin{equation*}
\sup_{x\in X}f\left( a,x\right) \quad \text{s.t.}\quad x\in g\left( a\right)
\end{equation*}を構成できますが、\(a\)の値に応じてこの最大化問題も変化し得るため、最大化問題の解や、さらにはその解のもとで実現する目的関数\(f\left( a,x\right) \)の最大値もまた\(a\)の値に応じて変化します。そこで、目的関数\(f\left( a,x\right) \)の最大値そのものを\(a\)を変数として持つ関数とみなした上で、そのような関数を価値関数(value function)や包絡面関数(envelope plane function)などと呼びます。より正確には、価値関数とは、パラメータのそれぞれの値\(a\in A\)に対して、\begin{equation*}
V\left( a\right) =\sup \left\{ f\left( a,x\right) \in \mathbb{R}\ |\ x\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 X\)は定義域の値\(a\in A\)に対して空集合を像として定めることがありますが、その場合、\(a\)に対応する最大化問題の制約集合\(g\left( a\right) \)が空集合になってしまいます。つまり、そのような\(a\)に対応する制約付き最大化問題は、\begin{equation*}
\sup_{x\in X}f\left( a,x\right) \quad \text{s.t.}\quad x\in \phi
\end{equation*}となり、価値関数\(V\)がそのような\(a\)に対して定める値は、\begin{equation*}
V\left( a\right) =\sup \left\{ f\left( a,x\right) \in \mathbb{R}\ |\ x\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},x\right) \in \mathbb{R}_{+}^{2}\times \mathbb{R}_{+}\)に対して、\begin{equation*}
f\left( a_{1},a_{2},x\right) =x^{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\{ x\in \mathbb{R}_{+}\ |\ a_{1}x\leq a_{2}\right\}
\end{equation*}を定めるものとします。このとき、\(\left( a_{1},a_{2}\right) \in \mathbb{R}_{+}^{2}\)のもとでの制約付き最大化問題は、\begin{equation*}
\sup_{x\in \mathbb{R}}f\left( a_{1},a_{2},x\right) \quad \text{s.t.}\quad x\in g\left(
a_{1},a_{2}\right)
\end{equation*}すなわち、
$$\begin{array}{cl}
\sup\limits_{x} & x^{2} \\
s.t. & a_{1}x\leq a_{2} \\
& x\geq 0\end{array}$$
となります。この最大化問題の解は\(x=\frac{a_{2}}{a_{1}}\)であり、この解において目的関数\(x^{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_{x} & x^{2} \\
s.t. & x\leq 2 \\
& x\geq 0\end{array}$$
ですが、この最大化問題の解は\(x=2\)であり、この解において目的関数\(x^{2}\)がとる値は\(4\)です。実際、先に導出した価値関数\(V\)のもとでは、\begin{equation*}
V\left( 1,2\right) =\left( \frac{2}{1}\right) ^{2}=4
\end{equation*}となります。

 

最適選択対応

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

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

最適選択対応\(X^{\ast }:A\twoheadrightarrow X\)が与えられたとき、\(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 X\)を像として定める写像\begin{equation*}
x^{\ast }:A^{\ast }\rightarrow X
\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},x\right) \in \mathbb{R}_{+}^{2}\times \mathbb{R}_{+}\)に対して、\begin{equation*}
f\left( a_{1},a_{2},b\right) =x^{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\{ x\in \mathbb{R}_{+}\ |\ a_{1}x\leq a_{2}\right\}
\end{equation*}を定めるものとします。このとき、\(\left( a_{1},a_{2}\right) \in \mathbb{R}_{+}^{2}\)のもとでの制約付き最大化問題は、\begin{equation*}
\sup_{x\in \mathbb{R}}f\left( a_{1},a_{2},x\right) \quad \text{s.t.}\quad x\in g\left(
a_{1},a_{2}\right)
\end{equation*}すなわち、
$$\begin{array}{cl}
\sup\limits_{x} & x^{2} \\
s.t. & a_{1}x\leq a_{2} \\
& x\geq 0\end{array}$$
となります。この最大化問題の解は\(x=\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*}という関係がたしかに成立しています。

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

質問・コメント(プレミアム会員限定) 次へ進む

関連知識

Twitter
Mailで保存

質問とコメント

プレミアム会員専用コンテンツです

会員登録

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

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

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

プレミアム会員専用コンテンツです
ログイン】【会員登録