教材一覧
CONVEX SET

凸集合

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

凸結合

ユークリッド空間上の有限個の点\(x_{1},\cdots ,x_{k}\in \mathbb{R} ^{n}\)が与えられたとき、スカラー\(\lambda _{1},\cdots ,\lambda _{k}\in \mathbb{R} \)を用いて、\begin{equation*}\lambda _{1}x_{1}+\cdots +\lambda _{k}x_{k}
\end{equation*}という形で表される\(\mathbb{R} ^{n}\)の点を\(x_{1},\cdots ,x_{k}\)の線型結合(linear combination)と呼びます。特に、スカラー\(\lambda _{1},\cdots ,\lambda _{k}\in \mathbb{R} \)が、\begin{eqnarray*}&&\left( a\right) \ \forall i\in \left\{ 1,\cdots ,k\right\} :\lambda
_{i}\geq 0 \\
&&\left( b\right) \ \sum_{i=1}^{k}\lambda _{i}=1
\end{eqnarray*}を満たす場合には、すなわち、すべてのスカラーが非負であるとともにすべてのスカラーの和が\(1\)である場合には、\(x_{1},\cdots ,x_{k}\)の線型結合のことを凸結合(convex combination)と呼びます。

例(凸結合)
2つの点\(x_{1},x_{2}\in \mathbb{R} ^{n}\)の凸結合は、\(\lambda _{1}\geq 0\)かつ\(\lambda _{2}\geq 0\)かつ\(\lambda _{1}+\lambda_{2}=1\)を満たすスカラー\(\lambda _{1},\lambda _{2}\in \mathbb{R} \)を用いて、\begin{equation*}\lambda _{1}x_{1}+\lambda _{2}x_{2}
\end{equation*}という形で表される\(\mathbb{R} ^{n}\)の点ですが、\(\lambda _{2}=1-\lambda_{1}\)であることを踏まえると、上の凸結合を、\begin{equation*}\lambda _{1}x_{1}+\left( 1-\lambda _{1}\right) x_{2}
\end{equation*}と言い換えることができます。ただし、\(\lambda _{2}\geq 0\)より\(1-\lambda _{1}\geq 0\)すなわち\(\lambda _{1}\leq 1\)でなければなりません。つまり、2つの点の凸結合を表現するにはスカラーが1つあれば十分であるということです。以上の議論を踏まえた上で改めて整理すると、2つの点\(x_{1},x_{2}\in \mathbb{R} ^{n}\)の凸結合は、\(0\leq \lambda \leq 1\)を満たすスカラー\(\lambda \in \mathbb{R} \)を用いて、\begin{equation*}\lambda x_{1}+\left( 1-\lambda \right) x_{2}
\end{equation*}という形で表される\(\mathbb{R} ^{2}\)の点です。

 

線分

繰り返しになりますが、ユークリッド空間上の2つの点\(x_{1},x_{2}\in \mathbb{R} ^{n}\)が与えられたとき、それらの凸結合はスカラー\(\lambda \in \left[ 0,1\right] \)を用いて、\begin{equation*}\lambda x_{1}+\left( 1-\lambda \right) x_{2}
\end{equation*}という形で表される\(\mathbb{R} ^{n}\)の点です。特に、\(x_{1}\)と\(x_{2}\)が異なる点である場合、\(\lambda \)を変数とみなして\(\left[ 0,1\right] \)内で自由に動かすと、上の凸結合に相当する点はどのような軌跡を描くでしょうか。

図:2つの点を両端とする線分
図:2つの点を両端とする線分

見通しを良くするために上の式を変形すると、\begin{equation*}
x_{2}+\lambda \left( x_{1}-x_{2}\right)
\end{equation*}を得ますが、これは点\(x_{2}\)を通りベクトル\(x_{1}-x_{2}\)に平行な直線のベクトル方程式です。特に、\(\lambda =0\)の場合には先の凸結合に相当する点は\(x_{2}\)と一致し、\(\lambda =1\)の場合には\(x_{1}\)と一致するため、\(\lambda \)を動かすと先の凸結合に相当する点は\(x_{1}\)と\(x_{2}\)を両端とする線分の上を移動します(上図)。そのような事情もあり、異なる2つの点\(x_{1},x_{2}\in \mathbb{R} ^{n}\)に対し、それらのすべての凸結合からなる集合\begin{equation*}\left\{ \lambda x_{1}+\left( 1-\lambda \right) x_{2}\ |\ \lambda \in \left[
0,1\right] \right\}
\end{equation*}を\(x_{1}\)と\(x_{2}\)を端点とする線分(line segment)と呼びます。

 

凸集合

ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が与えられたとき、その2つの要素\(x_{1},x_{2}\in A\)を任意に選びます。このとき、\(x_{1}\)と\(x_{2}\)の任意の凸結合が\(A\)の点になるならば、すなわち、\begin{equation*}\forall x_{1}\in A,\ \forall x_{2}\in A,\ \forall \lambda \in \left[ 0,1\right] :\lambda x_{1}+\left( 1-\lambda \right) x_{2}\in A
\end{equation*}が成り立つ場合には\(A\)を凸集合(convex set)と呼びます。

