凸多面体

【とつためんたい (convex polyhedron, convex polytope)】

概要

有限個の閉半空間の共通部分を凸多面体と呼ぶ. すなわち, $n\,$次元実線形空間${\mathbf {R} }^{n}\,$内の凸多面体$P\,$は, 適当な$m\times n\,$実行列$A\,$と$m\,$次元ベクトル$b\,$を用いて

$P=\{x\in {\mathbf {R} }^{n}\mid Ax\leq b\}\,$

と表現できる. 特に有界な凸多面体は, convex polytope と英語では区別して呼ばれ, 有限個の点からなる集合の凸包であり, 逆も成り立つ.

詳説

　$n\,$次元実ベクトル$a=(a_{1},\cdots ,a_{n})^{\rm {T}}\in {\mathbf {R} }^{n}\,$と実数 $a_{0}{\in }{\mathbf {R} }\,$ により定まる1次不等式 (線形不等式) $(a_{1}x_{1}+\cdots +a_{n}x_{n}\leq a_{0})\,$を満たす点$x=(x_{1},\cdots ,x_{n})^{\rm {T}}\,$全体からなる集合を閉半空間(closed halfspace)とよぶ. 有限個の閉半空間の共通部分を凸多面体 (convex polyhedron) とよぶ. すなわち, ${\mathbf {R} }^{n}\,$内の凸多面体は, 適当な$m{\times }n\,$実行列$A\,$と$m\,$次元ベクトル$b\,$を用いて

$P=\{x\in {\mathbf {R} }^{n}\mid Ax\leq b\}\,$　　　　$(1)\,$

と表現できる. 凸多面体$P\,$が, ある正の実数$M\,$に対して

$x\in P\;\Longrightarrow \;|x_{i}|\leq M\quad (i=1,\cdots ,n)\,$

をみたすとき有界である(bounded)とよばれ, 英語では convex polytopeと区別してよばれることが多い. 凸多面体の例としては, 線形計画問題での実行可能多面体, TSP多面体, マトロイドの基多面体, ポリマトロイドなどがある.

　凸多面体には不等式表現以外にもう一つ有益な表現方法がある. $v^{1},\cdots ,v^{\ell }\in {\mathbf {R} }^{n}\,$に対して, 適当な$\alpha _{1},\cdots ,\alpha _{\ell }\in {\mathbf {R} }\,$によって

$v=\alpha _{1}v^{1}+\cdots +\alpha _{\ell }v^{\ell }\,$

と表現されるベクトル $v\,$ を$v^{1},\cdots ,v^{\ell }\,$の一次結合(線形結合) (linear combination) とよぶ. 係数$\alpha _{1},\cdots ,\alpha _{\ell }\,$が非負条件

$\alpha _{1}\geq 0,\cdots ,\alpha _{\ell }\geq 0\,$　　　　$(2)\,$

をみたす場合には $v\,$ は非負結合(nonnegative combination), 和が1という条件

$\alpha _{1}+\cdots +\alpha _{\ell }=1\,$　　　　$(3)\,$

をみたす場合には $v\,$ はアフィン結合 (affine combination), さらに (2) と (3) の両方をみたすとき $v\,$ は$v^{1},\cdots ,v^{\ell }\,$の凸結合 (convex combination) とよばれる. 有限個の$v^{1},\cdots ,v^{\ell }\in {\mathbf {R} }^{n}\,$と$r^{1},\cdots ,r^{d}\in {\mathbf {R} }^{n}\,$に対して, $v^{1},\cdots ,v^{\ell }\,$の凸結合と$r^{1},\cdots ,r^{d}\,$の非負結合の和として表される点全体, すなわち

$\left\{x=\sum _{i=1}^{\ell }\alpha _{i}v^{i}+\sum _{j=1}^{d}\beta _{j}d^{j}\;\;{\begin{array}{|l}\sum _{i=1}^{\ell }\alpha _{i}=1\\\alpha _{i}\geq 0\;(i=1,\cdots ,\ell )\\\beta _{j}\geq 0\;(j=1,\cdots ,d)\end{array}}\right\}\,$　　　　$(4)\,$

と定義される集合は凸多面体となり, 逆に (1) で定義される凸多面体については (4) をみたす有限個の$v^{1},\cdots ,v^{\ell }\in {\mathbf {R} }^{n}\,$と$r^{1},\cdots ,r^{d}\in {\mathbf {R} }^{n}\,$が存在することが知られている. 特に, 有界な凸多面体に対しては有限個の点$v^{1},\cdots ,v^{\ell }\in {\mathbf {R} }^{n}\,$の凸結合全体, すなわち,

