Powell's method 설명

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

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

Powell's method 를 이해하기 위한 사전 지식

Powell's method 는 Univariate search 를 응용한 것이기 때문에 이를 먼저 이해하고 있어야 합니다.

Powell's method

Powell's method 를 시각화 한 영상입니다.

앞서 언급했듯이 Powell's method 는 Univariate search 를 응용한 것입니다. 두 방법을 이미지를 통해 비교하면 Powell's method 를 더 쉽게 이해할 수 있습니다.

Univariate search(좌), Powell's method(우)

같은 문제에 대해 그래프로 iteration 결과를 표현한 것입니다. Univariate search 는 각 Unit vector 의 방향과 순서대로 iteration 이 진행되고 있음을 알 수 있습니다.

Powell's method 는 각 Unit vector 의 방향과 순서대로 iteartion 을 진행한 뒤, 최초 지점에서 현재 위치까지의 방향을 새로운 Unit vector 삼아서 iteration 을 진행합니다. 이를 그림으로 표현하면

여기서 (1,0) 방향으로 라는 표현이 혼동을 줄 수도 있는데, (1,0) 이라는 vector 가 위 그래프에서 꼭 오른쪽으로의 최적화를 보장하는 것이 아닙니다. (1,0) 앞에 붙는 계수가 음수인 경우를 생각하면 왼쪽으로도 최적화 될 수 있는 것이죠.

Powell's method 를 의사코드로 표현하면 다음과 같습니다.

코드는 차후 추가 예정

참조

All about