《凸多面体》

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

　$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n} $次元実ベクトル$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a=(a_1,\cdots,a_n)^{\rm T} \in {\bf R}^n} $と実数 $$a_{0}{\in }{\bf {R}}$$ により定まる1次不等式 (線形不等式) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \(a_1 x_1 + \cdots + a_n x_n \leq a_0\)} を満たす点$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x = (x_1,\cdots,x_n)^{\rm T}} $全体からなる集合を閉半空間(closed halfspace)とよぶ. 有限個の閉半空間の共通部分を凸多面体 (convex polyhedron) とよぶ. すなわち, $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\bf R}^n$} 内の凸多面体は, 適当な$$m{\times }n$$実行列$$A$$と$$m$$次元ベクトル$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b} $を用いて

$P=\{x\in {\bf {R}}^{n}\mid Ax\leq b\}$　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (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 {\bf {R}}^{n}$$に対して, 適当な$$\alpha _{1},\cdots ,\alpha _{\ell }\in {\bf {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$　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (2)}

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

$\alpha _{1}+\cdots +\alpha _{\ell }=1$　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (3)}

をみたす場合には $$v$$ はアフィン結合 (affine combination), さらに (2) と (3) の両方をみたすとき $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v} $ は$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v^1,\cdots,v^\ell} $の凸結合 (convex combination) とよばれる. 有限個の$構文解析に失敗 (構文エラー): {\displaystyle v^1,\cdots,v^\ell \in {\bf R}^n$と$r^1,\cdots,r^d \in {\bf R}^n$} に対して, $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v^1,\cdots,v^\ell} $の凸結合と$$r^{1},\cdots ,r^{d}$$の非負結合の和として表される点全体, すなわち

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \left\{ x = \sum_{i=1}^\ell \alpha_iv^i + \sum_{j=1}^d \beta_jd^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 {\bf {R}}^{n}$$と$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r^1,\cdots,r^d \in {\bf R}^n} $が存在することが知られている. 特に, 有界な凸多面体に対しては有限個の点$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v^1,\cdots,v^\ell \in {\bf 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)で定義される集合は, 点集合$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V=\{v^1,\cdots,v^\ell\}} $を含む (集合の包含関係の意味で) 最小な凸集合 (convex set)として定義される$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V} $の凸包 (convex hull) と一致する. 例えば, ${(0,0,0),(1,0,0),(0,1,0),(0,0,1)}\subset {\bf {R}}^{3}$$の凸包である有界な凸多面体は

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_1+x_2+x_3 \leq 1,\quad x_1 \geq 0, \quad x_2 \geq 0, \quad x_3 \geq 0}

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

　点集合$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V=\{v^1,\cdots,v^\ell\} \subseteq {\bf R}^n} $について, どの要素も他の要素たちのアフィン結合で表現できないとき, すなわち,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_1v^1 + \cdots + \alpha_\ell v^\ell = 0 \;\Longrightarrow\; \alpha_1 = \cdots = \alpha_\ell = 0}

をみたすとき, $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V} $ はアフィン独立(affinely independent)であるという. $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\bf R}^n} $からは高々 $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n{+}1$} 個のアフィン独立な点しか取れない. 集合$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S \subseteq {\bf R}^n} $に含まれるアフィン独立な点集合で要素数最大のものを$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V=\{v^1,\cdots,v^\ell\}} $としたとき, $$S$$の次元は$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \ell{-}1} $と定義する(次元は$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V} $の選び方に依存しないことを付記しておく). 先の例では,${(0,0,0),(1,0,0),(0,1,0),(0,0,1)}$$はアフィン独立であり, この凸包である三角錐の次元は$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 3} $となる. 凸多面体$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P \subseteq {\bf R}^n} $の次元が $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n} $ であるとき全次元的(full dimensional)という.

　凸多面体$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P \subseteq {\bf R}^n} $に対して, 超平面(hyperplane) $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle H} $, すなわち,

非ゼロベクトル$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (a_1,\cdots,a_n)^{\rm T} \in {\bf R}^n} $と$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a_0 \in {\bf R}} $を用いて

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle H = \{x \mid a_1x_1 + \cdots + a_nx_n = a_0 \}}

と表現できる集合が

:構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P \cap H \neq \emptyset \quad\}
かつ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \quad  P \subseteq \{x \mid a_1x_1 + \cdots + a_nx_n \leq a_0 \}}

をみたすとき, $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle H} $は$$P$$の支持超平面 (supporting hyperplane) とよばれる. 支持超平面と凸多面体の共通部分も凸多面体である. この共通部分を凸多面体の面 (face) とよび, その次元が$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k} $であるとき$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k} $次元面($$k$$-face, $$k$$ dimensional face)とよぶ. 特に多面体より次元が$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1} $小さい面をファセット(facet), $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1} $次元面を辺 (edge), $構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0} $次元面を頂点 (vertex) とよぶ. 先の三角錐を例にすると, 不等式表現の４本に対応する面は$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 2} $次元面 (ファセット) であり, 他に6個の$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1} $次元面 (辺) と4個の$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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.