ワイルの定理
ユークリッド空間の部分集合\(C\subset \mathbb{R} ^{n}\)が凸錐であることは、\begin{equation*}\forall \boldsymbol{x}_{1}\in C,\ \forall \boldsymbol{x}_{2}\in C,\ \forall
\lambda _{1}\geq 0,\ \forall \lambda _{2}\geq 0:\lambda _{1}\boldsymbol{x}_{1}+\lambda _{2}\boldsymbol{x}_{2}\in C
\end{equation*}が成り立つことを意味します。集合\(A\subset \mathbb{R} ^{n}\)を部分集合として持つ凸錐の中でも最小のものを\(A\)の凸錐包と呼びますが、これは、\begin{equation*}\mathrm{Cone}\left( A\right) =\left\{ \sum_{i=1}^{k}\lambda _{i}\boldsymbol{x}_{i}\ |\ k\in \mathbb{N} \wedge \forall i\in \left\{ 1,\cdots ,k\right\} :\left( \lambda _{i}\geq
0\wedge \boldsymbol{x}_{i}\in A\right) \right\}
\end{equation*}と一致します。つまり、\(A\)の任意個の点の任意の錐結合をすべて集めれば、それは\(A\)の凸錐包と一致することが保証されます。特に、有限個のベクトル集合\begin{equation*}\left\{ \boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\right\} \subset \mathbb{R} ^{n}
\end{equation*}の凸錐包は、\begin{equation*}
\mathrm{Cone}\left( \left\{ \boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\right\} \right) =\left\{ \sum_{i=1}^{k}\lambda _{i}\boldsymbol{x}_{i}\
|\ \forall i\in \left\{ 1,\cdots ,k\right\} :\lambda _{i}\geq 0\right\}
\end{equation*}となりますが、これを有限個のベクトルから有限生成される凸錐と呼びます。これは\(\left\{ \boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\right\} \)を部分集合として持つ最小の凸錐です。
一方、ユークリッド空間の部分集合\(P\subset \mathbb{R} ^{n}\)が多面錐であることは、\(P\)が多面体かつ錐であることを意味します。つまり、以下の2つの条件\begin{eqnarray*}&&\left( a\right) \ \exists A\in M_{m,n}\left( \mathbb{R} \right) ,\ \exists \boldsymbol{b}\in M_{m,1}\left( \mathbb{R} \right) :P=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq \boldsymbol{b}\right\} \\
&&\left( b\right) \ \forall \boldsymbol{x}\in P,\ \forall \lambda \geq
0:\lambda \boldsymbol{x}\in P
\end{eqnarray*}が成り立つということです。ただし、\(\left(a\right) \)は\(P\)が多面体であることを意味し、\(\left( b\right) \)は\(P\)が錐であることを意味します。以上の2つの条件が成り立つことと、以下の条件\begin{equation*}\exists A\in M_{m,n}\left( \mathbb{R} \right) :P=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq \boldsymbol{0}\right\}
\end{equation*}が成り立つことは必要十分です。つまり、多面錐は変数\(x_{1},\cdots,x_{n}\in \mathbb{R} \)に関する同次連立1次不等式\begin{equation*}\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\leq 0 \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\leq 0\end{array}\right.
\end{equation*}の解集合であるということです。ちなみに、\(P\)が多面体であることを、\begin{equation*}\exists A\in M_{m,n}\left( \mathbb{R} \right) :P=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\geq \boldsymbol{0}\right\}
\end{equation*}と表現することもできます。
有限生成される凸錐は多面錐です。つまり、有限個のベクトル\(\boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\in \mathbb{R} ^{n}\)から生成された凸錐\begin{equation*}C=\mathrm{Cone}\left( \left\{ \boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\right\} \right)
\end{equation*}が与えられたとき、それに対して、\begin{equation*}
\exists A\in M_{m,n}\left( \mathbb{R} \right) :C=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq \boldsymbol{0}\right\}
\end{equation*}が成り立ちます。有限個のベクトルから生成された凸錐は、何らかの同次連立1次不等式の解集合であるということです。これをワイルの定理（Weyl’s theorem）と呼びます。証明ではフーリエ・モツキンの消去法を利用します。
\boldsymbol{a}_{2} &=&\left( 1,-1\right)
\end{eqnarray*}から生成される凸錐は、\begin{eqnarray*}
C &=&\mathrm{Cone}\left( \left\{ \boldsymbol{a}_{1},\boldsymbol{a}_{2}\right\} \right) \\
&=&\left\{ \lambda _{1}\left( 0,1\right) +\lambda _{2}\left( 1,-1\right) \in \mathbb{R} ^{2}\ |\ \lambda _{1},\lambda _{2}\geq 0\right\} \\
&=&\left\{ \left( \lambda _{2},\lambda _{1}-\lambda _{2}\right) \in \mathbb{R} ^{2}\ |\ \lambda _{1},\lambda _{2}\geq 0\right\}
\end{eqnarray*}です。他方で、以下の多面錐\begin{equation*}
P=\left\{ \left( x,y\right) \in \mathbb{R} ^{2}\ |\ x\geq 0\wedge x+y\geq 0\right\}
\end{equation*}に注目します。\(\left( x,y\right)\in C\)を任意に選んだとき、\(C\)の定義より、\begin{equation*}x=\lambda _{2}\wedge y=\lambda _{1}-\lambda _{2}\wedge \lambda _{1},\lambda
_{2}\geq 0
\end{equation*}が成り立ちますが、この場合には、\begin{eqnarray*}
x &=&\lambda _{2}\geq 0 \\
x+y &=&\lambda _{2}+\left( \lambda _{1}-\lambda _{2}\right) =\lambda
_{1}\geq 0
\end{eqnarray*}がともに成り立つため、\(P\)の定義より\(\left(x,y\right) \in P\)を得ます。以上より、\begin{equation*}C\subset P
\end{equation*}であることが示されました。逆に、\(\left( x,y\right)\in P\)を任意に選んだとき、\(P\)の定義より、\begin{equation*}x\geq 0\wedge x+y\geq 0
\end{equation*}が成り立ちますが、この場合、\begin{equation*}
\left( x,y\right) =\left( x+y\right) \left( 0,1\right) +x\left( 1,-1\right)
\end{equation*}と表せるとともに、その係数は、\begin{eqnarray*}
x+y &\geq &0 \\
x &\geq &0
\end{eqnarray*}を満たすため、\(C\)の定義より\(\left( x,y\right) \in C\)を得ます。以上より、\begin{equation*}P\subset C
\end{equation*}であることが示されました。以上より、\begin{equation*}
C=P
\end{equation*}であることが示されましたが、以上の結果は先の命題の主張と整合的です。
ミンコフスキーの定理
有限個のベクトルから生成された凸錐は多面錐であることが明らかになりましたが、逆の主張もまた成り立ちます。つまり、多面錐は有限個のベクトルから生成された凸錐であるということです。同次連立1次不等式の解集合は、有限個のベクトルから生成された凸錐であるということです。これをミンコフスキーの定理（Minkowski’s theorem）と呼びます。証明には先に示したワイルの定理と、双対錐に関するファルカスの補題を利用します。
以上の命題の証明から明らかになったように、多面錐\begin{equation*}
P=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\geq \boldsymbol{0}\right\}
\end{equation*}が与えられたとき、係数行列\(A\)の行ベクトルからなる有限集合\begin{equation*}\left\{ \mathrm{row}\left( A,1\right) ,\cdots ,\mathrm{row}\left( A,m\right)
\right\}
\end{equation*}から生成される凸錐は\(P\)の双対錐\(P^{\ast }\)とするとともに、\(P\)は\(P^{\ast }\)の双対錐と一致します。つまり、\begin{equation*}P^{\ast }=\mathrm{Cone}\left( \left\{ \mathrm{row}\left( A,1\right) ,\cdots ,\mathrm{row}\left( A,m\right) \right\} \right)
\end{equation*}であるとともに、\begin{equation*}
P=\left( P^{\ast }\right) ^{\ast }
\end{equation*}が成り立ちます。
\end{equation*}として与えられているものとします。係数行列は、\begin{equation*}
A=\begin{pmatrix}
1 & 0 \\
1 & 1\end{pmatrix}\end{equation*}ですが、その行ベクトルを、\begin{eqnarray*}
\boldsymbol{a}_{1} &=&\left( 1,0\right) \\
\boldsymbol{a}_{2} &=&\left( 1,1\right)
\end{eqnarray*}で表記します。この2つの行ベクトルによって生成される凸錐は、\begin{eqnarray*}
C &=&\mathrm{Cone}\left( \left\{ \boldsymbol{a}_{1},\boldsymbol{a}_{2}\right\} \right) \\
&=&\left\{ \lambda _{1}\left( 1,0\right) +\lambda _{2}\left( 1,1\right) \in \mathbb{R} ^{2}\ |\ \lambda _{1},\lambda _{2}\geq 0\right\} \\
&=&\left\{ \left( \lambda _{1}+\lambda _{2},\lambda _{2}\right) \in \mathbb{R} ^{2}\ |\ \lambda _{1},\lambda _{2}\geq 0\right\} \\
&=&\left\{ \left( x,y\right) \in \mathbb{R} ^{2}\ |\ x\geq y\geq 0\right\}
\end{eqnarray*}ですが、これは第1象限中の45度線より下側の領域です。すると先の命題より、\begin{equation*}
P^{\ast }=C
\end{equation*}であるとともに、\begin{equation*}
P=\left( P^{\ast }\right) ^{\ast }=C^{\ast }
\end{equation*}が成り立ちますが、そのことを以下で確認します。\(C\)の双対錐は、\begin{eqnarray*}C^{\ast } &=&\left\{ \left( x,y\right) \in \mathbb{R} ^{2}\ |\ \forall \left( c_{1},c_{2}\right) \in C:\left( x,y\right) \cdot
\left( c_{1},c_{2}\right) \geq 0\right\} \\
&=&\left\{ \left( x,y\right) \in \mathbb{R} ^{2}\ |\ \forall \lambda _{1},\lambda _{2}\geq 0:\left( x,y\right) \cdot
\left( \lambda _{1}+\lambda _{2},\lambda _{2}\right) \geq 0\right\} \\
&=&\left\{ \left( x,y\right) \in \mathbb{R} ^{2}\ |\ \forall \lambda _{1},\lambda _{2}\geq 0:x\left( \lambda
_{1}+\lambda _{2}\right) +y\lambda _{2}\geq 0\right\} \\
&=&\left\{ \left( x,y\right) \in \mathbb{R} ^{2}\ |\ \forall \lambda _{1},\lambda _{2}\geq 0:x\lambda _{1}+\left(
x+y\right) \lambda _{2}\geq 0\right\} \\
&=&\left\{ \left( x,y\right) \in \mathbb{R} ^{2}\ |\ x\geq 0\wedge x+y\geq 0\right\} \\
&=&P
\end{eqnarray*}となります。以上の結果は先の命題の主張と整合的です。
ミンコフスキー・ワイルの定理
以上の2つの命題より、多面錐と有限個のベクトルから生成される凸錐は概念として一致することが明らかになりました。同次連立1次不等式の解集合と、有限個のベクトルから生成された凸錐は実質的に等しい概念であるということです。これをミンコフスキー・ワイルの定理（Minkowski-Weyl’s theorem）と呼びます。
一般の多面体に関するするミンコフスキー・ワイルの定理
ミンコフスキー・ワイルの定理は多面錐\begin{equation*}
\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq \boldsymbol{0}\right\}
\end{equation*}と有限生成された凸錐\begin{equation*}
\mathrm{Cone}\left( \left\{ \boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\right\} \right)
\end{equation*}の関係について言及した命題です。では、多面錐に限定されない多面体\begin{equation*}
\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq \boldsymbol{b}\right\}
\end{equation*}に関しても、ミンコフスキー・ワイルの定理に相当する主張は成り立つのでしょうか。
\end{equation*}と表現できることは必要十分である。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】