ちなみに、\(x_{1}=x_{2}\)を満たす点\(x_{1},x_{2}\in A\)に関しては、任意の\(\lambda \in \left[ 0,1\right] \)について、\begin{eqnarray*}\lambda x_{1}+\left( 1-\lambda \right) x_{2} &=&\lambda x_{1}+\left(
1-\lambda \right) x_{1}\quad \because x_{1}=x_{2} \\
&=&x_{1} \\
&\in &A\quad \because x_{1}\in A
\end{eqnarray*}となるため上の条件は明らかに成り立ちます。したがって、\(A\)が凸集合であることの定義を「\(A\)の異なる2つの点を任意に選んだとき、それらの任意の凸結合が\(A\)の要素になる」と言い換えることができます。線分の定義を踏まえると、これをさらに「\(A\)の異なる2つの点を任意に選んだとき、それらを端点とする線分が\(A\)の部分集合になる」と言い換えることもできます。

例(凸集合)
以下の図で表される\(\mathbb{R} ^{2}\)の部分集合\(A\)は凸集合です。実際、\(A\)上の異なる2つの点を任意に選んだとき、それらを結んで得られる線分全体が\(A\)に含まれるからです。
図:凸集合
図:凸集合

以下の図で表される\(\mathbb{R} ^{2}\)の部分集合\(B\)は凸集合ではありません。実際、下図のような\(B\)上の2つの点\(x_{1},x_{2}\)に関しては、それらを結んで得られる線分上の点の中に\(B\)の点でないものが存在するからです。

図:凸集合ではない
図:凸集合ではない

以下の図で表される\(\mathbb{R} ^{2}\)の部分集合\(C\)は凸集合ではありません。実際、下図のような\(C\)上の2つの点\(x_{1},x_{2}\)に関しては、それらを結んで得られる線分上の点の中に\(C\)の点でないものが存在するからです。

図:凸集合ではない
図:凸集合ではない
例(ユークリッド空間は凸集合)
ユークリッド空間\(\mathbb{R} ^{n}\)は自身の部分集合ですが、これは明らかに凸集合です。実際、点\(x_{1},x_{2}\in \mathbb{R} ^{n}\)とスカラー\(\lambda \in \left[ 0,1\right] \)をそれぞれ任意に選んだとき、\begin{equation*}\lambda x_{1}+\left( 1-\lambda \right) x_{2}\in \mathbb{R} ^{n}
\end{equation*}が成り立つからです。
例(空集合は凸集合)
空集合\(\phi \)はユークリッド空間\(\mathbb{R} ^{n}\)の部分集合です。\(\phi \)が凸集合であるならば、\begin{equation*}\forall x_{1}\in \phi ,\ \forall x_{2}\in \phi ,\ \forall \lambda \in \left[
0,1\right] :\lambda x_{1}+\left( 1-\lambda \right) x_{2}\in \phi
\end{equation*}が成り立つはずですが、空集合の定義より\(x_{1}\in \phi \)は偽であるため、上の命題は真です。したがって\(\phi \)は凸集合です。
例(1点集合は凸集合)
ユークリッド空間の点\(x\in \mathbb{R} ^{n}\)を任意に選んだ上で、それだけを要素として持つ\(\mathbb{R} ^{n}\)の部分集合\(\left\{ x\right\} \)について考えます。このとき、任意の\(\lambda \in \left[0,1\right] \)について、\begin{equation*}\lambda x+\left( 1-\lambda \right) x=x\in \left\{ x\right\}
\end{equation*}が成り立つため\(\left\{ x\right\} \)は凸集合です。

 

凸集合の代替的な定義

ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(A\)が凸集合である場合には、\(A\)の任意の2つの点の任意の凸結合が\(A\)の要素になるだけでなく、実は、\(A\)の任意個の任意の点の任意の凸結合もまた\(A\)の要素になります。ただし、\(A\)の点の凸結合は\(A\)の有限個の点に対して定義される概念であることを踏まえると、これは、\(A\)の有限個の任意の点の任意の凸結合が\(A\)の要素になるという主張になります。つまり、\(A\)が凸集合である場合には、任意(有限)個の点\(x_{1},\cdots ,x_{k}\in A\)を任意に選んだとき、\begin{eqnarray*}&&\left( a\right) \ \forall i\in \left\{ 1,\cdots ,k\right\} :\lambda
_{i}\geq 0 \\
&&\left( b\right) \ \sum_{i=1}^{k}\lambda _{i}=1
\end{eqnarray*}を満たす任意のスカラー\(\lambda _{1},\cdots ,\lambda _{k}\in \mathbb{R} \)に対して、\begin{equation*}\lambda _{1}x_{1}+\cdots +\lambda _{k}x_{k}\in A
\end{equation*}が成り立つということです。これは凸結合を構成する\(A\)の点の個数に関する数学的帰納法によって示すことができます(演習問題にします)。

