1. 경사하강법

경사하강접은 임의의 점에서 시작해 함수의 기울기가 가장 급격한 방향으로 계속해서 이동해 함수의 정류점에 도착하는 방법입니다. 이를 최적화 한다고 합니다. 간단하게 다음과 같이 구현할 수 있습니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

C0 = np.array(0.0)
C1 = np.array((0.0, 0.0),)
C2 = np.array(((1.0,0.0),(0.0,1.0),))
step_size = 0.3

def f(x):
	return C0 + C1 @ x.T + x @ C2 @ x.T

def gradient_f(x):
	return C1 + x @ ( C2 + C2.T )

p = np.array((9.0, 3.0,))
path = [(*p, f(p),)]
for i in range(30):
	grad = gradient_f(p)
	step_vec = -grad / np.linalg.norm(grad, ord=2)
	step = step_size * step_vec
	p += step
	path += [(*p, f(p),)]

show(path)

2. 제약이 있을 경우 경사하강법

$$ \begin{array}{ll} \tag{1} & \min_{x} f(x)\label{0} \newline & s.t. \quad g(x) \ge 0 \end{array} $$

위와 같이 특정 범위안에서 $f$를 최적화할 때, 범위를 제약하는 함수를 조건식($g$)이라고 합니다. 범위의 제약이 있을 때 일반적인 경사하강법과 다른 점은 조건식이 등식으로 만족되는 지점에서($g(x)=0$) 이동에 제약이 있다는 점 입니다. 이를 조건식이 활성화 되었다고 합니다. $x$를 조건식이 활성화된 점이라고 합시다. $x$에서의 이동 방향의 단위벡터를 $v_x$라고 합시다. 앞으로 나오는 목적함수의 기울기 ($\nabla f$), 조건식의 기울기 ($\nabla g$)는 이 점을 기준으로 합니다.

$x$에서 이동에 제약이 있지만 기본 원리는 조건식이 없을 때와 같습니다. 이동 가능한 방향중 가장 기울기가 급격한 방향으로 움직입니다. 임의의 단위벡터를 $v$라고 합시다. $v$ 방향으로 이동 했을 때 목적함수 $f$의 변화량은 $\nabla f^T v$입니다. 따라서 $\nabla f^T vx$를 최대화 혹은 최소화하는 방향으로 움직입니다. 문제(1)은 최소화 문제이므로 가장 작은 방향으로 이동합니다.

우선 이동방향이 어떻게 제약되는지 알아야 합니다. $v$ 방향으로 이동하면 $g(x)$의 변화량은 $\nabla g(x)^T v$입니다. $\nabla g(x)^T v$이 음수면 방향 $v$로 이동시 조건식이 감소합니다. 조건식이 0보다 커야하므로 해당 방향을 제약됩니다. 따라서 $v_x$는 $\nabla g(x)^T v$이 0 이상인 방향입니다.

따라서 $v_x$는 (2)를 최적화합니다.

$$ \begin{array}{l} \tag{ 2 } & \min_{v} \nabla f^T v \\ & s.t. \quad \|v\| = 1 \quad \nabla g^T v \ge 0 \end{array} $$

행렬 $M$의 컬럼 $e_0$, $e_1$, $ e_2$ … 가 $g^\bot$의 orthonormal basis라고 합시다. $M$의 컬럼과 조건식의 기울기를 선형 조합해 $v$를 표현합니다(3). $\lambda$는 스칼라이며 $u$ 벡터입니다. $\lambda$가 0 이상일 때 만, $\nabla g(x)^T v$이 0 이상입니다.

$$ \begin{array}{l} \tag{ 3 } v = \lambda \frac{\nabla g}{\|\nabla g\|} + Mu\newline \lambda^2 + \|u\|^2 = 1 \quad \lambda \ge 0 \end{array} $$

따라서 (2)의 $v$를 $\lambda$와 $u$로 치환하고 조건식을 간단히 해줍니다(4).

$$ \begin{array}{l} \tag{ 4 } \min_{\lambda, u} \lambda \frac{1}{\|\nabla g\|} \nabla f^T \nabla g +\nabla f Mu \\ \lambda^2 + \|u\|^2 = 1 \quad \lambda \ge 0 \end{array} $$

