논문

하루에도 수만개의 글자를 읽고 있습니다. 하루에도 수백장의 종이를 들춰 읽습니다.
이것은 그 읽기에 대한 일기입니다.

Conjugate Gradient Method

http://www.gantovnik.com/vg/soft/python/powells.pdf

n 차원 공간에서의 함수 $ f(x) $를 최소화시키는 문제를 생각하여 보자. 함수를 정확히 알 수 없기 때문에 다음과 같이 진행될 것이다.

  1. 공간상의 하나의 지점 $ x_0 $를 선택한다.
  2. $ i = 1, 2, 3, ... $으로 반복하는 동안,
    벡터 $ v_i $를 선택하고 지점 $x_{i-1}$ 으로부터 벡터 방향으로 $f(x)$를 최소화한 뒤, 그 최소지점을 $x_i$라 한다.
    $ |x_i - x_{i-1} | \lt \epsilon $ 이라면 반복을 종료한다.

2에서 벡터 방향으로의 최소화는 1차원적인 최소화 방법 중 어느 것이라도 사용할 수 있으나, 중요한 점은 어떻게 벡터 $v_i$를 정할 것인지다.

Conjugate Directions

함수 $f(x)$가 quadratic 이라고 가정하여보자.

$$f(x) = c - b^Tx + \frac{1}{2} x^TAx$$

그렇다면 이 함수의 편미분 값으로 이루어진 그래디언트 공간은 $ \nabla f = -b + Ax $ 으로 나타낼 수 있다.

이 그래디언트 공간에서 지점 $x_0$에서 벡터 $u$ 방향으로 이동하는 것을 생각해보면, $ x=x_0 + su $ 와 같이 표현된다. $s$는 벡터 방향으로 얼마나 이동할지를 나타내는 거리 값이다. 이 식을 위의 그래디언트 공간을 나타내는 식에 대입하여 보자.

$$\nabla f|_{x_0 + su} = -b + A(x_0 + su) = \nabla f|_{x_0} + sAu$$

따라서 함수 공간에서의 $ su $ 만큼의 이동은 그래디언트 공간에서 $sAu$만큼 이동하는 것과 대응된다. 그리고 어느 한 벡터 $v$가 u에 직교한다면 $ v^TAu = 0 $이고 이를 conjugate한다고 표현한다. 아이디어는 여기서 나오는데, 만약 이전에 최소화했던 $v$방향에 conjugate하는 $u$방향으로 움직인다면, 이전 방향인 $v$방향으로의 최소화 결과를 엉망으로 망치지 않고 이동할 수 있을 것이다.

Conjugate 그래디언트를 만드는 방법에 따라 $f(x)$에 대해서만 만드는 zero-order 방법이나, $f(x)$$\nabla f$모두에 대해서 계산하는 first-order방법 등 여러가지 방법이 존재한다. First-order 방법의 계산이 더 효과적이나 $ \nabla f $를 계산하는 과정에서 어려움이 있을 수 있다.

보통 함수는 quadratic인 경우가 아니기 때문에 Taylor series를 이용하여 근사식을 만들어 사용하며, 때문에 구해진 최소지점은 지역적인 최소지점이 될 것이다.

Powell’s Method

Powell의 방법은 zero-order 방법으로 $f(x)$의 값만 알 수 있으면 된다.

  1. 시작 지점 $x_0$를 정한다.
  2. 시작 벡터 $v_i, i=1, 2,...,n$를 정한다. 보통 $v_i = e_i$이며, $e_i$는 공간 상 각 축의 유닛벡터이다.
  3. 각 축에 대하여 ($i = 1, 2, ..., n$) 아래 방법으로 각각 최소화를 수행한다.
    지점 $x_{i-1}$에서 함수 $f(x)$$v_i$방향으로 최소화한다. 그리고 최소지점을 $x_i$라 한다.
  4. 최소화가 끝나면, $v_{n+1} \leftarrow x_0 - x_n $를 계산한 뒤, 다시 $x_0$지점에서 $v_{n+1}$방향으로 최소화를 수행한다. 이 후 최소 지점을 $x_{n+1}$으로 지정한다.
    $ |x_i - x_{i-1} | \lt \epsilon $ 이라면 반복을 종료하고 그렇지 않으면,
    $i = 1, 2, ..., n$에 대하여 $v_i \leftarrow v_{i+1} $로 갱신한다.
  5. 3,4 과정을 반복한다.

Add a Comment Trackback