Affine and convex sets - Euclidean ball and ellipsoid

$\mathbf{R}^n$에서 Euclidean ball은 아래와 같은 형태를 가진다.

$$ \begin{align} \text{B(} x_c , r \text{)} \; &= \; \left\{ x \; | \; \lVert x-x_x \rVert _2 \leq r \right\} \; \\ &= \; \left\{x \; | \; \left( x-x_c \right)^T \left( x-x_c \right) \leq r^2 \right\} \\ &= \; \left\{ x_c+ru \; | \; \lVert u \rVert_2 \leq 1 \right\}  \end{align}$$

 

여기서 $x_c$는 Ball의 Center를 의미하며, $r$은 Ball의 반지름($ r > 0 $)을 의미한다. 

 

또한 수학기호 $ \lVert · \rVert$는 norm을 의미한다.  ($\lVert u \rVert_2 = \left( u^t u \right)^{1 \over 2}$)

 

Ball의 기하학적인 의미는 점 $x_c$(center)에서 거리가 r에 있는 모든 점들의 집합을 의미한다.

 

Euclidean Ball 또한 Convex set이며 convex set의 정의를 생각하면 직관적으로 convex set임을 알 수 있다. 

(convex set의 정의 - 어떤 집합의 임의의 점 두개를 연결한 선분이 두 점이 속한 집합에 포함될때, 그 집합을 convex set이라고 한다)

 

이를 수학적으로 다시 한번 증명하면 아래와 같을 것이다. 

 

Euclidean ball이 convex set임을 보이기 위해서는 ball에 속하는 임의의 점 $x_1, \; x_2$로 이어지는 선분이 다시 Euclidean ball에 속하는 것을 보이면 된다.  

 

즉, $ 0 \leq \theta \leq 1$ 을 만족하는 임의의 $ \theta $에 대해서  $\theta x_1 + (1-\theta) x_2$가 다시 Euclidean ball에 속하는 것을 보이면 된다.

($\lVert \theta x_1 + (1- \theta ) x_2 - x_c \rVert_2 \leq r$을 만족함을 보이면 된다.)

 

한편 ball에 속하는 임의의 점 $x_1, \; x_2$에 대해 $\lVert x_1 - x_c \rVert_2 \leq r$,  $\; \lVert x_2 - x_c \rVert_2 \leq r$가 성립하며, 이를 이용해서 다음과 같은 결론을 도출 할 수 있다.

$$ \begin{align} \lVert \theta x_1 + (1- \theta ) x_2 - x_c \rVert_2 &= \lVert \theta (x_1 - x_c) + (1- \theta )(x_2 - x_c) \rVert_2 \quad \text{· · · · ·   (1)} \\ &\leq \lVert \theta (x_1 - x_c) \rVert _2 + \lVert (1-\theta)(x_2-x_c) \rVert _2 \quad \text{· · · · ·   (2)} \\ & \leq \theta r + (1- \theta)r \quad \text{· · · · ·   (3)}\\ & \leq r \quad \text{· · · · ·   (4)} \end{align}$$

 

즉, $\lVert \theta x_1 + (1- \theta ) x_2 - x_c \rVert_2 \leq r$을 만족하므로, Euclidean ball은 convex set이다.

 

참고로, 수식(1)에서 (2)로 전개될때 norm의 성질 중 하나인 triangle inequality를 이용한 것이다.

 

다음은 Ellipsoid도 알아보자. 고등학교때 타원으로 공부했는데, $R^n$에서 아래와 같은 형태를 가진다.

$$ \begin{align} \varepsilon &=  \left\{ x \; | \; (x-x_c)^T P^{-1} (x-x_c) \leq 1 \right\} \\ &= \left\{ x_c + Au \; | \; \lVert u \rVert_2 \leq 1 \right\} \end{align}$$

여기서  Matrix $P$는 Positive definite하며 symmetric ($P = P^T \succeq 0 $)한 Matrix이다. 

(참고로 Matrix A가 positive definite라는 의미는 0아 아닌 x에 대해 $x^T Ax \geq 0$를 만족한다는 것이며, 이때 eigenvalue는 모두 양수이다.)

 

또한 Matrix A는 square하고 nonsingular(역행렬이 존재)한 Matrix이다.

 

Euclidean ball 처럼 $x_c$는 ellipsoid의 center 이다. ($x_c \in R^n$)

 

Matrix P는 ellipsoid가 center $x_c$에서, 사방으로 얼마나 멀어지는지를 결정한다.

(ellipsoid의 semi-axes가 $ \sqrt{ \lambda_i}$로 주어짐 )

 

ball은 $P = r^2 I$인 ellipsoid의 특수한 경우이다. 

 

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