教材一覧
教材一覧
教材検索

凸集合

凸集合の定義

目次

前のページ:
次のページ:

狭義凸集合の定義

Twitterで共有
メールで共有

点の凸結合

ユークリッド空間上の有限個の点\(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\)である場合には、線型結合のことを凸結合(convex combination)と呼びます。

何らかのスカラー\(\lambda_{i}\in \mathbb{R} \)について\(\lambda _{i}>1\)が成り立つ場合、条件\(\left( a\right) \)より、\begin{equation*}\sum_{i=1}^{k}\lambda _{i}>1
\end{equation*}となり、これは\(\left( b\right) \)と矛盾です。したがって、凸結合については、\begin{equation*}\forall i\in \left\{ 1,\cdots ,k\right\} :0\leq \lambda _{i}\leq 1
\end{equation*}が成り立つこと、つまり、すべてのスカラーが\(0\)以上\(1\)以下になることが保証されます。

例(点の凸結合)
\(2\)次元ユークリッド空間上の2つの点\begin{eqnarray*}x &=&\left( x_{1},x_{2}\right) \in \mathbb{R} ^{2} \\
y &=&\left( y_{1},y_{2}\right) \in \mathbb{R} ^{2}
\end{eqnarray*}の凸結合は、\(\lambda _{1}\geq 0\)かつ\(\lambda _{2}\geq 0\)かつ\(\lambda _{1}+\lambda _{2}=1\)を満たすスカラー\(\lambda_{1},\lambda _{2}\in \mathbb{R} \)を用いて、\begin{eqnarray*}\lambda _{1}x+\lambda _{2}y &=&\lambda _{1}\left( x_{1},x_{2}\right)
+\lambda _{2}\left( y_{1},y_{2}\right) \quad \because x,y\text{の定義} \\
&=&\left( \lambda _{1}x_{1},\lambda _{1}x_{2}\right) +\left( \lambda
_{2}y_{1},\lambda _{2}y_{2}\right) \quad \because \text{ベクトルのスカラー倍の定義} \\
&=&\left( \lambda _{1}x_{1}+\lambda _{2}y_{1},\lambda _{1}x_{2}+\lambda
_{2}y_{2}\right) \quad \because \text{ベクトルの和の定義}
\end{eqnarray*}と表されます。また、3つの点\begin{eqnarray*}
x &=&\left( x_{1},x_{2}\right) \in \mathbb{R} ^{2} \\
y &=&\left( y_{1},y_{2}\right) \in \mathbb{R} ^{2} \\
z &=&\left( z_{1},z_{2}\right) \in \mathbb{R} ^{2}
\end{eqnarray*}の凸結合は、\(\lambda _{1}\geq 0\)かつ\(\lambda _{2}\geq 0\)かつ\(\lambda _{3}\geq 0\)かつ\(\lambda _{1}+\lambda _{2}+\lambda _{3}=1\)を満たすスカラー\(\lambda _{1},\lambda _{2},\lambda_{3}\in \mathbb{R} \)を用いて、\begin{eqnarray*}\lambda _{1}x+\lambda _{2}y+\lambda _{3}z &=&\lambda _{1}\left(
x_{1},x_{2}\right) +\lambda _{2}\left( y_{1},y_{2}\right) +\lambda
_{3}\left( z_{1},z_{2}\right) \quad \because x,y,z\text{の定義} \\
&=&\left( \lambda _{1}x_{1},\lambda _{1}x_{2}\right) +\left( \lambda
_{2}y_{1},\lambda _{2}y_{2}\right) +\left( \lambda _{3}z_{1},\lambda
_{3}z_{2}\right) \quad \because \text{ベクトルのスカラー倍の定義} \\
&=&\left( \lambda _{1}x_{1}+\lambda _{2}y_{1}+\lambda _{3}z_{1},\lambda
_{1}x_{2}+\lambda _{2}y_{2}+\lambda _{3}z_{2}\right) \quad \because \text{ベクトルの和の定義}
\end{eqnarray*}と表されます。

例(点の凸結合)
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} \quad \cdots (1)
\end{equation}という形で表される\(\mathbb{R} ^{n}\)の点ですが、\begin{equation}\lambda _{2}=1-\lambda _{1} \quad \cdots (2)
\end{equation}であることを踏まえた上で\(\left( 1\right) \)を言い換えると、\begin{equation*}\lambda _{1}x_{1}+\left( 1-\lambda _{1}\right) x_{2}
\end{equation*}と言い換えることができます。ただし、\(\lambda _{2}\geq 0\)および\(\left( 2\right) \)より\(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} ^{n}\)の点です。

 

凸集合

ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が与えられたとき、その2つの要素\(x_{1},x_{2}\in A\)を任意に選びます。このとき、これらの任意の凸結合が\(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)と呼びます。

例(ユークリッド空間は凸集合)
ユークリッド空間\(\mathbb{R} ^{n}\)は\(\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 \)は偽であり、したがって上の命題は真です。以上より、空集合が凸集合であることが明らかになりました。
例(1点集合は凸集合)
ユークリッド空間の点\(x\in \mathbb{R} ^{n}\)を任意に選んだ上で、それだけを要素として持つ1点集合\(\left\{ x\right\} \)を構成します。明らかに\(\left\{ x\right\} \subset \mathbb{R} ^{n}\)です。\(\left\{ x\right\} \)が凸集合であることは以下の命題\begin{equation*}\forall x_{1}\in \left\{ x\right\} ,\ \forall x_{2}\in \left\{ x\right\} ,\
\forall \lambda \in \left[ 0,1\right] :\lambda x_{1}+\left( 1-\lambda
\right) x_{2}\in \left\{ x\right\}
\end{equation*}が真であることを意味しますが、\(\left\{ x\right\} \)が1点集合であることから、これは以下の命題\begin{equation*}\forall \lambda \in \left[ 0,1\right] :\lambda x+\left( 1-\lambda \right)
x\in \left\{ x\right\}
\end{equation*}すなわち、\begin{equation*}
\forall \lambda \in \left[ 0,1\right] :x\in \left\{ x\right\}
\end{equation*}と必要十分であり、これは明らかに真です。したがって\(\left\{ x\right\} \)は凸集合です。

