[Convex Optimization] Affine/Convex set

 

1. Affine set

아핀 집합은 벡터 공간에서 선형 부분 공간의 개념을 확장한 것으로, 원점을 통과할 필요가 없는 "평평한" 구조를 가리킵니다. 볼록 집합과 유사하게, 아핀 집합은 집합 내의 두 점을 잇는 직선 위의 모든 점을 포함한다는 중요한 특징을 가집니다. 직선이 포함된다는 의미는 경계가 없다는 의미이므로 어떤 공간이 경계가 있다면 affine set이 될 수 없다는 말도 되겠죠.  점(point), 직선(line), 평면(plane), 초평면(hyperplane) 등이 affine set의 예라고 할 수 있습니다. 

 

집합 \(C \subseteq \mathbf{R}^n\) 이 affine set이라는 것은 집합 \(C\) 내의 임의의 두 점 \(x_{1}, x_{2} \in C\)를 잇는 직선 상의 모든 점이 다시 \(C\)에 포함된다는 의미이다.  

즉, 임의의 두 점 \(x_{1}, x_{2} \in C\)와 임의의 \(\theta \in \mathbf{R} \)에 대해서 $$\theta x_1 + (1-\theta) x_2 \in C$$

 

Affine set은 아래와 같은 특성을 갖습니다. 

1) 모든 affine combination에 대해 닫혀있다. 

2) 모든 affine set은 convex set이다. 

 

2. Affine Combination

k개의 점 \(x_{1}, ..., x_{k} \in \mathbf{R}^n \) 이 주어졌을 때 이들의 Affine combination은 아래와 같이 표현되는 점 \(x\)를 의미합니다. 

\[x = \theta_1 x_1 + \dots + \theta_k x_k\]

여기서 \(\theta_1 + \dots + \theta_k \in \mathbf{R} \) 은 다음 조건을 만족해야 합니다. \( \theta_1 + \dots + \theta_k = 1 \)

뭔가 선형결합과 유사하지만 계수의 합이 1이되어야 한다는 추가 조건이 있죠?

 

3. Affine Hull

집합 \(C \subseteq \mathbf{R}^n\) 의 affine hull aff(\(C\))는 \(C\)를 포함하는 가장 작은 affine set 을 말합니다.

$$\mathrm{aff}(C) = \{\theta_1 x_1 + \dots + \theta_k x_k \mid x_1, \dots, x_k \in C, \sum_{i=1}^k \theta_i = 1, k \in \mathbf{Z}^+ \}$$

 

4. Convex set

직관적으로 convex set은 "속이 꽉 찬" 형태이며 집합 내의 어떤 두 점을 선택하더라도 그 두 점을 잇는 선분 전체가 항상 집합 내에 존재하는 특징을 가집니다. 

 

집합 \(C \subseteq \mathbf{R}^n\) 이 convex set이라는 것은 집합 \(C\) 내의 임의의 두 점 \(x_{1}, x_{2} \in C\)를 잇는 선분(segment) 상의 모든 점이 다시 \(C\)에 포함된다는 의미이다.  

즉, 임의의 두 점 \(x_{1}, x_{2} \in C\)와 임의의 \( \theta \in [0, 1] \) 에 대해서 $$\theta x_1 + (1-\theta) x_2 \in C$$

 

convex set은 모든 convex combination에 대해 닫혀있는 특성을 갖고 있습니다. 

 

5. Convex Combination

k개의 점 \(x_{1}, ..., x_{k} \in \mathbf{R}^n \) 이 주어졌을 때 이들의 convex combination은 아래와 같이 표현되는 점 \(x\)를 의미합니다. 

\[x = \theta_1 x_1 + \dots + \theta_k x_k\]

여기서 \(\theta_1 + \dots + \theta_k \in \mathbf{R} \) 은 다음 두 조건을 만족해야 합니다.

1) \( \theta_1 + \dots + \theta_k = 1 \)

2) \(\theta_i \ge 0 \quad \text{for } i = 1, \dots, k\)

 

6. Convex Hull

집합 \(C \subseteq \mathbf{R}^n\) 의 convex hull conv(\(C\))는 \(C\)를 포함하는 가장 작은 convex set 을 말합니다. 이는 \(C\)의 모든 점들의 가능한 모든 convex combination으로 이루어진 set과 동일합니다.

$$\mathrm{conv}(C) = \{\theta_1 x_1 + \dots + \theta_k x_k \mid x_1, \dots, x_k \in C, \theta_i \ge 0, \sum_{i=1}^k \theta_i = 1, k \in \mathbf{Z}^+ \}$$