Univariate search 설명
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다.
Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다.
Univariate search 를 이해하기 위한 사전 지식
아래 링크는 Univariate optimization(단변수 최적화) 를 위한 알고리즘입니다. 아래 링크의 내용을 이해하고 보시면 더 쉽게 Univariate search 를 이해할 수 있습니다.
Univariate search
이미지 출처: http://mathfaculty.fullerton.edu/mathews/n2003/PowellMethodMod.html
위 그림은 Univariate search 의 예시입니다. 이미지 출처에서는 Taxi cab method 라고 설명되어 있습니다. 이미지를 보면 x, y 축과 평행한 방향으로 탐색이 진행되고 있음을 알 수 있습니다.
Univariate search 의 아이디어는 함수의 공간을 N-dimensional space 에서 1-dimension 으로 변경하는 것입니다. 위 그림에서는 최초 iteration 에서 y 의 값을 1.7~1.8 사이의 값으로 고정하고, 즉 f(x, 1.7...) 에 대해서 optimization 을 수행합니다.
이미지 출처: https://arxiv.org/abs/1706.06066v1
전혀 다른 내용의 논문이지만, 설명을 위해 이미지를 인용합니다. 특정 변수 y 를 고정한다는 건 함수의 형태가 위 그림과 같다고 할때, 검정색 선으로 함수 공간을 한정하는 것과 같습니다. 원래의 함수 f(x, y) 가 f(x) 가 되는 것이죠.
함수의 공간을 Unit vector 의 방향으로 한정한 뒤 기존의 Unimodal optimization method 인 Fibonacci search 나 Golden section search 를 적용하여 단계적으로 함수의 minimum 을 찾아간다고 이해할 수 있습니다.
구현 코드 추가 예정
11월 중(?)