\(\mathbb{R} ^{n}\)の部分集合\(A\)が複数の要素を持つ場合には、\(A\)が凸集合であることを以下のように表現できます。

命題(複数の要素を持つ凸集合)
ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が複数の要素を持つ場合、\begin{equation*}\forall x_{1}\in A,\ \forall x_{2}\in A\backslash \left\{ x_{1}\right\} ,\
\forall \lambda \in \left[ 0,1\right] :\lambda x_{1}+\left( 1-\lambda
\right) x_{2}\in A
\end{equation*}が成り立つことは、\(A\)が凸集合であるための必要十分条件である。
証明

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

つまり、\(\mathbb{R} ^{n}\)の部分集合\(A\)が複数の要素を持つ場合には、\(A\)の異なる2つの点を任意に選んだ上で、それらの任意の凸結合が\(A\)の要素であることを示せば、\(A\)が凸集合であることを示したことになるということです。

 

凸集合の幾何学的解釈

ユークリッド空間上の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}\)の場合、これらの凸結合は、\begin{equation*}\lambda x_{1}+\left( 1-\lambda \right) x_{1}=x_{1}
\end{equation*}であり、これは点\(x_{1}\ \left( =x_{2}\right) \)と一致します。\(x_{1}\not=x_{2}\)の場合、スカラー\(\lambda \)を変数とみなして\(\left[ 0,1\right] \)内で自由に動かすと、\(x_{1}\)と\(x_{2}\)の凸結合はどのような軌跡を描くでしょうか。見通しを良くするため凸結合を変形すると、\begin{equation*}x_{2}+\lambda \left( x_{1}-x_{2}\right)
\end{equation*}を得ますが、これは点\(x_{2}\)を通りベクトル\(x_{1}-x_{2}\)と平行な直線のベクトル方程式です。

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

特に、\(\lambda =0\)の場合にこれは点\(x_{2}\)と一致し、\(\lambda =1\)の場合には点\(x_{1}\)と一致するため、\(\lambda \)を動かすと\(x_{1}\)と\(x_{2}\)の凸結合は点\(x_{1},x_{2}\)を両端とする線分の上を移動します(上図)。以上を踏まえた上で、2つの点\(x_{1},x_{2}\in \mathbb{R} ^{n}\)に対し、それらのすべての凸結合からなる集合を、\begin{equation*}\left[ x_{1},x_{2}\right] =\left\{ \lambda x_{1}+\left( 1-\lambda \right)
x_{2}\ |\ \lambda \in \left[ 0,1\right] \right\}
\end{equation*}で表記し、これを点\(x_{1},x_{2}\)を端点とする閉じた線分(closed line segment)と呼びます。

\(\mathbb{R} ^{n}\)の部分集合\(A\)が凸集合であることとは、\(A\)の2つの点を任意に選んだときに、それらを端点とする閉じた線分がいずれも\(A\)の部分集合になることを意味します。

命題(閉じた線分を用いた凸集合の定義)
ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)について、\begin{equation*}\forall x_{1}\in A,\ \forall x_{2}\in A:\left[ x_{1},x_{2}\right] \subset A
\end{equation*}が成り立つことは、\(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}\)の部分集合\(A\)が複数の要素を持つ場合には、\(A\)が凸集合であることを以下のように表現できます。

命題(複数の要素を持つ凸集合)
ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が複数の要素を持つ場合、\begin{equation*}\forall x_{1}\in A,\ \forall x_{2}\in A\backslash \left\{ x_{1}\right\} :
\left[ x_{1},x_{2}\right] \subset A
\end{equation*}が成り立つことは、\(A\)が凸集合であるための必要十分条件である。
証明

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

 

凸集合の特徴づけ

ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(A\)が凸集合である場合には、\(A\)の2つの点の任意の凸結合が\(A\)の要素になるだけでなく、\(A\)の任意個の点の任意の凸結合もまた\(A\)の要素になります。ただし、\(A\)の点の凸結合は\(A\)の有限個の点に対して定義される概念であることを踏まえると、これは、自然数\(k\)を任意に選んだ上で、さらに\(k\)個の点\(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\)が凸集合である場合には以上の条件が成り立つということです(演習問題)。

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

命題(凸集合の特徴づけ)
ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が与えられたとき、自然数\(k\in \mathbb{N} \)を任意に選んだ上で、さらに\(k\)個の点\(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 1\)を満たすスカラー\(\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} \)であるとともに、\begin{equation*}\mathbb{R} _{+}^{n}=\left\{ \left( x_{1},\cdots ,x_{n}\right) \in \mathbb{R} ^{n}\ |\ \forall i\in \left\{ 1,\cdots ,n\right\} :x_{i}\geq 0\right\}\end{equation*}です。

解答を見る

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

問題(有界開区間は凸集合)
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*}と定義されます。これが凸集合であることを示してください。

解答を見る

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

問題(点の閉近傍は凸集合)
ユークリッド空間の点\(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*}と定義されます。これが凸集合であることを示してください。

解答を見る

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

問題(予算集合は凸集合)
ユークリッド空間の部分集合\(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*}と定義される集合が凸集合であることを証明してください。

解答を見る

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