Affine and convex sets - convex sets

이번에는 Convex sets에 대해 알아보자. 

Convex sets의 수리적인 정의는 아래 식과 같다.

$$ \text{if for any}\; x_1,\;x_2\; \in C\; \text{and}\; \text{any} \; \theta \; \text{with} \; 0 \leq \theta \leq 1, \text{we} \; \text{have}\; \theta x_1 + \left(1- \theta \right) x_2 \; \in C $$
위 수식의 의미를 설명하면, 

어떤 임의의 집합 C의 두점을 연결한 선분(line segment)가 다시 집합 C에 속하게 될때, 그 집합 C를 Convex set이라 정의한다는 것이다

아래 그림은 Convex set의 쉽게 설명해주는 예시이다. 

좌측의 육각형은 내부의 두 점을 연결해도 항상 그 선분이 원래 집합에 포함됨을 알 수 있으며, 따라서 좌측 육각형은 convex set이다. 

 

한편, 우측의 그림은 Convex set의 정의에 따라 임의의 두 점을 연결한 선분이 원래 집합에 포함 되지 않기 때문에 convex set이 아님을 알 수 있다.

 

또한, 지난번 시간에 공부했던 affine set과 convex set의 관계에 대해서도 생각해보자.

 

결론부터 이야기 하면, 모든 affine set은 모두 convex set이다. 

 

이는 affine set의 정의를 생각하면 쉽게 이해할 수 있다. 

affine set은 집합 내부의 임의의 두 점을 연결하는 직선을 포함하는 집합이다. 또한 직선을 포함하고 있기 때문에 선분 또한 당연히 집합에 포함된다.

 

따라서 모든 affine set은 자연스럽게 convex set이다. 

다음은 convex combination에 대해서 알아보자. 

 

convex combination은 affine combination에서 θ가 0보다 크다는 제약조건이 추가가 된 것이다.

 

affine set과 마찬가지로, 집합 C에 속하는 임의의 점들에 대해서 convex combination을 했을때, convex combination 된 점이 

다시 집합 C에 속할때, 그 집합은 convex set이다.

다음은 convex hull에 대해서 알아보자.

어떤 집합 C의 점들에 대해 convex combination으로 된 점들의 집합을 convex hull이라고 하며, 수학적인 표현은 아래와 같다.

 

$$ \mathbf{con C}\; = \;\left\{ \theta_1 x_1\; + \;.\; .\; .\; +\; \theta_k x_k \; \text{|}\; \; x_i \in C, \; \theta_i \geq 0, \; i=1,\;.\;.\;.\;k,\; \theta_1+.\;.\;.+ \theta_k = 1 \right\} $$

convex hull은 위에서 설명했듯, convex combination으로 된 점들의 집합이기 때문에 항상 convex set이며, 집합 C를 포함하는

가장 작은 convex set이다. 

convex combination은 무한합(infinite sum) 또는 integral을 통해 일반화가 가능하다.  

 

이를 수학적으로 쓰면 아래와 같다.

 

$$ \text{suppose} \; \theta_1 \; \theta_2 \; .\;.\;.\; \; \text{satisfy} \; \; \theta_i \geq 0, \; i \; = \; 1,\;2,\;.\;.\;.\;,\; \; \sum_{i=1}^\infty \theta_i = 1\; $$

$$\; \text{and} \; x_1\; x_2,\;. \;. \;. \; \in C, \; \text{where} \; C \subseteq \textbf{R}^n \; \text{is}\; \text{convex.}$$

$$\text{then} \; 
\sum_{k=1}^\infty \theta_i x_i \; \in C, \; \text{if the series converges.} $$

 

그림 및 내용 출처 : Boyd, S., Boyd, S. P., & Vandenberghe, L. (2004). Convex optimization. Cambridge university press.