多面錐（凸多面錐）の定義と具体例

多面錐（凸多面錐）

有限\(n\)個の変数\(x_{1},\cdots ,x_{n}\in \mathbb{R} \)に関する有限\(m\)本の1次不等式から構成される連立1次不等式\begin{equation*}\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\leq b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\leq b_{m}\end{array}\right.
\end{equation*}が与えられているものとします。ただし、\(a_{ij}\in \mathbb{R} \)は係数、\(b_{i}\in \mathbb{R} \)は定数項、\(x_{i}\in \mathbb{R} \)は変数です。係数行列\(A\)と変数ベクトル\(\boldsymbol{x}\)および定数ベクトル\(\boldsymbol{b}\)を、\begin{eqnarray*}A &=&\begin{pmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{m1} & \cdots & a_{mn}\end{pmatrix}\in M_{m,n}\left( \mathbb{R} \right) \\
\boldsymbol{x} &=&\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n}\end{pmatrix}\in \mathbb{R} ^{n} \\
\boldsymbol{b} &=&\begin{pmatrix}
b_{1} \\
\vdots \\
b_{m}\end{pmatrix}\in \mathbb{R} ^{m}
\end{eqnarray*}と定義すれば、先の連立1不等式を、\begin{equation*}
A\boldsymbol{x}\leq \boldsymbol{b}
\end{equation*}と表現できるため、その解集合は、\begin{equation*}
P=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq \boldsymbol{b}\right\}
\end{equation*}となります。これを多面体と呼びます。多面体は凸集合であるため、多面体を凸多面体と呼ぶ場合もあります。

一方、ユークリッド空間の部分集合\(C\subset \mathbb{R} ^{n}\)が錐であることとは、\(C\)が非負のスカラー倍について閉じていること、すなわち、\begin{equation*}\forall \boldsymbol{x}\in C,\ \forall \lambda \geq 0:\lambda \boldsymbol{x}\in C
\end{equation*}が成り立つことを意味します。錐は凸集合であるとは限りません。凸集合であるような錐を凸錐と呼びます。集合\(C\)が凸錐であることと、以下の条件\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*}が成り立つことは必要十分です。

多面体は錐であるとは限りません。まずは、錐ではない有界な多面体の例を挙げます。

続いて、錐ではない非有界な多面体の例を挙げます。

多面体は錐であるとは限らないことが明らかになりました。そこで、錐であるような多面体を多面錐（polyhedral cone）と呼びます。多面体は凸集合であるため、多面錐もまた凸集合です。そこで、多面錐を凸多面錐（convex polyhedral cone）と呼ぶ場合もあります。

改めて定義すると、ユークリッド空間の部分集合\(P\subset \mathbb{R} ^{n}\)が多面錐であることとは、\(C\)が多面体かつ錐であること、すなわち、\begin{eqnarray*}&&\left( a\right) \ \exists A\in M_{m,n}\left( \mathbb{R} \right) ,\ \exists \boldsymbol{b}\in \mathbb{R} ^{m}: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*}がともに成り立つこととして定義されます。ただし、多面体は凸集合であるため、\(P\)が錐であるという条件\(\left( b\right) \)を、\(P\)が凸錐であるという条件\begin{equation*}\left( b\right) \ \forall \boldsymbol{x}_{1}\in P,\ \forall \boldsymbol{x}_{2}\in P,\ \forall \lambda _{1}\geq 0,\ \forall \lambda _{2}\geq 0:\lambda
_{1}\boldsymbol{x}_{1}+\lambda _{2}\boldsymbol{x}_{2}\in P
\end{equation*}に置き換えることもできます。

多面錐の代替的な定義

集合\(P\subset \mathbb{R} ^{n}\)が多面錐であることを、\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*}とシンプルに表現することもできます。つまり、多面錐は定数ベクトルがゼロベクトルであるような連立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*}の解集合であるということです。

多面錐を以下のように表現することもできます。

多面錐は非有界

ゼロベクトルだけを要素として持つ1点集合は多面錐です。

有界は多面体は\(\left\{ \boldsymbol{0}\right\} \)に限定されます。

ユークリッド空間の部分集合\(P\subset \mathbb{R} ^{n}\)が多面錐であるとともに、\begin{equation*}P\not=\left\{ \boldsymbol{0}\right\}
\end{equation*}であるものとします。すると先の命題より\(P\)は非有界です。つまり、\(\left\{ \boldsymbol{0}\right\} \)以外の任意の多面錐は非有界であるということです。

多面錐の幾何学的解釈

多面錐の形式的定義は、\begin{equation*}
P=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq \boldsymbol{0}\right\}
\end{equation*}と必要十分ですが、これは有限個の1次不等式から構成される連立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*}の解集合と一致します。個々の不等式は空間\(\mathbb{R} ^{n}\)上に存在する原点を通過する平らな壁の片側の領域に相当するため、多面錐は原点を通過する有限個の平らな壁で仕切られた領域です。加えて、多面錐は非有界であるため、その領域は無限の広がりを持ちます。

演習問題