点の凸結合
ユークリッド空間上の有限個の点\(\boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\in \mathbb{R} ^{n}\)が与えられたとき、スカラー\(\lambda _{1},\cdots ,\lambda _{k}\in \mathbb{R} \)を用いて、\begin{equation*}\lambda _{1}\boldsymbol{x}_{1}+\cdots +\lambda _{k}\boldsymbol{x}_{k}
\end{equation*}という形で表される\(\mathbb{R} ^{n}\)の点を\(\boldsymbol{x}_{1},\cdots ,\boldsymbol{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\)以下になることが保証されます。
\boldsymbol{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}\boldsymbol{x}+\lambda _{2}\boldsymbol{y} &=&\lambda _{1}\left(
x_{1},x_{2}\right) +\lambda _{2}\left( y_{1},y_{2}\right) \quad \because
\boldsymbol{x},\boldsymbol{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*}
\boldsymbol{x} &=&\left( x_{1},x_{2}\right) \in \mathbb{R} ^{2} \\
\boldsymbol{y} &=&\left( y_{1},y_{2}\right) \in \mathbb{R} ^{2} \\
\boldsymbol{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}\boldsymbol{x}+\lambda _{2}\boldsymbol{y}+\lambda _{3}\boldsymbol{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
\boldsymbol{x},\boldsymbol{y},\boldsymbol{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*}と表されます。
\end{equation}という形で表される\(\mathbb{R} ^{n}\)の点ですが、\begin{equation}\lambda _{2}=1-\lambda _{1} \quad \cdots (2)
\end{equation}であることを踏まえた上で\(\left( 1\right) \)を言い換えると、\begin{equation*}\lambda _{1}\boldsymbol{x}_{1}+\left( 1-\lambda _{1}\right) \boldsymbol{x}_{2}
\end{equation*}と言い換えることができます。ただし、\(\lambda _{2}\geq 0\)および\(\left( 2\right) \)より\(1-\lambda _{1}\geq 0\)すなわち\(\lambda _{1}\leq 1\)でなければなりません。つまり、2つの点の凸結合を表現するためにはスカラーが1つあれば十分です。以上の議論を踏まえた上で改めて整理すると、2つの点\(\boldsymbol{x}_{1},\boldsymbol{x}_{2}\in \mathbb{R} ^{n}\)の凸結合は、\(0\leq \lambda \leq 1\)を満たすスカラー\(\lambda \in \mathbb{R} \)を用いて、\begin{equation*}\lambda \boldsymbol{x}_{1}+\left( 1-\lambda \right) \boldsymbol{x}_{2}
\end{equation*}という形で表される\(\mathbb{R} ^{n}\)の点です。
凸集合
ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が与えられたとき、その2つの要素\(\boldsymbol{x}_{1},\boldsymbol{x}_{2}\in A\)を任意に選びます。このとき、これらの任意の凸結合が\(A\)の要素になることが保証されるならば、すなわち、\begin{equation*}\forall \boldsymbol{x}_{1}\in A,\ \forall \boldsymbol{x}_{2}\in A,\ \forall
\lambda \in \left[ 0,1\right] :\lambda \boldsymbol{x}_{1}+\left( 1-\lambda
\right) \boldsymbol{x}_{2}\in A
\end{equation*}が成り立つ場合には、\(A\)を凸集合（convex set）と呼びます。
\end{equation*}が明らかに成り立つからです。
\end{equation*}を構成すると、これは凸集合になります（演習問題）。
\(\mathbb{R} ^{n}\)の部分集合\(A\)が複数の要素を持つ場合には、\(A\)が凸集合であることを以下のように表現できます。
\left\{ \boldsymbol{x}_{1}\right\} ,\ \forall \lambda \in \left[ 0,1\right] :\lambda \boldsymbol{x}_{1}+\left( 1-\lambda \right) \boldsymbol{x}_{2}\in A
\end{equation*}が成り立つことと、\(A\)が凸集合であることは必要十分である。
つまり、\(\mathbb{R} ^{n}\)の部分集合\(A\)が複数の要素を持つ場合には、\(A\)の異なる2つの点を任意に選んだ上で、それらの任意の凸結合が\(A\)の要素であることを示せば、\(A\)が凸集合であることを示したことになるということです。
凸集合の幾何学的解釈
ユークリッド空間上の2つの点\(\boldsymbol{x}_{1},\boldsymbol{x}_{2}\in \mathbb{R} ^{n}\)の凸結合はスカラー\(\lambda \in \left[ 0,1\right] \)を用いて、\begin{equation*}\lambda \boldsymbol{x}_{1}+\left( 1-\lambda \right) \boldsymbol{x}_{2}
\end{equation*}という形で表される\(\mathbb{R} ^{n}\)の点です。\(\boldsymbol{x}_{1}=\boldsymbol{x}_{2}\)の場合、これらの凸結合は、\begin{equation*}\lambda \boldsymbol{x}_{1}+\left( 1-\lambda \right) \boldsymbol{x}_{1}=\boldsymbol{x}_{1}
\end{equation*}であり、これは点\(\boldsymbol{x}_{1}\ \left( =\boldsymbol{x}_{2}\right) \)と一致します。\(\boldsymbol{x}_{1}\not=\boldsymbol{x}_{2}\)の場合、スカラー\(\lambda \)を変数とみなして\(\left[ 0,1\right] \)内で自由に動かすと、\(\boldsymbol{x}_{1}\)と\(\boldsymbol{x}_{2}\)の凸結合はどのような軌跡を描くでしょうか。見通しを良くするため凸結合を変形すると、\begin{equation*}\boldsymbol{x}_{2}+\lambda \left( \boldsymbol{x}_{1}-\boldsymbol{x}_{2}\right)
\end{equation*}を得ますが、これは点\(\boldsymbol{x}_{2}\)を通りベクトル\(\boldsymbol{x}_{1}-\boldsymbol{x}_{2}\)と平行な直線のベクトル方程式です。
特に、\(\lambda =0\)の場合にこれは点\(\boldsymbol{x}_{2}\)と一致し、\(\lambda =1\)の場合には点\(\boldsymbol{x}_{1}\)と一致するため、\(\lambda \)を動かすと\(\boldsymbol{x}_{1}\)と\(\boldsymbol{x}_{2}\)の凸結合は点\(\boldsymbol{x}_{1},\boldsymbol{x}_{2}\)を両端とする線分の上を移動します（上図）。以上を踏まえた上で、2つの点\(\boldsymbol{x}_{1},\boldsymbol{x}_{2}\in \mathbb{R} ^{n}\)に対し、それらのすべての凸結合からなる集合を、\begin{equation*}\left[ \boldsymbol{x}_{1},\boldsymbol{x}_{2}\right] =\left\{ \lambda
\boldsymbol{x}_{1}+\left( 1-\lambda \right) \boldsymbol{x}_{2}\ |\ \lambda
\in \left[ 0,1\right] \right\}
\end{equation*}で表記し、これを点\(\boldsymbol{x}_{1},\boldsymbol{x}_{2}\)を端点とする閉じた線分（closed line segment）と呼びます。
\(\mathbb{R} ^{n}\)の部分集合\(A\)が凸集合であることとは、\(A\)の2つの点を任意に選んだときに、それらを端点とする閉じた線分がいずれも\(A\)の部分集合になることを意味します。
\boldsymbol{x}_{1},\boldsymbol{x}_{2}\right] \subset A
\end{equation*}が成り立つことは、\(A\)が凸集合であるための必要十分条件である。
\(\mathbb{R} ^{n}\)の部分集合\(A\)が複数の要素を持つ場合には、\(A\)が凸集合であることを以下のように表現できます。
\left\{ \boldsymbol{x}_{1}\right\} :\left[ \boldsymbol{x}_{1},\boldsymbol{x}_{2}\right] \subset A
\end{equation*}が成り立つことと、\(A\)が凸集合であることは必要十分である。
凸集合の特徴づけ
ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(A\)が凸集合である場合には、\(A\)の2つの点の任意の凸結合が\(A\)の要素になるだけでなく、\(A\)の任意個の点の任意の凸結合もまた\(A\)の要素になります。ただし、\(A\)の点の凸結合は\(A\)の有限個の点に対して定義される概念であることを踏まえると、これは、自然数\(k\)を任意に選んだ上で、さらに\(k\)個の点\(\boldsymbol{x}_{1},\cdots ,\boldsymbol{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}\boldsymbol{x}_{1}+\cdots +\lambda _{k}\boldsymbol{x}_{k}\in A
\end{equation*}が成り立つという主張になります。\(A\)が凸集合である場合には以上の条件が成り立つということです（演習問題）。
逆に、任意の自然数\(k\)について、\(k\)個の任意の\(A\)の点の凸結合が\(A\)の要素である場合、その特殊ケースとして、\(2\)個の任意の\(A\)の点の凸結合は\(A\)の要素になりますが、これは\(A\)が凸集合であることの定義に他なりません。したがって以下を得ます。
演習問題
1-\lambda _{1}-\lambda _{2}\right) \boldsymbol{x}_{3}
\end{equation*}という形で表すことができることを示してください。
\end{equation*}を構成すると、これは凸集合になることを示してください。
\end{equation*}が凸集合であることを示してください。
\end{equation*}と定義されます。これが凸集合であることを証明してください。
\right\}
\end{equation*}と定義されます。これが凸集合であることを示してください。
\varepsilon \right\}
\end{equation*}と定義されます。これが凸集合であることを示してください。
\end{equation*}が凸集合であることを証明してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】