02-01-03 Convex set

이제 이 장의 핵심 개념인 convex set을 살펴보자. 직관적으로 convex set이란 오목하게 들어간 부분이나 내부에 구멍이 없는 집합을 의미한다. 따라서, 어떤 집합이 convex set이라고 말할 수 있으려면 집합에 속한 임의의 두 점으로 선분(line segment)을 만들어서 그 선분이 집합에 포함되는지를 보면 된다.

Convex set

집합 $C\subseteq R^n$에 속한 두 점 $x_1$, $x_2\in C$을 연결한 line segment가 $C$에 포함되면 이 집합을 convex set이라고 한다.

$\theta x_1+(1-\theta )x_2\in C$ with $x_1,x_2\in C$, $0\le \theta \le 1$

이 식을 다르게 해석해 보면 set $C$에 속한 두 점을 linear combination하되 계수가 양수이고 계수의 합을 1로 제한했다고 볼 수 있다. 그리고, 그 결과가 $C$에 다시 포함되면 convex set이다.

아래 그림에는 convex set을 설명하는 예들이 있다. 왼쪽의 육각형은 convex이지만 가운데 있는 콩팥 모양은 내부에 두 점을 이었을 때 선분이 외부로 나가기 때문에 convex가 아니다. 오른쪽 네모의 경우 경계의 일부가 open된 상태라 경계에서 선분을 만들면 set의 범위를 벗어나므로 convex가 아니다.

Convex combination

점들을 linear combination할 때 계수가 양수이고 계수의 합을 1로 제한하면 이를 convex combination이라고 한다.

A point of the form ${\theta }_1{x}_1+{\theta }_2{x}_2+\cdots +{\theta }_k{x}_k$ with ${\theta }_1+{\theta }_2+\cdots +{\theta }_k=1,{\theta }_i\ge 0,i=1,...,k$

이제 convex set의 정의를 convex combination 개념을 이용해서 일반화해 볼 수 있다. 즉, 어떤 집합 C에 속하는 임의의 여러 점들의 convex combination이 집합 C에 속하면 그 집합은 convex set이라고 말할 수 있다.

반대로 convex set C에 속하는 점들의 convex combination은 항상 set C에 속하게 된다.

Convex hull

$C\subseteq R^n$에 포함된 점들의 모든 convex combination들의 집합을 $C$의 convex hull이라고 하며 conv $C$로 표기한다. Convex hull conv $C$은 항상 convex이며, 집합 $C$를 포함하는 가장 작은 convex set이다.

conv $C=\{{\theta }_1{x}_1+\cdots +{\theta }_k{x}_k\phantom{1}\mid \phantom{1}{x}_i\in C,\phantom{1}{\theta }_i\ge 0,\phantom{1}i=1,...,k,\phantom{1}{\theta }_1+\cdots +{\theta }_k=1\}$ 아래 그림은 15개의 점으로 이뤄진 집합과 콩팥 모양의 집합에 대한 convex hull이다.