-Basic Linear Algebra-
8. 볼록성(Convexity)
8.1. 대충 설명하자면..
오늘은 볼록성에 대해 알아보자. 볼록성은 말 그대로 볼록하냐 안 하냐를 말하는 것이다. 예를 들어 볼록렌즈는 마냥 볼록하다. 무슨 소리냐 하면 렌즈면이 볼록할 뿐 중간에 조금이라도 움푹 들어간 부분이 없다는 뜻이다. 오목렌즈는 오목(concave)하다. 마찬가지로 오목렌즈는 렌즈면이 오목할 뿐 중간에 뽈록 튀어나온 부분이 없는 것이다. 그리고 우리는 직관적으로 이 볼록렌즈나 오목렌즈의 정점(vertex)이 렌즈면 중에서 가장 높거나 가장 낮다는 것을 알고 있다.
이와 유사하게 만약 어떤 함수가 볼록하다는 것을 알고 있으면 그 구간 안에 극소점(minimum)이 반드시 딱 한 개만 있을 것이고 그것이 곧 최소점이라고 직관적으로 예상할 수 있다. 두 개도 아니고 딱 한 개만 있다. 왜냐하면 볼록하다고 하면 중간에 움푹 들어간 곳이 없다는 것이기 때문이다. 따라서 우리는 함수가 볼록하다는 것만 판단이 되면 우리가 찾은 어떤 극소점(local minimum)은 반드시 전역 최소점(global minimum)이라고 선언할 수 있게 된다. 그리고 왜 볼록한데 최솟값이냐 하면 수학에서는 어떤 함수가 아래쪽으로 배가 나왔을 때 볼록하다고 하기 때문이다. 그럼 수학에서는 볼록하다는 것을 어떻게 정의하는지 알아보자.
8.2. 볼록 집합(Convex Set)
$x$와 $y$가 어떤 집합 $\theta$에 속할 때 $x$와 $y$를 연결한 직선 위의 모든 점들이 $\theta$에 속하면 집합 $\theta$는 볼록하다. 역도 성립한다.
$$ \forall x, y \in \theta,\quad \alpha \in [0, 1] $$
$$ \alpha x + (1-\alpha)y \in \theta $$
8.3. 볼록 함수(Convex Function)
볼록 함수는 다음과 같이 정의한다.
$$ \forall \boldsymbol{x}_1, \boldsymbol{x}_2 \in \theta,\quad \alpha \in [0, 1] $$
$$ f(\alpha\boldsymbol{x}_1 + (1-\alpha)\boldsymbol{x}_2) \leq \alpha f(\boldsymbol{x}_1) + (1-\alpha)f(\boldsymbol{x}_2) $$
수식이 괜히 복잡해 보이니 아래처럼 다시 써보자. 어떤 볼록 집합에 속하는 임의의 두 입력 $\boldsymbol{x}_1, \boldsymbol{x}_2$사이에는 어떤 입력 $\boldsymbol{x}_k$가 존재한다.
$$ \boldsymbol{x}_k = \alpha\boldsymbol{x}_1 + (1-\alpha)\boldsymbol{x}_2 $$
이때 함수값 $f(\boldsymbol{x}_k)$이 각 입력 $\boldsymbol{x}_1, \boldsymbol{x}_2$에 대한 함수 값을 연결한 직선 위의 값보다 작으면 이 함수 $f(\boldsymbol{x})$는 볼록하다.
$$ f(\boldsymbol{x}_k) \leq \alpha f(\boldsymbol{x}_1) + (1-\alpha)f(\boldsymbol{x}_2) $$
위 볼록성의 정의를 보면 "작거나 같다($\leq$)"로 되어 있는 것에 주목하자. 등호가 포함 된다는 것은 함수의 위 두 점을 연결한 직선과 같아도 된다는 것이다. 따라서 아래 그림3과 같은 함수도 볼록하다. 왜냐하면 선형 함수는 볼록하면서 오목한 것이기 때문이다. 볼록하기는 한데 오목하기도 하기 때문에 이런 경우는 엄격하게 볼록(strictly convex)한 것은 아니라고 말한다. 그림 2와 같은 경우는 엄격하게 볼록한 것이다.
8.4. 여러가지 성질
1. $\theta$가 볼록 집합이고 $\beta \in \mathbb{R}$이면 $\beta\theta$ 역시 볼록하다.
2. $\theta_1, \theta_2$가 볼록 집합이면 $\theta_1+\theta_2$ 역시 볼록하다.
$$ \theta_1 + \theta_2 = \{\boldsymbol{x}\ |\ \boldsymbol{x}=\boldsymbol{v}_1+\boldsymbol{v}_2,\quad \boldsymbol{v}_1\in\theta_1,\ \boldsymbol{v}_2\in\theta_2\} $$
Proof)
$\boldsymbol{v}_1,\boldsymbol{v}_2 \in \theta_1+\theta_2$라고 하자. 그리고 $\boldsymbol{v}_1,\boldsymbol{v}_2$는 원래 $\theta_1$과 $\theta_2$에 있던 원소의 합이므로 다음과 같이 쓸 수 있다.
$$ \boldsymbol{v}_1 = \boldsymbol{v}_1' + \boldsymbol{v}_1'' $$
$$ \boldsymbol{v}_2 = \boldsymbol{v}_2' + \boldsymbol{v}_2'' $$
$$ \text{where, } \boldsymbol{v}_1', \boldsymbol{v}_2' \in \theta_1,\ \boldsymbol{v}_1'', \boldsymbol{v}_2'' \in \theta_2 $$
이 때 $\theta_1$과 $\theta_2$가 볼록 집합이면 어떤 $\alpha \in [0,1]$에 대해 다음이 성립한다.
$$ \boldsymbol{x}_1 = \alpha\boldsymbol{v}_1' + (1-\alpha)\boldsymbol{v}_2' \in \theta_1 $$
$$ \boldsymbol{x}_2 = \alpha\boldsymbol{v}_1'' + (1-\alpha)\boldsymbol{v}_2'' \in \theta_2 $$
$\theta_1 + \theta_2$의 정의에 의해 $\boldsymbol{x}_1+\boldsymbol{x_2}$는 $\theta_1+\theta_2$에 속한다.
$$ \boldsymbol{x}_1+\boldsymbol{x_2} \in \theta_1+\theta_2 $$
$$ \text{since, }\boldsymbol{x}_1\in\theta_1,\ \boldsymbol{x}_2\in\theta_2 $$
$\boldsymbol{x}_1+\boldsymbol{x_2}$는 다시 다음과 같이 쓸 수 있다.
\begin{align} \boldsymbol{x}_1+\boldsymbol{x_2} &= \alpha(\boldsymbol{v}_1' + \boldsymbol{v}_1'') + (1-\alpha)(\boldsymbol{v}_2' + \boldsymbol{v}_2'') \\\\ &= \alpha\boldsymbol{v}_1 + (1-\alpha)\boldsymbol{v}_2 \in \theta_1 + \theta_2 \end{align}
따라서 $\theta_1+\theta_2$는 볼록 집합이다.
3. $\theta_1 + \theta_2$는 $\theta_1 \cup \theta_2$와 다르다.
다음과 같이 볼록 집합 $\theta_1$과 $\theta_2$가 있다고 하자.
$$ \theta_1 = \{\boldsymbol{x}=(x_1, x_2)\ |\ 2 \leq x_1 \leq 4,\ 2 \leq x_2 \leq 4\} $$
$$ \theta_2 = \{\boldsymbol{x}=(x_1, x_2)\ |\ 3 \leq x_1 \leq 5,\ 3 \leq x_2 \leq 5\} $$
두 볼록 집합의 합은 다음과 같이 쓴다.
$$ \theta_1 + \theta_2 = \{\boldsymbol{x}\ |\ \boldsymbol{x}=\boldsymbol{x}_1+\boldsymbol{x}_2,\ \boldsymbol{x}_1\in\theta_1,\ \boldsymbol{x}_2\in\theta_2\} $$
이 경우 $\theta_1\cup\theta_2$와 $\theta_1+\theta_2$를 비교해 보면 그림 4~5와 같다.
두 결과가 상당히 다르다는 것을 알 수 있다. 합집합은 원소들의 나열이 단순히 합쳐지는 것이고 집합의 합은 모든 원소 사이의 덧셈에 대한 무수한 경우의 수가 결과이기 때문이다.
4. 볼록 집합의 교집합(intersection)은 볼록 집합이다.
볼록한 것들끼리 교집합 하면 볼록 밖에 안 나온다. 선형 함수는 볼록하면서 동시에 오목한 것이다. 다시 말해 선형 함수는 볼록하다고 해도 되고 오목하다고 해도 된다. 이 선형 함수들의 교집합은 반드시 볼록하다.
최근댓글