비선형 최적화에는 어떤 것들이 있을까요?

비선형 최적화에는 Gradient Descent, Gauss-Newton, Levenberg-Marquardt 방식들이 있습니다.
너무 많아서 정리하는데 시간이 걸릴 것 같습니다.

---

최적화

최적화는 결국 함수가 가장 (작은 or 큰) 값이 될 수 있도록 하는 parameter를 찾는 과정입니다.
parameter를 어떠한 방향으로 조금씩 이동시키면서 수렴하는 곳으로 찾는 과정이라 보시면 됩니다.
앞에 언급한 여러가지 방식들은 이 어떠한 방향과 조금씩(step size)를 정하는 방식이 다른 것 뿐입니다.

1차 미분기반 최적화

꼭대기로 가려면 올라가야 하고 1층으로 가려고 하면 내려가야 합니다.
그렇다면 최댓값을 찾으려면 기울기가 양수인 방향으로 가야하고 최소값을 찾으려면 기울기가 음수인 방향으로 가야합니다. 기울기는 1차 미분으로 알 수 있는데 이렇게 쉽게 생각해낸게 1차 미분 기반 최적화입니다.

$x_{k+1} = x_k - \lambda f'(x_k)$
이 수식에 따라 임의의 시작점 $x_0$부터 시작해서 $\lambda$만큼 계속 움직입니다.

1차 기반의 문제점은 극값에 가까워질수록 수렴 속도가 급격히 떨어진다는 것입니다.
step size에 따라 정확함 지점을 찾기가 엄청 어려워질 것 같기도 하고
역시 간단하게 최적화 문제점이 풀리질 않네요.
이러한 방식을 gradient descent방식이라고 하고 이러한 문제점을 해결하기 위해
여러 gradient descent방식들이 나오기도 했습니다.

• 단점 보완 기법: Line Search 기법
  1차 미분의 단점은 step size가 고정되어 있어서 극값 근처에서 수렴이 잘안된다는 점입니다.
  만약 가기 전에 함수를 좀 살펴보고 이 정도 가야겠군한다면 훨씬 더 효율적인 방법이 되겠죠.
  그렇기 때문에 line search 기법을 활용하여 step size를 정하면 단점을 보완할 수 있습니다.

2차 미분기반 최적화

$x_{k+1}=x_k - \frac{f'(x_k)}{f''(x_k)}$

이렇게 1차미분과 2차미분을 모두 사용하여 최적화를 하는 방식입니다.
이렇게 하면 step size를 2차미분을 기반으로 정하게 되고 1차 미분보다 훨씬 수렴이 잘됩니다.

하지만 이러한 방식도 문제점이 있는데 첫번째는 변곡점 근처에서 매우 불안정한 이동을 보인다는 것입니다.
변곡점에서는 f''이 너무 작아져서 step size가 너무 커져버리기 때문입니다.
두번째 문제는 이동할 방향을 결정할 때 극대와 극소를 구분하지 않는다는 것입니다.
극값으로 가기는 하는데 그것이 극대인지 극소인지 모른다는 것이죠. 그래서 initial point가 더욱 중요해지는 것 같기도 합니다. 이것을 Newton-Raphson 방식이라고 합니다.

• 단점 보완 기법: Trust Region 기법
  2차 미분기반 방식은 f''이 상수여서 step size가 상수로 나온다는 것을 가정합니다.
  하지만 모든 함수는 2차 함수가 아니기 때문에 문제가 생깁니다.
  이것을 해결하기 위해 함수를 2차 함수로 근사하면 문제가 해결될 수 있습니다.
  이 과정에서 사용하는 것이 trust region 기법입니다.
  2차 함수로 근사할 수 있는 신뢰 영역을 찾고 거기서 근사한다면 앞의 가정을 충족할 수 있게 됩니다.
  $x=x_k$일때 trust region을 $\parallel x - x_k \parallel \leq r_k$로 설정하고 2차 미분기반 최적화를 진행하게 됩니다.

Gauss-Newton 방식

Gauss-Newton 방식도 2차 미분 기반 최적화 알고리즘이라고 생각하시면 되는데 너무 유명해서 따로 정리를 한번 해보겠습니다.

2차 미분기반 최적화는 step size이 고정되지 않고 극값 근처에서는 작게 극값에서 멀리 떨어져 있으면 크게 설정되어 수렴이 잘된다는 장점이 있었습니다.

앞의 newton-raphson 법은 2차 미분을 다 해야하지만 gauss-newton은 approximation을 통해 1차 미분만으로 2차미분 기반 최적화를 할 수 있습니다.

$x_{k+1}$=$$ $x_k$-${(J^T_rJ_r)^{-1}}$$J^T_rr(x_k), k \geq 0$
이 식을 좀 더 간략히 한다면 $x_{k+1} = x_k - inv(J_r)r(x_k), k \geq 0$
이렇게 나타낼 수 있습니다. 어떻게 이런 식이 나오는걸까요?

바로 비선형 함수를 지역적으로 선형함수로 근사하여 해를 구하는 것입니다.

오차 벡터 r(p) = [$r_1(x) r_2(x) ... r_n(x)$]$^T$를 테일러 전개를 이용하여
$x_k$ 근처에서 선형 함수로 근사하면 r(x) $\simeq$ $r(x_k) + J_r(x_k)(x-x_k)$가 됩니다.

근사된 오차에 대한 제곱합은 $\parallel r(x_k)+J_r(x_k)(x-x_k)\parallel^2$이고 이것을 최소화하려고 계산하면
x =$x_k$-$(J_r(x_k)^TJ_r(x_k))^{-1}J_r(x_k)r(x_k)$ 이렇게 나옵니다.

하지만 선형 근사를 했기 때문에 완벽한 x가 아니라서 이 x를 $x_{k+1}$로 해서 iteration을 합니다.

그래서 $x_{k+1}$ = $x_k$-$(J_r(x_k)^TJ_r(x_k))^{-1}J_r(x_k)r(x_k)$ 식이 나오게 됩니다.

Levenberg-Marquardt 방식

이 방식은 1차 미분기반 최적화와 2차 미분 최적화 기법의 장점을 합친 방식입니다.

쉽게 생각하면 해로부터 멀리 떨어져 있으면 Gradient Descent 방식으로 작동하고
가까이 있으면 Gauss-Newton 방식으로 작동하는 최적화 방식입니다.

$x_{k+1} = x_k - (J^T_rJ_r+\mu_kdiag(J^T_rJ_r))^{-1}J^T_rr(p_k), k \geq0$
이 식이 Levenberg-Marquardt 방식입니다.

여기서 보면 $\mu_k$ 값이 크면 step size $\frac{1}{\mu_k}$인 gradient descent 처럼 작동하고
$\mu_k$값이 작으면 gauss-Newton 방식으로 작동하는 것을 알 수 있습니다.

iteration마다 $\mu$ 값이 바뀌기 때문에 잘 조절하면 효과적인 방식이 될 수 있습니다.
이것을 어떻게 조절하는지에 따라 다양한 Levenberg-Marquardt 방식이 있습니다.

---

결국 보면 어느 방향으로 얼마나를 조절하는 다양한 방식이 있었습니다.
뭐 gradient descent의 한계를 보완하기 위한 momentum 같은 방식도 있지만 본질에서 벗어난 것 같아서 다음에 기회가 되면 정리하도록 하겠습니다!
감사합니다.