최소한의 기능 평가를 가진 단 변량 root-finding

Question

아주 적은 기능 평가를 사용하는 root-finding 알고리즘을 찾고 있습니다 (목표는 최소 임). 루트 - 발견 된 문제는 다음과 같은 특징이 있습니다 :

f(x) = 0, R -> R

• 기능 (f(.)) 평가는 매우 비용이 많이 드는 *;
• 경계 간격 ([a,b])은 시작에 사용할 수 있습니다 (비교적 좋은 근사값, 야생 추정치는 아닙니다).
• f(.)은 연속적이다;
• f(.)은 분화 가능하다 (분석적인 유도체는 이용 가능하지 않다).
• 시작 간격 ([a,b]) 내에 단일 루트 만있는 것으로 알려져 있습니다.
• 부드럽게 변화하는 f(.) (기능에서 극단적 인 것은 기대하지 않는다); 허용 기준, 예를 들어. |f(x)| < 1e-2이면 충분합니다.

* 알고리즘에 의해 수행 된 계산이 단일 평가 f(.)에 비해 무시할 만하다고 가정 할 수 있습니다. 따라서 단일 기능 평가를 절약하는 것이 중요한 이점입니다.

주어진 기능 평가의 수가 가장 적은 루트를 찾는 가장 효율적인 알고리즘은 무엇입니까? 위에 설명 된 특정 문제에 대한보다 효율적인 알고리즘이있을 수 있지만 matlab에의 fzero와 scipy의 root-finding functions을 바탕으로

은, 브렌트의 방법은 인기있는 선택으로 보인다.

도서 및 리뷰 기사에 대한 참고 자료도 환영합니다.

Answer 1

브렌트의 방법을 시도하려는 경우 아래의 원래 알고리즘에 대한 번역을 시도해 볼 수 있습니다. 이것은 원래 C 코드를 MATLAB으로 번역 한 것입니다. 원래의 C 코드에 대한 모든 테스트 케이스가 번역에서 동일한 결과를 산출한다는 것을 확인했습니다.

아래 코드에서 This은 함수 핸들이고 a 및 b은 검색 범위입니다.

function x = brent(This,a,b) 

tol = 1e-2 ; 
maxit = 1e+3 ; 
displayIter = true ; 

Fa = This(a) ; 
Fb = This(b) ; 
c = a ; 
Fc = Fa ; 

it = 0 ; 
if displayIter 
    fprintf(1,'Searching for a root in the interval [%g,%g] using Brent''s method...\n',a,b) ; 
end 
while it<maxit 
    it = it + 1 ; 

    prevStep = b - a ; 

    if abs(Fc) < abs(Fb) 
     % swap for b to be best approximation 
     a = b ; 
     b = c ; 
     c = a ; 
     Fa = Fb ; 
     Fb = Fc ; 
     Fc = Fa ; 
    end 

    tolAct = 2*eps*abs(b) + tol/2 ; 

    newStep = (c-b)/2 ; 

    if abs(newStep) <= tolAct || abs(Fb)<eps 
     % acceptable solution found 
     x = b ; 
     return 
    end 

    if abs(prevStep) >= tolAct && Fa == Fb 
     % previous step was large enough and in the right direction, try 
     % interpolation 
     cb = c-b ; 
     if abs(a-c)<eps 
      % if only two distinct points, interpolate linearly 
      t1 = Fb/Fa ; 
      p = cb*t1 ; 
      q = 1 - t1 ; 
     else 
      % three points, do quadratic inverse interpolation 
      a = Fa/Fc ; 
      t1 = Fb/Fc ; 
      t2 = Fb/Fa ; 
      p = t2*(cb*q*(q-t1) - (b-a)*(t1-1)) ; 
      q = (q-1)*(t1-1)*(t2-1) ; 
     end 
     if p>0 
      q = -q ; 
     else 
      p = -p ; 
     end 
     if p < (0.75*cb*q-abs(tolAct*q)/2) && p < abs(prevStep*q/2) 
      newStep = p/q ; 
     end 
    end 
    % step must be at least as large as tolerance 
    if abs(newStep)<tolAct 
     if newStep>0 
      newStep = tolAct ; 
     else 
      newStep = -tolAct ; 
     end 
    end 

    a = b ; 
    Fa = Fb ; 
    b = b + newStep ; 
    Fb = This(b) ; 
    if (Fb > 0 && Fc > 0) || (Fb < 0 && Fc < 0) 
     c = a ; 
     Fc = Fa ; 
    end 
    if displayIter 
     fprintf(1,'[%g] Gap = %g, dx = %g\n',it,abs(Fb),newStep) ; 
    end 
end 
fprintf(1,'[%g] Gap = %g, dx = %g\n',it,abs(Fb),newStep) ; 

end