具有最小函数求值的单变量根查找

Question

我正在寻找寻根算法，使用非常少的功能评估(目标是最小)。寻根问题具有以下特点：

f(x) = 0, R -> R

• 功能(f(.))评估非常昂贵*；
• 边界间隔([a,b])是可用的开始(相对较好的逼近，而不是一个疯狂的猜测)；
• f(.)是连续的；
• f(.)是可微的(解析导数不可用)；
• 已知只有一个根位于起始区间([a,b])内；
• 平滑变化的f(.) (没有任何极端的期望从函数)；
• 允许停止标准，例如|f(x)| < 1e-2就足够了。

*我们可以安全地假定，与f(.)的单个评估相比，该算法所做的任何计算都可以忽略不计。因此，即使只进行一次功能评估也是一项重大的收获。

给出了用最少的函数求根的最有效算法是什么？

在Matlab的fzero和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