[수치프로그래밍] 황금분할 탐색법

황금분할 탐색법

해당 탐색법은 말 그대로 Euclid의 황금비를 이용하여 우리가 원하는 최적값에 도달하는 방식이다.

 

황금비의 정의는 아래와 같다.

 

---

특징

- 한 개의 최소값을 포함하고 있는 구간에서 최소값을 탐색하는 방법 중 하나

- 이분법(Bisection Method)에서 한 개의 중간값을 사용하는 것과는 다르게, 황금반할 탐색법은 최소값의 발생 여부를 알기 위해 두 개의 중간 함숫값이 필요하다

- 이러한 방법이 효율적이기 위해서는 중간점들은 현명하게 선택해야 하며, 이분법에서처럼 이전값을 새로운 값으로 치환함으로써 함수 계산을 최소화시킨다.

 

---

알고리즘

 

해당 그림을 보자

우리는 xl, xr을 통해 아래처럼 x1, x2를 계산할 수 있다.

그리고 x1, x2에 해당하는 함숫값 또한 계산이 가능하다. 

1. 이미지 (b)를 보면 f(x2) > f(x1)인 모습을 볼 수 있다.

2. 이후 해당 x2를 xl로 치환하는 과정을 통해 범위를 좁힐 수 있다. 

{f(x2) < f(x1)라면 xr=x1 치환}

 

위의 과정을 iterative하게 반복하여 어느정도 우리가 원하는 error rate에 진입했다면, xl과 xr를 반환하여 결과를 낼 수 있다. 

---

장점

- 황금비를 사용했을 때의 장점은 이전값이 새로운 값이 되어 새로운 함숫값을 갱신할 필요가 없음을 의미한다.

 

++++

 

황금분할 탐색법에서 함수계산의 수를 최소화하고자하는 두 가지 이유

1. 해당 알고리즘이 대형 계산의 일부인 경우가 있다. 이러한 경우 여러 번 황금분할탐색을 부프로그램을 부르게 된다. 따라서 함수 계산의 수를 최소화하는 것이 중요하다.

2. 시간이 많이 드는 계산을 할 때 유리하다. -> 황금 분할을 이용했기 때문에 어떤 선택되지 않은 x1, x2의 경우 다음 iteration에서의 x1 또는 x2가 될 수 있다.

---

에러 계산

황금비 탐색의 종료판정기준을 살짝 특이한데 계산은 다음과 같다.

x_opt란 내가 선택한 x1또는 x2를 의미한다.. 

---

코드

function [x,fx,ea,iter]=goldmin(f,xl,xu,es,maxit,varargin)
  phi=(1+sqrt(5))/2;
  iter=0;
  while(1)
    d=(phi-1)*(xu-xl);
    x1=xl+d;
    x2=xu-d;
    if f(x1, varargin{:}) < f(x2, varargin{:})
      xopt=x1;
      xl=x2;
    else
      xopt=x2;
      xu=x1;
    endif
    iter=iter+1;
    if xopt~=0, ea=(2-phi)*abs((xu-xl)/xopt)*100; endif
    if ea <= es || iter >= maxit, break, end
  endwhile
  x=xopt;
  fx=f(xopt, varargin{:});
end

결과