(4)를 최소화 하는 $u$, $\lambda$를 통해 (2)를 최소화 하는 $v$를 구합시다. $\nabla f^T \nabla g$이 음수면 (2)를 최소화 하는 $v$는 $-\hat{\nabla f}$ 입니다. 따라서 $\nabla f^T \nabla g$를 양수일 때만 고려합니다. 따라서 $\lambda$가 0일 때 (4)는 최소화 됩니다. 따라서 (4)는 (5)가 됩니다.

$$ \begin{array}{l} \tag{ 5 } \min_{u} \nabla f^T Mu \\ \|u\| = 1 \end{array} $$

(5)를 최소화 하는 $u$는 쉽게 구할 수 있습니다.

$$ \begin{array}{l} \tag{ 6 } u = - \frac{1}{\| \nabla f \|} M^T \nabla f \end{array} $$

따라서 (2)를 최소화 하는 $v$는 다음과 같습니다.

$$ \begin{array}{l} \tag{ 7 } v = Mu = - \frac{1}{\|\nabla f\|} M M^T \nabla f \end{array} $$

유도과정에서 나온 조건을 고려하면 $v_x$는 다음과 같습니다(8). 최대화 문제였다면 (8-2) 와 같습니다.

$$ \begin{array}{l} \tag{ 8 } v_x = \begin{cases} -\frac{1}{\|\nabla f\|} M M^T \nabla f & (\text{if } -\nabla f \cdot \nabla g < 0)\\ -\hat{\nabla f} & (else) \end{cases} \end{array} $$ $$ \begin{array}{l} \tag{ 8-2 } v_x = \begin{cases} \frac{1}{\|\nabla f\|} M M^T \nabla f & (\text{if } \nabla f \cdot \nabla g < 0)\\ \hat{\nabla f} & (else) \end{cases} \end{array} $$

3. 예시

Linear 함수를 조건식으로 최소점을 가지는 Convex 함수를 최소화 해봅시다. (1)의 최적화문제의 $f$와 $g$를 다음과 같이 정의합니다. f가 최소점을 가지기 위해 $C_2$는 positive definite matrix입니다.

$$ \begin{array}{l} \tag{9} f(x) = C_0 + x^T C_1 + x^T C_2 x \newline g(x) = B + x^T W \end{array} $$

이동에 제약이 없을 경우 경사하강법을 사용해 이동합니다. 제약이 있을 경우 $g$에 의해 제약된 방향중 가장 급격한 방향으로 이동합니다. 이 방향은 norm_gradient_f_subject_to_g() 함수를 통해 구합니다. 이동 중 조건식을 만족하지 않는 영역에 들어가면 조건식을 만족하는 가장 가까운 위치로 이동합니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

W = np.array((1.0, 1.0,))
B = np.array((-5.0))
precision = 0.0001

w_norm = np.linalg.norm(W, ord=2)
w = W / w_norm
b = B / w_norm
_, s, v_inv = np.linalg.svd(np.matrix(W))
m = np.array(v_inv[len(s):]) # m is orthogonal basis
mT_m = m.T @ m

def norm_gradient_f_subject_to_g(grad):
	if grad @ w.T <= 0: return grad /np.linalg.norm(grad, ord=2)
	step_vec = grad @ mT_m
	return step_vec / np.linalg.norm(step_vec, ord=2)

def distance_from_g(p):
	return p @ w.T + b, w
	

p = np.array((9.0, 3.0,))
p_dis, h = distance_from_g(p)
if p_dis < -precision:
	raise ValueError('condition is not satisfied')

path = [(*p, f(p),)]
for i in range(30):
	
	grad = gradient_f(p)
	if p_dis < precision:
		step_vec = -norm_gradient_f_subject_to_g(grad)
	else:
		step_vec = -grad / np.linalg.norm(grad, ord=2)
	step = step_size * step_vec
	p += step
	
	p_dis, h = distance_from_g(p)
	if p_dis < -precision: 
		p -= p_dis * h
		p_dis, h = distance_from_g(p)
	path += [(*p, f(p),)]

show(path)

4. 제약이 여러개 있는 경사하강법

$$ \begin{array}{l} \tag{ 10 } \\min_x & f(x) \\ s.t. & g_i(x) \ge 0 & i=0,...,m \end{array} $$

제약이 여러개 있을 경우도 하나 있을 때와 비슷한 방법을 사용합니다. 우선 조건식에 의해 제약된 방향을 구하고 제약된 방향중 기울기가 가장 급격한 방향을 선택합니다. 활성화된 조건식이 있는 경우만 고혀하겠습니다. (10)를 예시로 설명하겠습니다. 경사하강을 하는 과정에서 임의의 점을 $x$, $x$에서 경사하강을 통한 이동방향의 단위벡터를 $v_x$라고 합시다. 목적함수의 기울기 ($\nabla f$), 조건식의 기울기 ($\nabla g$)는 이 점을 기준으로 합니다.