逆に、\(A\)の任意(有限)個の任意の点の任意の凸結合が\(A\)の要素である場合、その特殊ケースとして、\(A\)の任意の2つの点の任意の凸結合が\(A\)の要素になりますが、これは\(A\)が凸集合であることの定義に他なりません。したがって凸集合の定義を以下のように言い換えることができます。

命題(凸集合の特徴づけ)
ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が与えられたとき、その任意(有限)個の点\(x_{1},\cdots ,x_{k}\in A\)を任意に選ぶ。これらの点の任意の凸結合が\(A\)の要素であることは、\(A\)が凸集合であるための必要十分条件である。
証明

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

 

演習問題

問題(凸結合)
3つの点\(x_{1},x_{2},x_{3}\in \mathbb{R} ^{n}\)の凸結合は、\(0\leq \lambda _{1}\leq1\)かつ\(0\leq \lambda _{2}\leq \)を満たすスカラー\(\lambda _{1},\lambda _{2}\in \mathbb{R} \)を用いて、\begin{equation*}\lambda _{1}x_{1}+\lambda _{2}x_{2}+\left( 1-\lambda _{1}-\lambda
_{2}\right) x_{3}
\end{equation*}という形で表すことができることを示してください。
解答を見る

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

問題(非負実数空間の直積は凸集合)
\(\mathbb{R} _{+}^{n}\)が凸集合であることを証明してください。ただし\(n\in \mathbb{N} \)です。
解答を見る

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

問題(有界開区間は凸集合)
1次元ユークリッド空間\(\mathbb{R} \)上の有界な開区間を、\(a<b\)を満たす実数\(a,b\in \mathbb{R} \)を用いて、\begin{equation*}\left( a,b\right) =\left\{ x\in \mathbb{R} \ |\ a<x<b\right\}
\end{equation*}と定義します。これが凸集合であることを証明してください。
解答を見る

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

問題(点の近傍は凸集合)
ユークリッド空間の点\(a\in \mathbb{R} ^{n}\)を中心とし、半径を\(\varepsilon >0\)とする近傍は、\begin{equation*}N_{\varepsilon }\left( a\right) =\left\{ x\in \mathbb{R} ^{n}\ |\ \left\Vert x-a\right\Vert <\varepsilon \right\}
\end{equation*}と定義されます。\(N_{\varepsilon }\left( a\right) \)が凸集合であることを示してください。
解答を見る

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

問題(点の閉近傍は凸集合)
ユークリッド空間の点\(a\in \mathbb{R} ^{n}\)を中心とし、半径を\(\varepsilon >0\)とする閉近傍は、\begin{equation*}C_{\varepsilon }\left( a\right) =\left\{ x\in \mathbb{R} ^{n}\ |\ \left\Vert x-a\right\Vert \leq \varepsilon \right\}
\end{equation*}と定義されます。\(C_{\varepsilon }\left( a\right) \)が凸集合であることを示してください。
解答を見る

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

問題(予算集合は凸集合)
ユークリッド空間の部分集合\(X\subset \mathbb{R} ^{n}\)が凸集合であるものとします。点\(p\in \mathbb{R} _{++}^{n}\)と正の実数\(w>0\)がそれぞれ任意に与えられたとき、\begin{equation*}B\left( p,w\right) =\left\{ x\in X\ |\ p\cdot x\leq w\right\}
\end{equation*}と定義される集合が凸集合であることを証明してください。
解答を見る

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

次回は狭義凸集合について学びます。

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

狭義凸集合

狭義凸集合

ユークリッド空間の部分集合に属する異なる2つの点を任意に選んだとき、それらの任意の狭義凸結合がその集合の内点であるならば、その集合を狭義凸集合と呼びます。

予算集合

予算集合の凸性

消費者理論では予算集合が凸集合であることを仮定することがあります。この場合、非分割財の消費などは分析対象から除外されることになります。

凸関数・凹関数

凸関数・凹関数

定義域が凸集合であるとともに、そのグラフが直線もしくは谷型の曲線になるような関数を凸関数と呼びます。また、定義域が凸集合であるとともに、そのグラフが直線もしくは山型の曲線になるような関数を凹関数と呼びます。凸関数や凹関数の概念はスカラー場(多変数関数)にも容易に拡張されます。

狭義凸関数・狭義凹関数

狭義凸関数・狭義凹関数

定義域が凸集合であるとともに、そのグラフが谷型の曲線になるような関数を狭義凸関数と呼び、グラフが山型の曲線になるような関数を狭義凹関数と呼びます。狭義凸関数や狭義凹関数の概念はスカラー場(多変数関数)にも容易に拡張されます。

選好の凸性

選好の凸性

消費ベクトル x 以上に望ましい消費ベクトル y,z を任意に選んだとき、それらを任意の割合で混ぜることで得られる消費ベクトルもまた x 以上に望ましいことが保証されるのであれば、選好は凸性を満たすと言います。凸性を満たす選好は準凹な効用関数によって特徴づけられます。

DISCUSSION

質問とコメント

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