Nelder and Mead method 설명
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다.
Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다.
Nelder and Mead method 를 이해하기 위한 사전지식
아래 링크는 Nelder and mead method 를 이해를 돕기 위해 위키피디아에 작성되어 있던 용어에 대한 내용을 제가 한글로 풀어서 작성한 것입니다.
본문을 보다가 아래 용어 때문에 이해 안되는 부분이 있다면, 그 때 읽으면 됩니다.
3. Simplex(링크)
Nelder and Mead method
Nelder and Mead method 시각화 영상
몇몇 이미지가 동일한 이미지로 보일 수 있으니 주의해서 봐주세요, 작성간 변수 위치만 바꿔서 재활용해서 그렇습니다. 모두 다른 이미지입니다.
Nelder and Mead method(이하 NMM) 는 Downhill simplex method 라고도 불리며 총 3가지 단계로 구성됩니다.
1. Reflection
2. Expansion
3. Contraction
0. Preprocess
Unimodal function f(x) 의 minimum 을 구하고자 합니다.
N+1 개의 임의의 함수값을 계산합니다.
앞으로의 내용을 이해하기 위해 N-dimensional space 에서 N+1 vertices 로 구성된 polygon(simplex) 를 생각해봅니다. 모든 vertices 는 함수 f(x) 위의 점들입니다.
1. Reflection
1) 함수 값을 크기순으로 정렬하고
2) C, X_r 을 계산합니다.
여기서 C 는 가장 큰 함수값을 가지는 x_N+1 을 제외한 점들의 중심점입니다.
결과적으로 x_r 은 x_N+1 과 C 를 직선으로 이은 선 위에 존재하게 되죠.
원본 이미지 출처: DOI: 10.1016/j.cma.2018.04.011
N 차원 공간 위에서(2차원내지 3차원 좌표계로 상상하면 이해가 쉽습니다.) 이런 x 들로 계산한 함수값 f(x) 들이 구성하는 Simplex(즉 Convex hull) 를 상상해봅니다. 공중에 위 그림과 같이 어떤 다면체가 둥둥 떠있다고 생각하는거죠.
함수가 Unimodal 이기 때문에 minimum 으로부터 가장 먼 f(x_N+1) 에서 반대방향의 f(x_r) 을 찾으면, 이는 보편적으로 minimum 에 더 가까울 것입니다. 언덕의 가장 꼭대기에 있는 f(x_N+1) 로부터 내려오기 때문에 Downhill simplex method 라고 이름 붙인 것 같습니다.
그림에서는 minimum 으로부터 가장 먼 x_4 에서 C 방향으로 x_r 을 탐색한다는 것으로 이해했습니다.
3) x_r 에서의 함수값 f_r 을 계산합니다.
4) 여기서 Reflection 을 반복할지, Expansion, Contraction 의 분기로 나아갈지 나뉩니다.
이 경우 f_N+1 을 제외하고 f_r 을 포함한 N+1 개의 vertices 들을 함수값을 기준으로 크기를 재정렬후 index 도 크기 순으로 다시 부여한다는 의미입니다.
2. Expansion
1) 새로운 x_e 와 f_e 를 계산하고 이를 f_r 과 비교합니다.
2) Reflection 으로 돌아갑니다.
Expansion 과정은 "x_r 방향으로 발을 뻗었는데 기존 함수값들보다 더 작은 값인 f_r 이 계산되었으니 이 방향으로 좀 더 뻗으면 더 작은 함수값을 찾을 수도 있다." 라는 느낌으로 이해하면 될 것 같습니다.
3. Contraction
Case 1.
case 2
a. 에서 f_N < f_r 이지만, f_r < f_N+1 이기 때문에 현재 simplex 에서 x_N+1 을 제거하고 x_r 을 업데이트하고, reflection 으로 돌아가도 minimum 으로 수렴할 수 있겠지만, 이는 비효율적이기 때문에 x_c, f_c 를 계산하는 과정을 한번 더 거치는 것으로 이해했습니다.
좀 쉽게 혹은 다르게 표현하면 "발을 뻗어서 x_r 을 찾았지만 생각보다 크니까, 덜 뻗으면 더 좋은 함수값을 찾겠지" 정도로 이해했습니다.
Nelder and Mead method 장점과 단점
장점:
실행이 쉽습니다.
N+1 개의 vertices 만 기억하면 되기 때문에 메모리 사용이 linear 합니다. 즉 메모리를 적게 사용합니다.
단점:
α, β, γ 총 3가지의 parameter 를 어떻게 설정하느냐에 따라 계산 속도의 차이가 있습니다.
다른 알고리즘에 비해 상대적으로 더 많은 iteration 을 수행해야 합니다.
Stagnation(굄, 고임) 이 발견되면 새로운 polygon 으로 알고리즘을 다시 시작해야 합니다. Stagnation 이란 minimum 이 아닌 지점에 수렴하는 것으로 이해했습니다.
코드는 차후 추가 예정(아마도 11월 중에?)
참고