우선 활성화된 조건식의 기울기의 단위벡터의 집합 $A$를 정의합니다. 이를 이용해 $N$과 $M$을 정의합니다. $N$의 컬럼스페이스는 $span(A)$ 이고, $M$의 컬럼스페이스는 $A^\bot$ 입니다. 조건식이 제약하는 방향은 조건식의 기울기와 관련있기 때문에 벡터를 $M$과 $N$으로 나누어주면, 조건식에 의해 제약된 방향을 쉽게 구할 수 있습니다.

$$ \begin{array}{l} \tag{ 11 } A & = & \{ \: \frac{\nabla g_i}{\| \nabla g_i \|} \: | \: g_i(x) = 0 \: \} \\ N & = & \begin{bmatrix} A_0 | A_1 | A_2 … \end{bmatrix} \\ M & = & ( M \text{’s columns is orthonomal basis of } A^\bot ) \end{array} $$

0과 임의의 단위벡터의 집합 $V$를 정의합니다.

$$ \begin{array}{l} \tag{ 12 } V&=&\{\,0\,\} \cup \{\, N\lambda + M u \,\mid\, \|\lambda\|^2 + \|u\|^2 = 1 \,\} \end{array} $$

$N$의 컬럼은 조건식의 기울기의 단위벡터입니다. $V$의 원소 $v$에 대해 $i$ 번째 컬럼과 내적이 음수라면 $v$방향으로 이동시 $i$번째 조건식이 감소함을 말합니다. $V$의 원소중 이동해도 조건식을 만족하는 방향만 추출해 집합 $\bar{V}$를 정의합니다(13).

$$ \begin{array}{l} \tag{ 13 } \bar{V} & = & \{\, v \in V \,\mid\, \forall{i} \quad (N^T v)_i \ge 0 \,\}\\ & = & \{\, N\lambda + M u \,\mid\, \|\lambda\|^2 + \|u\|^2 = 1, \quad \forall{i} \quad (N^T N \lambda)_i \ge 0 \,\} \end{array} $$

$v_x$는 제약되지 않은 방향($\bar{V}$의 원소)중 목적함수의 기울기가 가장 급격한 방향이므로 $v_x$는 (14)를 최소화 합니다.

$$ \begin{array}{l} \tag{ 14 } \underset{v \in \bar{v}}{\min} \nabla f^T v \end{array} $$

$\nabla f$와 $\bar{V}$의 원소 $v$를 $N$과 $M$의 컬럼의 선형조합으로 표현합니다. $\lambda^v$, $u^v$, $\lambda^f$, $u^f$는 선형조합을 위해 사용한 벡터입니다.

$$ \begin{array}{l} \tag{ 15 } v = N\lambda^v + M u^v \quad \|\lambda^v\|^2 + \|u^v\|^2 = 1\\ \nabla f = N \lambda^f + M u^f \end{array} $$

그러면 (14)는 (16)이 됩니다.

$$ \begin{array}{l} \tag{ 16 } \underset{\lambda^v, u^v}{\min} & \{\lambda^{fT} N^T N \lambda^v + u^{fT} u^v\} \\ s.t. & \|\lambda^v\|^2 + \|u^v\|^2 = 1\\ & \forall{i} \quad (N^T N \lambda^v)_i \ge 0 \end{array} $$

$N^T N \lambda^v$를 $\lambda^*$로 바꾸어 (16)를 (17)로 바꾸어줍니다.

$$ \begin{array}{l} \tag{ 17 } \underset{\lambda^*, u^v}{\min} & \{\lambda^{fT} \lambda^* + u^{fT} u^v\} \\ s.t. & \|\lambda^*\|^2 + \|u^v\|^2 = 1, \\ & \forall{i} \quad \lambda^*_i \ge 0 \\ \end{array} $$

아시다시피 이 문제의 답은 아래와 같습니다. k는 크기조절을 위한 값으로 양수 입니다.

$$ \begin{array}{l} \tag{ 14 } u^v & = & -k u^f\\ \lambda^*_i &=& \begin{cases} 0 & \text{if } -\nabla f^T A_i \le 0 \\ -k \lambda^f_i & \text{else } \end{cases} \\ \end{array} $$