Univariate optimization - Lagrange polynomial Interpolation 설명

이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다.

Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다.

이전 글에서 Newton's method 에서 2차 근사함수를 통해서 local mimimum 을 탐색하는 방법을 언급했습니다. 이와 유사한 방법으로 Lagrange polynomial 을 통해서 minimum 을 탐색할 수 있습니다.

Lagrange polynomial

출처: https://en.wikipedia.org/wiki/Lagrange_polynomial

Lagrange polynomial 은 주어진 서로 다른 지점 n 개를 포함하는 가장 낮은 차수의 함수를 찾는 interpolation(보간법) 입니다. interpolation 은 불연속한 데이터를 사용해서 데이터와 데이터 사이의 값을 추정하는 기법입니다. 위 그림에서 각각의 서로 다른 지점 네곳을 모두 포함하는 점선으로 표현된 곡선을 볼 수 있습니다. 이 곡선이 Lagrange polynomial 입니다.

기본 아이디어

1. n+1 개의 데이터로 n차 함수를 만든다.

2. 특정 숫자를 대입하면 0이나 1의 값을 갖는 항을 만든다.

2-1. (x-a)를 곱해주면 x 에 a 값을 대입할 때 0이 된다.

2-2. (x-a)를 (b-a)로 나누면, x에 b를 대입했을 때 1이 된다.

이 아이디어를 1차함수, 2차함수, 3차함수의 예를 통해서 다시 설명하겠습니다.

일차함수의 경우

두 점 (x_0, y_0), (x_1, y_1) 이 주어진 경우 Lagrange polynomial interpolation(라그랑주 보간식) 은 다음과 같습니다.

위 식에 x = x_0, x = x_1 를 대입해보면 주어진 두 지점을 지나고 있음을 알 수 있습니다.

이차함수의 경우

삼차함수의 경우

삼차함수 이상의 고차함수들도 위의 전개들처럼 동일한 순서로 항을 하나씩 늘려나가면 됩니다.

이걸 어떻게 써먹지?

Lagrange polynomial interpolation 을 통해서 local minimum 을 찾는 알고리즘은 다음과 같습니다.

1. 주어진 함수가 Unimodal 하기 때문에 f'(a)f'(b) < 0 인 초기 해가 있는 구간 a,b 를 선택합니다.

2. a,b,c 를 통해서 Lagrange polynomial interpolation 하여 함수 f^(x) 를 찾습니다.

3. f^(x) 의 정확한 형태를 알고 있기 때문에 f^(x) 의 local minimum 은 쉽게 찾을 수 있습니다. 이 local minimum 은 [a,b] 에 존재함이 보장됩니다.

4. f^(x) 의 local minimum θ 에 대해 f'(θ) 를 계산하여 f'(a)f'(θ) < 0 라면 [a,θ] 에 대해 2,3 과정을 반복하고, f'(b)f'(θ) < 0 라면 [θ,b] 에 대해 2,3 과정을 반복합니다.

5. 이외의 경우는 f'(θ) = 0 인 경우 밖에 없고, 이때는 θ 가 local minimum 인 경우입니다.