[수치해석] Ch14. Grandient Methods - Multidimensional

복습하기 위해 학부 수업 내용을 필기한 내용입니다.
이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다.

2022.12.10 - [컴퓨터공학/수치해석] - [수치해석] Ch14. Directed Methods - Multidimensional

 

Gradient method은 최적을 찾기 위한 효율적인 algorithm을 생성하기 위해 derivative 정보를 명시적으로 사용한다.

▶Gradients and Hessians

첫 번째 도함수가 0이 되면 최적의 값에 도달한 것이다.

두 번째 도함수의 부호는 양수면 최소, 음수면 최대에 도달한 것이다.

방향 gradient는 x축과 각도 세타를 형성하는 축 h를 따라 정의된다.

즉, 갈 수 있는 공간 360도 전체 중에서, 가장 경사가 급한 쪽으로 간다. (특히 심한 곳으로)

where the partial derivatives are evaluated at x = a, y = b.

 x = a 및 y = b 지점에서 f(x, y)의 방향 도함수를 나타낸다.

 

ex. f(x, y) = x * y^2, point(2, 2)

 

del_f = y^2 * i + 2xy * j = 4i + 8j

y^2 = 4

2 * x * y = 8

theta = tan^-1(8/4) = 1.107 radians( = 63.4도)

 가장 가파른 상승 방향은 좌표(2, 2)에서 등고선과 수직 또는 직교한다.

 

 

the Hessian

hessian행렬은 다변수 함수가 극값을 가질 때, 그것이 극대인지, 극소인지, saddle인지 판정할 때 사용한다.

공식 암기해야 한다.

미분 불가능한 경우

▶Steepest Ascent Method

경사 방향을 따라 짧은 거리를 걸을 수 있다.

그러고 나서 멈춰서, 경사를 재평가하고 또 다른 짧은 거리를 걸을 수 있다.

그 과정을 반복함으로써 결국 언덕 꼭대기에 도달할 것이다.

 

매우 실용적이지 않다.

특히, 경사도의 지속적인 재평가는 계산적으로 요구될 수 있다.

f(x, y)가 증가를 멈출 때까지, 이동 방향을 따라 수평이 될 때까지 처음 기울기를 따라 이동한다.

멈추게 되면, ∇f가 재평가되고 새로운 방향의 시작점이 된다.

정상에 도달할 때까지 반복된다.

이 접근법은 steepest ascent method이다.

 

ex.

x0 = 1, y0 = 2

∇f = 3i + 4j

 

x = 1 + 3h

y = 2 + 4h

728x90

ex. gradient direction

f(x, y) = 2xy + 2x - x^2 - 2y^2

x = -1, y = 1

 

x' -> 2y + 2 - 2x = 2 + 2 + 2 = 6

y' -> 2x - 4y = -2 - 4 = -6

 

∇f = 6i - 6j

 

f(x0 + 6h, y0 - 6h) = f(-1 + 6h, 1 - 6h)

= 2(-1 + 6h)(1 - 6h) + 2(-1 + 6h) - (-1 + 6h)^2 - 2(1 - 6h)^2

 

g(h) = -180h^2 + 72h - 7 

g'(h) = 0 -> h = 0.2

 

x = -1 + 6*0.2 = 0.2

y = 1 - 6*0.2 = -0.2

grandient direction 하면 여러 번 거쳐서 최적 값을 구할 수 있다.

(0.2, -0.2)

x' -> 2y + 2  - 2x = -0.4 + 2 + -0.4 = 1.2

y' -> 2x - 4y = 0.4 +0.8 = 1.2

 

∇f = 1.2i + 1.2j

 

f(x1 + 1.2h, y1 + 1.2h) = f(0.2 + 1.2h, -0.2 + 1.2h)

 

g(h) = -1.44h^2 + 2.88h + 0.2

g'(h) = 0 = -2.88h + 2.88

h = 1

 

x = 0.2 + 1.2 = 1.4

y = -0.2 + 1.2 = 1

...

이런 식으로 반복한다.

 

 

ex. optimal steepest ascent

x' -> 2y + 2 - 2x = 0

y' -> 2x - 4y = 0

=> x = 2, y = 1

 

x'' -> -2

y'' -> -4

x'y' -> 2

 

|H| = -2*-4 - 2^2 = 4

|H| > 0 -> min, max

x'' -> -2 < 0 -> f(2, 1) is a maximum

 

optimal steepest ascent 하면 한 번에 optimal을 구할 수 있다.