23. 다변수 함수의 최적화 방법

1. 선형 근사
   1) 일변수에서의 선형근사는 다음과 같이 구했다.
   

   $f(x) \approx f(\alpha) + f'(\alpha)(x-\alpha)$

   2) 이를 다변수로 확장하면 아래와 같은 형식으로 나타낼 수 있다.

   $f(x,y) = f(x_{0},y_{0}) + \frac{\partial f}{\partial x}(x - x_{0}) + \frac{\partial f}{\partial y}(y - y_{0})$

   
   
2. 다변수 함수의 뉴턴법
   
   1) 일변수 함수의 뉴턴법인 $x_{n+1} = x_{n} + \frac{f(x)}{f'(x)}$ 를 다변수 미적분으로 확대한 방법론
   
   2) 이변수 누턴법에 대하여 먼저 고려해보자
   
   ${(1)}$ 함수가 두개이고, 변수도 두개인 경우를 상정하자.
   (다변수 뉴턴법은 기본적으로 변수보다 방정식의 갯수가 같거나 더 많은 상황을 가정한다)
   
   -. (선형 근사 방정식 = 0)으로 놓고 각각의 함수에 대하여 이를 정의하면(함수를 각각 g,h라고 놓자) 
   $$g(x,y) + \frac{\partial g}{\partial x}(x_{n+1}-x_{n}) + \frac{\partial g}{\partial x}(x_{n+1}-x_{n}) = 0\\ h(x,y) + \frac{\partial h}{\partial x}(x_{n+1}-x_{n}) + \frac{\partial h}{\partial x}(x_{n+1}-x_{n}) = 0$$
   
   -. 위의 식에서 $g(x,y)$, $h(x,y)$를 우변으로 이항하면
   $$-g(x,y) = \frac{\partial g}{\partial x}(x_{n+1}-x_{n}) + \frac{\partial g}{\partial x}(x_{n+1}-x_{n}) \\ -h(x,y) = \frac{\partial h}{\partial x}(x_{n+1}-x_{n}) + \frac{\partial h}{\partial x}(x_{n+1}-x_{n})$$
   ${(2)}$ 위의 식을 반복적으로 이용하면 어떤 특정한 수렴점 (x,y)를 구할 수 있다.
   
   -. (첫번째) 미분항 $\frac{\partial g}{\partial x}$, $\frac{\partial g}{\partial y}$, $\frac{\partial h}{\partial x}$, $\frac{\partial h}{\partial y}$ 를 구한다
   
   -. (두번째) 각각의 함수의 연산값 $h(x,y)$와 $g(x,y)$를 구한다(첫번째 Iteration의 경우 원점 $(x_{0}, y_{0})$를 쓴다
   
   -. (세번째) 도출한 식 $$-g(x,y) = \frac{\partial g}{\partial x}(x_{n+1}-x_{n}) + \frac{\partial g}{\partial y}(y_{n+1}-y_{n}) \\ -h(x,y) = \frac{\partial h}{\partial x}(x_{n+1}-x_{n}) + \frac{\partial h}{\partial y}(y_{n+1}-y_{n})$$의 연립방정식을 풀어 $\Delta x = x_{n+1}-x_{n}$, $\Delta y = y_{n+1}-y_{n}$을 구한다.
   
   -. (네번째) $x_{n+1} = x + \Delta x, y_{n+1} = y + \Delta y$ 를 구해 새로운 점 (x,y)를 도출한다.
   ${(3)}$ 예시로 보는 이변수 뉴턴법
   
   -. $g = x^{3} - y, h = y^{3}-x$라는 두개의 함수를 상정하자
   -. 원점 $(x_{0}, y_{0})$ = (2,1)에서 이 함수의 편미분을 수행하면 아래와 같이 나타낼 수 있다.

   $\frac{\partial g}{\partial x} = 3x^{2}|_{x = 2} = 12$	$\frac{\partial g}{\partial y} = -1$
   $\frac{\partial h}{\partial x} = -1$	$\frac{\partial h}{\partial y} = 3y^{2}|_{y = 1} = 3$

   
   -. $\left\{\begin{matrix}
   g(2,1) = 2^{3} - 1 = 7 \\ 
   h(2,1) = 1^{3} - 2 = -1
   \end{matrix}\right.$이고, 이를 이용하여 공식을 도출하면
   $$-7 = 12 \Delta x -1 \Delta y \\ 1 = -\Delta x + 3\Delta y$$
   
   -. 두 공식을 이용하여 연립방정식의 해 $\Delta x$와 $\Delta y$를 구하면
   $$\Delta x = -\frac{4}{7}\\
   \Delta y = \frac{1}{7}$$
   
   -. 이를 이용하여 다음 점 $(x_{1}, y_{1})$을 구하면
   $$x_{1} = 2 - \frac{4}{7} = \frac{10}{7}\\
   y_{1} = 1 + \frac{1}{7} = \frac{8}{7}$$ 
   
   3) 위에서 도출한 방법론을 다차원으로 확장하면
   
   ${(1)}$ (첫번째) n개의 함수에 대하여 m개 변수에 대한 미분을 구하는 야코비 행렬을 구한다.

   $$J(X) = \frac{\partial f}{\partial x} = \begin{bmatrix} \frac{\partial f_{1}}{\partial x_{1}} & \frac{\partial f_{1}}{\partial x_{2}} & ... & \frac{\partial f_{1}}{\partial x_{m}}\\  \frac{\partial f_{2}}{\partial x_{1}} & \frac{\partial f_{2}}{\partial x_{2}} & ... &  \frac{\partial f_{2}}{\partial x_{m}}\\  ... & ... & ... & ... \\  \frac{\partial f_{n}}{\partial x_{1}} & \frac{\partial f_{n}}{\partial x_{2}}  & ...  & \frac{\partial f_{n}}{\partial x_{m}}  \end{bmatrix}$$

   
   ${(2)}$ (두 번째와 세번째의 통합) 다음을 만족하는 $[\Delta x_{1}, ..., \Delta x_{m}]$인 벡터 P를 구한다
   $$J(X)P = F(X)$$
   
   -. F(X)를 구하는 것은 이변수 뉴턴법에서 (두번째)에 해당하는 [h(x,y), g(x,y)]를 구하는것과 동일하고, P를 구한다는것은 (세번째)에 해당하는 연립방정식의 해를 구하는것과 동일한 방법이다.
   
   -. P를 구하는 방법은 여러가지가 있는데, 선형대수학에서는 최소 제곱법이라 하여 J(X)와 F(X)간 오차를 최소화하는 부분공간 P를 구하는 방법론이 있다.
   
   -. 최소 제곱법을 이용하면, P를 구하는 식은 다음과 같이 나타낼 수 있다.
   $$ P = (J^{T}J)^{-1}J^{T}F(x) $$
   
   ${(3)}$ (네번째) 다음을 이용해 업데이트된 변수 벡터 X_{n+1}을 구한다.
   $$X_{n+1} = X_{n} - P = X_{n} -(J^{T}J)^{-1}J^{T}F(x)$$
   
   -. 이 때,$(J^{T}J)^{-1}$ 라는 J행렬 대한 이차형식(Quadratic Form)의 역행렬을 구하게 된다.
   
   -. J의 행렬식 $det(J)$이 0에 가까울수록 이 역행렬의 분산 $Var(J)$을 과도하게 커지게 하고, 0이 되는 순간 역행렬을 구할수 없게 되는 문제가 발생할 수 있다.
   
   -. 이런 점이 뉴턴법을 직접적으로 활용하기 어렵게 만드는 제약점으로 작용한다.