$P=\left\{x=\sum _{i=1}^{\ell }\alpha _{i}v^{i}\;\;\right|\left.\sum _{i=1}^{\ell }\alpha _{i}=1,\;\;\alpha _{i}\geq 0\;(i=1,\cdots ,\ell )\right\}\,$　　　　$(5)\,$

と表現でき, (5)で定義される集合は, 点集合$V=\{v^{1},\cdots ,v^{\ell }\}\,$を含む (集合の包含関係の意味で) 最小な凸集合 (convex set)として定義される$V\,$の凸包 (convex hull) と一致する. 例えば, ${(0,0,0),(1,0,0),(0,1,0),(0,0,1)}\subset {\mathbf {R} }^{3}\,$の凸包である有界な凸多面体は

$x_{1}+x_{2}+x_{3}\leq 1,\quad x_{1}\geq 0,\quad x_{2}\geq 0,\quad x_{3}\geq 0\,$

という４本の不等式で表現できる三角錐である.

　点集合$V=\{v^{1},\cdots ,v^{\ell }\}\subseteq {\mathbf {R} }^{n}\,$について, どの要素も他の要素たちのアフィン結合で表現できないとき, すなわち,

$\alpha _{1}v^{1}+\cdots +\alpha _{\ell }v^{\ell }=0\;\Longrightarrow \;\alpha _{1}=\cdots =\alpha _{\ell }=0\,$

をみたすとき, $V\,$ はアフィン独立(affinely independent)であるという. ${\mathbf {R} }^{n}\,$からは高々 $n{+}1\,$個のアフィン独立な点しか取れない. 集合$S\subseteq {\mathbf {R} }^{n}\,$に含まれるアフィン独立な点集合で要素数最大のものを$V=\{v^{1},\cdots ,v^{\ell }\}\,$としたとき, $S\,$の次元は$\ell {-}1\,$と定義する(次元は$V\,$の選び方に依存しないことを付記しておく). 先の例では,${(0,0,0),(1,0,0),(0,1,0),(0,0,1)}\,$はアフィン独立であり, この凸包である三角錐の次元は$3\,$となる. 凸多面体$P\subseteq {\mathbf {R} }^{n}\,$の次元が $n\,$ であるとき全次元的(full dimensional)という.

　凸多面体$P\subseteq {\mathbf {R} }^{n}\,$に対して, 超平面(hyperplane) $H\,$, すなわち, 非ゼロベクトル$(a_{1},\cdots ,a_{n})^{\rm {T}}\in {\mathbf {R} }^{n}\,$と$a_{0}\in {\mathbf {R} }\,$を用いて

$H=\{x\mid a_{1}x_{1}+\cdots +a_{n}x_{n}=a_{0}\}\,$

と表現できる集合が

$P\cap H\neq \emptyset \,$　かつ　$P\subseteq \{x\mid a_{1}x_{1}+\cdots +a_{n}x_{n}\leq a_{0}\}\,$

をみたすとき, $H\,$は$P\,$の支持超平面 (supporting hyperplane) とよばれる. 支持超平面と凸多面体の共通部分も凸多面体である. この共通部分を凸多面体の面 (face) とよび, その次元が$k\,$であるとき$k\,$次元面($k\,$-face, $k\,$ dimensional face)とよぶ. 特に多面体より次元が$1\,$小さい面をファセット(facet), $1\,$次元面を辺 (edge), $0\,$次元面を頂点 (vertex) とよぶ. 先の三角錐を例にすると, 不等式表現の４本に対応する面は$2\,$次元面 (ファセット) であり, 他に6個の$1\,$次元面 (辺) と4個の$0\,$次元面 (頂点) を持つ. 一般に有界な凸多面体は頂点全体の凸包と一致し, 全次元的な凸多面体はファセットに対応した不等式で一意的に表現できる (不等式の両辺を正数倍しても同じものとみなす). 凸多面体自身と空集合を便宜上面とすると, 面全体は包含関係に関して束となり, 凸多面体の面束 (face lattice) とよばれる. 同型な面束を持つ凸多面体を互いに組合せ的に同型 (combinatorially equivalent) とよぶ. 束の順序関係を逆にしても束となるが, 任意の凸多面体の面束の順序関係を逆にした束と同型な面束を持つ凸多面体が常に存在し, これは, 元の凸多面体の双対多面体 (dual polytope) とよばれる.

　凸多面体は計算幾何学の重要な研究対象であるばかりでなく, 組合せ最適化問題の実行可能解全体を表現あるいは近似的に表現するための有益な道具である. 多面体理論の項目も参照されたい.

---

参考文献

[1] A. Brondsted, An Introduction to Convex Polytopes, Springer-Verlag, 1980.

[2] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley-Interscience, 1988.

[3] G. M. Ziegler, Lectures on Polytopes, Springer, 1995.