[경고] 아래 글을 읽지 않고 "볼록과 오목 함수"를 보면 바보로 느껴질 수 있습니다.
[그림 1] 볼록 함수의 정의(출처: wikipedia.org)
볼록 형태는 눈으로 보면 바로 알 수 있지만, 볼록 함수(convex function)의 수학적 정의는 한 번 더 생각이 필요하다. 쉽게 이해하려면 [그림 1]을 참고한다. 분홍색 직선보다 검정색 함수가 아래에 있는 구간이 볼록 구간(convex interval)이며, 볼록 구간을 가진 함수가 바로 볼록 함수이다[1].
(1)여기서 $x_1, x_2 \in \operatorname{dom}(f)$, $\operatorname{dom}(f)$는 함수 $f$의 정의역(domain), $0 \le t \le 1$, $x$ = $t x_1 + (1-t)x_2$, $t$ = $(x_2 - x) \mathbin{/} (x_2 - x_1)$이다. 식 (1)에서 등호가 없는 경우는 엄격 볼록 함수(strictly convex function)이라 한다. 매개변수 $t$의 중간인 $t$ = $1/2$을 대입해서 $x$와 $f(x)$의 중점(midpoint)에 대한 관계식을 얻을 수 있다.
(2)[그림 1]을 봐도 명확하지만 식 (2)는 직선의 중간값은 함수의 중간값보다 크거나 같다는 뜻이다. 엄격 볼록인 경우는 등호가 사라져서 함수값이 직선값보다 항상 작다. 만약 $x_2$ = $0$, $f(0) \le 0$이면, 다음 함수 관계도 성립한다.
(3a)
(3b)이와 같이 볼록 함수로 만들 수 있는 부등식의 성질은 다양하다.
[그림 2] 볼록 거울의 모습(출처: wikipedia.org)
거울 관점으로 보면, [그림 2]처럼 아래에서 볼 때 볼록한 거울로 보이는 함수가 바로 볼록 함수이다. 즉, 아래로 볼록(convex downward)한 모양이 볼록 함수의 특성이다. 볼록 함수를 아래가 아닌 위에서 보면 오목하므로, 볼록 함수는 위로 오목(concave upward)이기도 하다.
[그림 3] 오목 거울로 만든 태양열 조리기(출처: wikipedia.org)
아래로 볼록과 위로 오목은 약간 헷갈릴 수 있는 개념이지만, 관찰자가 있는 위치가 아래인지 위인지로 구분하면 수월하게 이해된다. 관찰자가 아래 있을 때 생긴 모양이 [그림 2]와 같은 볼록 거울이면 아래로 볼록이고, [그림 3]처럼 오목 거울로 보이면 아래로 오목(concave downward)이다. 마찬가지로 위에서 관찰할 때 형태가 볼록하면 위로 볼록(convex upward), 오목하면 위로 오목이다. 따라서 [그림 1]에 보인 볼록 함수는 관찰자를 아래에 두고 본 모양이 볼록한 경우이다.
어떤 함수가 볼록 함수인지 확인할 때는 정의역의 임의 위치에서 다음과 같은 미분의 대소 관계를 봐도 된다[1]. 아래 부등식을 만족하는 함수는 항상 아래로 볼록하며, 그 역도 성립한다.
[미분과 볼록 함수] [1]
(4)여기서 $x, y \in \operatorname{dom}(f)$, $f'(x)$는 $f(x)$의 미분(differentiation)이다.
[증명]
먼저 식 (1)을 변형해서 식 (4)의 모양으로 만든다.
(5)식 (5)의 $t$를 0으로 보내는 극한을 적용해서 식 (4)를 최종적으로 얻는다. 반대로 식 (4)는 다시 볼록 함수의 조건이라는 증명을 진행한다. 새로운 변수를 $w$ = $ty+(1-t)x$로 둔다. 변수 $w$에 대해 식 (4)를 적용한다.
(6a)
(6b)______________________________
미분을 한 번 더 적용한 2계 미분은 볼록 함수의 겉보기 조건을 더 간략화한다. 곡선의 형태만 봐도 2계 미분이 항상 0보다 크거나 같은 함수는 당연히 볼록하고 그 역도 쉽게 성립한다.
[2계 미분과 볼록 함수] [1]
(7)여기서 $f''(x)$는 $f(x)$의 2계 미분이다.
[증명]
볼록 함수는 식 (4)가 성립하므로, $x,y$를 바꾼 식을 더해서 미분의 대소 관계를 새로 만든다.
(8)
(9)여기서 $w$는 식 (9)의 첫째식을 만족하는 $x, y$ 사이의 적당한 값이다.
______________________________
[그림 4] 오목 함수의 정의(출처: wikipedia.org)
[그림 1]에 나온 볼록 함수를 뒤집으면 [그림 4]에 그린 오목 함수(concave function)가 된다. 오목 함수는 두 점을 이은 직선보다 항상 위에 있으며, 아래에서 볼 때 오목 혹은 아래로 오목하다.
(10)식 (10)을 등호 없이 쓴 때는 엄격 오목(strictly concave)으로 부른다. 오목 함수 $f(x)$의 부호를 바꾼 $-f(x)$는 식 (1)에 의해 볼록 함수가 된다. 이로 인해 볼록 함수의 성질에서 부호를 반대로 쓰면 오목 함수의 결과가 그대로 나온다.
[그림 5] 3차 함수의 볼록 및 오목 구간(출처: wikipedia.org)
볼록과 오목 함수의 변화를 예시적으로 보려고 [그림 5]를 제안한다. 3차 함수 $f(x)$ = $x^3 - 6x^2 + 9x -4$는 구간에 따라 볼록이나 오목 함수가 된다. 식 (7)에 따라 엄격 볼록 구간에서는 기울기의 변화율인 2계 미분이 항상 0보다 크고, 엄격 오목 구간에서는 이 2계 미분이 언제나 0보다 작다. 아니면 식 (1)을 써서 볼록이나 오목 구간에 두 점을 잡고 직선을 그어서 대소를 비교해도 좋다.
(a) 볼록 집합
(b) 비볼록 집합
[그림 6] 볼록과 비볼록의 구별(출처: wikipedia.org)
볼록 함수를 다차원으로 확대한 결과는 볼록 집합(convex set)으로 칭한다. 집합 내부에 있는 두 점을 이어서 만든 선분이 항상 이 집합에 속하면 볼록 집합이 된다. 예를 들어서 [그림 6(a)]는 어떤 두점을 뽑더라도 선분이 항상 이 집합 안에 들어간다. 반면 [그림 6(b)]처럼 점 $X, Y$를 선택해서 그린 선분은 집합 속에 있지 않는 부분이 생겨서 볼록이 아닌 비볼록 집합(non-convex set)으로 간주한다. 볼록 집합의 둘레 혹은 경계는 말 그대로 볼록해서 볼록 곡선(convex curve)으로 이름 붙인다. 벡터 공간 관점에서는 더 쉽게 이해 가능하다. $n$차원 좌표 $\mathbb{R}^n$의 부분 집합을 $\Omega$로 표시할 때, $\Omega$가 볼록 집합이 되는 조건은 다음과 같다.
(11)여기서 $\bar v_1, \bar v_2$는 $\Omega$에서 임의로 선택한 원소, $0 \le t \le 1$이다. 볼록 집합의 수학적 정의는 기하학적 직관에 기반한다. [그림 6(a)]처럼 임의로 선택한 점 $X, Y$의 선분을 확장해 자르면, 튀어나온 볼록한 부분이 두 동강 나고 절단면은 구멍이 없는 평면이 된다. 반면 오목한 영역이 있는 비볼록 집합은 잘린 단면에 [그림 6(b)]와 같은 구멍이 꼭 생긴다. 이를 수학적으로 정리한 개념이 선분 그리기이다. 그은 선분이 볼록 집합에 속하는 성질은 자른 선분에 끊김이 없는 결과와 서로 등가이다.
[그림 7] 볼록 껍질의 예시(출처: wikipedia.org)
특정 조건이나 모양을 만족하는 가장 작은 볼록 집합은 볼록 껍질(convex hull)로 정의한다. [그림 7]은 모든 검정점을 포함하는 파란색으로 표시한 볼록 껍질을 보여준다. 10개의 검정점을 가지는 볼록 집합은 원하는 대로 만들 수 있지만, 최소로 작은 볼록 집합은 파란색 집합이 유일하다. 이 최소 집합이 바로 검정점의 볼록 껍질이다.
[그림 8] 3점으로 만든 볼록 결합의 궤적(출처: wikipedia.org)
식 (11)을 임의의 벡터 개수로 확장해서 제한 조건을 가진 선형 결합(linear combination)을 만든 경우는 볼록 집합을 생성하는 볼록 결합(convex combination)이 된다.
(12)여기서 볼록 결합의 계수는 $\alpha_i \ge 0$, $\alpha_1 + \alpha_2 + \cdots + \alpha_n$ = $1$로 제한된다. [그림 8]처럼 점이 3개인 볼록 결합은 잘 알려진 무게 중심 좌표계(barycentric coordinate system)를 구성한다. 볼록 결합이 만드는 벡터 집합의 특성을 알기 위해 식 (12)를 약간 변형한다.
(13)여기서 $\alpha_1$ = $1-\alpha_2-\alpha_3 - \cdots - \alpha_n$이다. 벡터 $\bar v$는 $\bar v_1$에서 시작해서 각 점 $\bar v_i$를 향하는 방향으로 벡터가 더해진 결과이다. 또한 $\alpha_i + \alpha_j$ = $1$인 조건은 $\bar v_i, \bar v_j$를 잇는 선분을 만든다. 그래서 결합된 결과의 궤적은 모든 점 $\bar v_i$가 만드는 볼록 다각형(convex polygon)과 같아진다. 볼록 집합처럼 볼록 다각형은 내부의 두 점을 이은 선분이 다각형 바깥을 나가지 않는 도형이다. 그래서 볼록 결합은 여러 점으로 볼록 집합을 만드는 수월한 방식이다. 특히 볼록 결합은 모든 점을 포함하면서 가장 작은 영역을 가진 볼록 집합이므로 볼록 결합은 볼록 껍질이다. 예를 들어, [그림 8]은 3점을 이용해서 파란색 삼각형을 만든 결과를 보여준다. 여기서 $P$는 볼록 결합의 계수가 제한 조건을 만족해서 내부점이 되고, $Q$는 제한 조건이 맞지 않아 외부점이다. 또한 점 $\bar x_1, \bar x_2, \bar x_3$의 볼록 결합은 이 점을 모두 포함하는 가장 작은 삼각형이며 볼록 껍질이 된다.
볼록 함수의 다차원 확장에는 매개변수 $t$가 중요하다. 만약 $g(t)$ = $f [\bar v_2 + t (\bar v_1 - \bar v_2)]$로 둔다면, $g(t)$는 다변수가 아닌 1변수로 처리된다. 그래서 1계와 2계 미분의 성질이 $g(t)$에도 그대로 적용된다.[다차원 평균값의 정리는 어려우므로, 식 (9)처럼 어떤 $t'$에서 평균값의 정리가 만족된다고 처리한다.] 다만 미분 자체는 약간 바뀐다. 이 변경에는 다변수 테일러 급수(multivariate Taylor series)의 결과를 똑같이 활용한다. 예시로써 $dg(t)/dt$는 완전 미분(exact differential)에 따라 구배(gradient) 연산자로 대체된다.
(14)여기서 $\Delta \bar x$ = $\bar v_1 - \bar v_2$, $x_i$는 벡터의 $i$번 성분이다. 함수 $g(t)$의 2계 미분은 더 복잡해져서 헤세 행렬(Hessian matrix) ${\bf H}_f$가 필요하다. 구배와 헤세 행렬을 써서 다차원 함수의 테일러 급수를 편하게 근사할 수 있다.
(15)식 (15)를 기반으로 종합해서 식 (1), (4), (7)을 다차원으로 일반화한다.
(16)여기서 ${\bf A} \succeq 0$은 $\bf A$가 양의 준정부호 행렬(positive semidefinite matrix)이란 뜻이다. 양의 준정부호 행렬은 식 (15)의 마지막 항과 같은 2차 형식(quadratic form)이 항상 0보다 크거나 같기 때문에 식 (7)의 멋드러진 확장이다.
[그림 9] 상부 그래프와 볼록 함수(출처: wikipedia.org)
새로운 개념인 볼록 집합을 이용해서 다차원의 볼록 함수를 보기 좋게 규정한다. 정의역은 벡터(vector), 치역은 실수로 생각해서, 함수 $f(\bar v)$를 선형 범함수(linear functional)로 간주한다. 여기서 $\bar v$는 $n$차원 벡터이며 $\bar v \in \mathbb{R}^n$을 만족한다. 이 선형 범함수 $f$가 볼록 함수가 되는 조건은 $f$의 상부 그래프(epigraph or supergraph) $\operatorname{epi}(f)$가 볼록 집합인 성질과 등가이다. 상부 그래프는 특별한 의미보다 [그림 9]처럼 특정 그래프의 위쪽에 있는 모든 그래프를 뜻한다. [그림 9]에서 파란색 그래프의 상부에 위치한 녹색 영역 전체가 바로 파란색의 상부 그래프이다.
[다차원 볼록 함수와 상부 그래프]
(17)여기서 $\bar v_1, \bar v_2 \in \mathbb{R}^n$, $0 \le t \le 1$, $\operatorname{epi}(f)$ = $\{(\bar v, y): f(\bar v) \le y \}$, $\Omega$는 $n+1$차원의 볼록 집합이다.
[증명]
다차원 함수 $f$를 매개변수 $t$에 대한 함수 $g(t)$ = $f[\bar v_2 + t (\bar v_1 - \bar v_2)]$로 생각한다. 식 (17)의 왼쪽 식에 따라 함수 $g(t)$는 볼록해서 [그림 1]과 같은 모양을 가지며, 시작점과 끝점의 함수값은 $g(t)$ $\le$ $tg(1) + (1-t) g(0)$을 만족한다. 그러면 모든 $(t, g(t))$가 만드는 그래프의 상부 그래프는 [그림 9]처럼 녹색 영역이며, 여기서 선택한 임의 두 점의 모든 선분은 다시 녹색 영역에 속한다. 따라서 이 녹색 영역은 식 (11)에 따른 볼록 집합이 되어서 식 (17)의 오른쪽 식이 성립한다. 여기서 각 $t$에 벡터 합 $t \bar v_1 + (1-t) \bar v_2$가 대응된다.
역으로 함수값을 $y_1$ = $f(\bar v_1)$, $y_2$ = $f(\bar v_2)$로 두면, $\mathbb{R}^n \times \mathbb{R}$인 다차원 공간에서 두 점 $(\bar v_1, y_1), (\bar v_2, y_2)$를 지나는 직선은 볼록 집합의 정의에 따라 모두 $C$에 속한다. 이때 매개변수 $t$에 따라 변하는 상부 그래프에 위치한 함수값은 $t y_1 + (1-t) y_2$가 된다. 이 함수값은 상부 그래프에 속하므로, 이 값의 아래에 위치한 $f[t \bar v_1 + (1-t) \bar v_2]$보다 항상 크거나 같다.
______________________________
함수가 볼록한 성질이 이렇게까지 심도 있게 고민하고 분석할 필요가 있을까? 우리의 우려를 녹여내는 놀라운 기법이 볼록 함수와 볼록 집합에 뿌리를 두고 있다. 바로 아는 사람들은 자주 활용한다는 볼록 최적화(convex optimization)이다. 볼록 최적화는 비용 함수(cost function)가 볼록 함수인 경우에 언제나 전역해(global solution)를 구할 수 있는 수학적으로 검증된 기법이다.
[최소해의 유일성(uniqueness of minimum solution)] [1]
볼록 최적화 문제 $\min_{\bar u} f(\bar u)$의 비용 함수 $f(\bar u)$가 엄격 볼록 함수인 경우에 최소해는 유일하다.
[증명]
일단 최소해가 $\bar v_1, \bar v_2$로 2개라고 가정한다. 그러면 최소해의 정의에 의해 $f(\bar v_1)$ = $f(\bar v_2)$ $\le$ $f(\bar u)$, $\forall \bar u$가 성립한다. 여기서 $\bar u \in \Omega$ $\subseteq$ $\mathbb{R}^n$, $\bar v_1, \bar v_2 \in \Omega$, $\Omega$는 볼록 집합이다. 벡터 $\bar u$는 우리가 선택할 수 있으므로, $\bar u$ = $(\bar v_1 + \bar v_2) \mathbin{/} 2$로 두고 엄격 볼록 함수(strictly convex function)에 적용하려 등호를 없앤 식 (2)에 대입한다.
(18)______________________________
[볼록 최적화의 최적 방향(optimal direction)] [1]
볼록 최적화 문제 $\min_{\bar u} f(\bar u)$에서 $f(\bar u)$가 볼록 함수라면, 최적해 $\bar v_\text{opt}$를 찾는 최적 방향은 다음처럼 선택한다.
(19a)
(19b)여기서 $\Omega$는 볼록 집합, $\bar v_i$는 $i$번 탐색한 후의 $\bar v$, $k$는 $\bar v_i$가 $\Omega$에 속하도록 적절히 선택한 양의 실수이다.
[증명]
어떤 벡터 $\bar v$가 식 (19)를 만족하면, 식 (16)의 둘째식에 의해 $f(\bar v)$가 작아질 수 있다.
(20)그래서 함수값이 커지는 방향인 $\bar \nabla f$의 반대로 움직이도록 $\bar v$를 선택한다.
다른 관점으로 $f(\bar v)$가 줄어드는 길은 항상 식 (19a)인가? 이에 대한 의문을 해결하도록 어떤 $\bar w$에서는 $\bar \nabla f(\bar v) \cdot (\bar w - \bar v)$ $<$ $0$이 최적 방향이라고 가정한다. 미분을 쉽게 하도록 $g(t)$ = $f[\bar v + t (\bar w - \bar v)]$로 둔다. 식 (14)에 의해 $g'(0)$ = $\bar \nabla f(\bar v) \cdot (\bar w - \bar v)$ $<$ $0$이다. 이에 따라 $t$ = $0$ 근방에서 기울기가 음수이므로, 아주 작은 양의 $\tau$에 대해 $g(\tau)$ $<$ $g(0)$이 성립한다. 이 관계를 함수 $f$ 관점으로 쓰면 $f[\bar v + \tau (\bar w - \bar v)]$ $<$ $f(\bar v)$이다. 이 결과는 $f(\bar v)$가 주변보다 작은 값이라는 가정에 위배되기 때문에, $\bar \nabla f(\bar v) \cdot (\bar w - \bar v)$ $<$ $0$은 최적 방향일 수 없다.
______________________________
식 (19b)는 볼록 최적화로 문제를 푸는 중요 절차이다. 임의로 $\bar u$ = $\bar v_0$를 선택하고, $\bar v_0$ 주변을 미분해서 $\bar f (\bar v_0)$을 구해 새로운 $\bar v_1$을 얻는다. 이 절차는 계속 최적 방향으로 진행되므로 결국은 비용 함수가 최소가 되는 해를 찾게 된다. 이 비용 함수가 엄격 볼록 함수일 때는 우리가 찾은 최소해가 유일하다. 따라서 볼록 최적화는 언제나 전역해를 찾을 수 있는 획기적 기법이다. 하지만 엄청난 결과에는 어마어마한 원인이 있다. 바로 볼록 함수 조건이다. 비용 함수가 볼록 함수란 증명이 없다면 볼록 최적화는 적용될 수 없으므로, 볼록 최적화는 관심 문제의 볼록함(convexity)을 확인하면서 조심해 써야 한다.
[참고문헌]
[1] A. A. Ahmadi, "Characterizations of convex functions, strict and strong convexity, optimality conditions for convex problems," Convex and Conic Optimization, Princeton University, USA, 2024. (방문일 2024-05-05)
[다음 읽을거리]
댓글 없음 :
댓글 쓰기
욕설이나 스팸글은 삭제될 수 있습니다. [전파거북이]는 선플운동의 아름다운 인터넷을 지지합니다.