Affine and convex - Affine sets

Affine set의 정의는 수식으로 표현하면 다음과 같다.

 

$$ if\;for\;any\;x_1, x_2 \in C \; and\; \theta \in R,\;we\;have\;\theta x_1+(1-\theta)x_2 \in C, \quad then\; A\; set\; C \subseteq R^n\;is\; affine$$

 

이를 해석하면, 집합 C의 임의의 점 2개를 선택하고, 그 선택한 2개의 점을 연결하는 Line이 다시 집합 C에 속할때,

 

그 집합 C를 Affine set이라고 한다.

 

또한, 위 수식은 집합 C의 임의의 두개의 점에 대해 선형결합의 계수의 합이 1인 선형결합이 다시 집합 C에 속하는 것으로도 이해할 수 있다. (선형결합의 계수의 합이 1이라는 의미는 예를 들어, 위 식에서 2개 점들의 계수가 (1-θ)와 θ이며, 그 합은 1임) 

 

이 아이디어는 두개 이상의 점으로 일반화(Generalization)이 가능하다. 이를 위해 affine combination을 먼저 알아야한다.

 

$$ \theta_1x_1+\theta_2x_2+\;·\;·\;·\;+\theta_kx_k, \;\;where\;\; \theta_1+\theta_2+\;·\;·\;·\;+\theta_k=1 $$

 

위와 같은 형태를 affine combination이라고 한다. affine combination을 이용하여 affine set의 정의를 수식으로 표현하면 다음과 같다.

 

차후에 공부를 하면 알게되겠지만, 여기서 중요한 것은 θ들의 범위가 정해져 있지 않고, 단순히 그들의 합이 1이라는 점이다.

(차후에 다른 combination들도 나오는데, 형태가 비슷하기 때문에 정확하게 알아야 한다.)

 

$$ \text{If}\; x_1,\;·\;·\;·\,x_k\in C,\; \theta_1+\;·\;·\;·\,+\theta_k=1, \;\text{and the point}\; \theta_1x_1+\;·\;·\;·\;+\theta_kx_k \in C\; \text{then a set C is an affine set} $$

 

어떤 집합 C의 임의의 점들을 affine combination이 다시 집합 C에 속하면 그 집합 C는 Affine set이다.

 

이를 해석하면, 집합 C의 임의의 점들의 affine combination이 다시 집합 C에 속할때, 그 집합 C를 Affine set이라고 한다.

 

만약 집합 C가 affine set이고, 집합 C의 임의의 점에 대해, 아래의 집합 V는 부분공간(subspace)이다. 

$$ V=C-x_0=\left\{ x-x_0 \; \text{|} \; x \in C \right\} $$

여기서 부분공간이란 덧셈과 스칼라 곱에 닫혀있는 집합을 의미한다.

 

이를 증명해보자.

부분공간이라는 것을 증명하기 위해서는 집합 V의 원소에 대해 스칼라 곱과 덧셈 연산을 했을때 원래 집합 V에 다시 속하면 되는 것을 보이면 된다.

 

$$ \text{Suppose}\; v_1,\; v_2\;\in V\; \text{and}\; \alpha,\;\beta\;\in R. \; \text{then}\; v_1+x_0\in C \; \text{and} \; v_2+x_0\; \in C  \;·\;·\;·\  (1) $$

 

(1)은 집합 V의 정의에 따라 당연하게 얻을 수 있는 결과이다. 이어서 증명해 보면

 

$$ \text{and so,} \;\; \alpha v_1+\beta v_2 + x_0 = \alpha \left( v_1+v_0 \right) + \beta \left( v_2 + x_0 \right) + \left( 1- \alpha - \beta \right)x_0 \in C \;·\;·\;·\  (2) $$ 

(2)는 affine set의 정의를 생각하면 쉽게 이해할 수 있다. 집합 C가 affine set이기 때문에, 그 내부의 점들의 affine combination 또한 affine set에 포함된다.    

$$ \left( v_1+v_0 \right),\; \left( v_2 + x_0 \right),\; x_0 \in C\; \text{and}, \alpha + \beta +\left( 1- \alpha - \beta \right)=1\;  $$

 

위의 조건을 만족하기 때문에 (2)를 만족하는 것이다. 

 

(1)과 (2)를 통해서  우리는 다음과 같은 결론을 얻을 수 있다. 

$$ \text{since } \alpha v_1 + \beta v_2 + x_0 \in C, \text{we can conclude } \alpha v_1+ \beta v_2 \in V $$

즉, 집합 V의 임의의 원소가 덧셈과 곱셈에 닫혀있기 때문에, 집합 V는 부분공간이다.

 

affine hull의 정의를 수식으로 쓰면 아래와 같다.

$$ \text{aff C}\; = \left\{ \theta_1 x_1+ \;·\;·\;· + \theta_k x_k \text{|}\;x_1,.\;.\;.\;, x_k \in C, \; \; \theta_1++ \;·\;·\;·+\theta_k=1 \right\}  $$

 

위 수식을 직관적으로 이해하면, 어떤 임의의 집합 C(실수공간의 부분집합)의 모든 점들을 affine combination하여 만든 점들의 집합이 affine hull이라는 것이다. 

 

affine hull은 방금전 언급한 임의의 집합 C를 포함하는 가장 작은 affine set이며, 수식으로 표현하면 아래와 같다.

$$ \text{ if S is any affine set with}\; C \in S, \text{then}\; \text{aff C} \in S$$

 

 

 

 

 

 

 

 

 

출처 : Boyd, S., Boyd, S. P., & Vandenberghe, L. (2004). Convex optimization. Cambridge university press.