Search algorithm - Seeking bound

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

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

다루는 함수의 Unimodality 가 보장되어 있다면, local minimum 이 존재하는 초기구간을 줄인 상태로 Root finding 알고리즘이나 Search 알고리즘을 적용할 수 있습니다.

간단히 표현하면 Unimodal function 에서 단조 증가와 단조 감소의 경계점인 극점(extreme point)이 있는 구간을 최대한 좁히는 것입니다.

순서는 다음과 같습니다.

1. 최초의 탐색지점 x_0 를 무작위로 선정합니다.

2. x_0 에서의 함수값 f_0 를 계산하고, x_0 로부터 d 만큼 떨어진 x_-1, x_1 에서의 함수 값 f_-1, f_1 을 계산합니다.

3. 세가지 경우로 나누어 생각할 수 있습니다.

1) f_-1 > f_0 < f_1 인 경우 탐색 알고리즘의 시작 구간 [a,b] = [x_-1, x_1] 로 탐색을 시작합니다.

2) f_0 > f_1 인 경우

3) f_0 < f_1 인 경우, 2)와 같은 과정을 반대 방향으로 진행합니다.

여기서 햇갈릴 수 있는 부분은 2) 에서 알고리즘 종료시인데,

로 구간을 설정하는 것은 맨 위의 그림을 사용해서 설명하면,

f_2 < f_3 이지만, minimum x* 는 x* < x_2 인 경우가 있을 수 있기 때문입니다.(위 그림이 그렇다는 것은 아닙니다.)