볼록 다포체

2. 정의

볼록 다포체는 문제에 따라 다양한 방법으로 정의될 수 있다. 그륀바움은 공간에서 점들의 볼록 집합의 관점에서 정의했다. 다른 중요한 정의는 반공간들의 교집합(반공간 표기)과 점들의 집합의 볼록 껍질(꼭짓점 표기)로 정의하는 것이다.

그륀바움은 그의 저서 ''볼록 다포체''에서 볼록 다포체를 '''유한한 수의 극점을 가지는 콤팩트 볼록 집합'''으로 정의했다.

: $K$가 $\backslash mathbb\{R\}^n$의 집합일 때, $K$ 내의 서로 다른 두 점 $a$, $b$에 대해, $a$와 $b$를 양 끝점으로 하는 닫힌 선분이 $K$ 내에 포함되면, $K$는 ''볼록''하다고 한다.

닫힌 반공간은 다음의 선형 부등식으로 쓸 수 있다.^[3]

:$a\_1\; x\_1\; +\; a\_2\; x\_2\; +\; \backslash cdots\; +\; a\_n\; x\_n\; \backslash leq\; b$

여기서 $n$은 다포체를 포함하는 공간의 차원이다. 따라서, '''닫힌 볼록 다포체'''는 다음의 선형 부등식계의 해 집합으로 간주될 수 있다.

:$\backslash begin\{alignat\}\{7\}$

a_{11} x_1 &&\; + \;&& a_{12} x_2 &&\; + \cdots + \;&& a_{1n} x_n &&\; \leq \;&&& b_1 \\

a_{21} x_1 &&\; + \;&& a_{22} x_2 &&\; + \cdots + \;&& a_{2n} x_n &&\; \leq \;&&& b_2 \\

\vdots\;\;\; && && \vdots\;\;\; && && \vdots\;\;\; && &&& \;\vdots \\

a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \cdots + \;&& a_{mn} x_n &&\; \leq \;&&& b_m \\

\end{alignat}

여기서 $m$은 다포체를 정의하는 반공간의 수이다. 이는 다음과 같이 행렬 부등식으로 간결하게 쓸 수 있다.

:$Ax\; \backslash leq\; b$

여기서 $A$는 $m\backslash times\; n$ 행렬이고, $x$는 좌표가 변수 $x\_1$에서 $x\_n$인 $n\backslash times1$ 열 벡터이며, $b$는 좌표가 스칼라 부등식의 우변 $b\_1$에서 $b\_m$인 $m\backslash times1$ 열 벡터이다.

'''열린 볼록 다포체'''는 비엄격 부등식 대신 엄격 부등식을 사용하여 동일한 방식으로 정의된다.

$A$와 $b$의 각 행은 해당 반공간을 정의하는 선형 부등식의 계수에 대응된다. 따라서 행렬의 각 행은 다포체의 '''지지 초평면'''에 해당한다. 지지 초평면이 다포체와 교차하면 '''경계 초평면'''이라고 한다.

앞의 정의는 다포체가 전체 차원이라고 가정한다. 이 경우, 정의 부등식의 ''유일한'' 최소 집합이 존재한다. 이 최소 집합에 속하는 부등식을 '''본질적'''이라고 한다. 본질적 부등식을 등식으로 만족하는 다포체의 점의 집합을 '''면'''이라고 한다.

다포체가 전체 차원이 아닌 경우, $Ax\backslash leq\; b$의 해는 $\backslash mathbb\{R\}^n$의 적절한 아핀 부분 공간에 놓이며, 다포체는 이 부분 공간에서 연구될 수 있다. 이 경우, 다포체의 모든 점이 만족하는 선형 방정식이 존재한다. 이러한 방정식 중 하나를 정의 부등식에 추가해도 다포체는 변경되지 않는다. 따라서, 일반적으로 다포체를 정의하는 유일한 최소 부등식 집합은 없다.

일반적으로 임의의 반공간의 교집합은 제한될 필요가 없다. 그러나 볼록 껍질과 동일한 정의를 원한다면, 경계를 명시적으로 요구해야 한다.

2. 1. 꼭짓점 표현 (볼록 껍질)

2. 2. 반공간의 교집합