无约束优化方法-一阶导数（最速下降法）

利用导数信息的方法皆为间接方法。在无约束优化法最开始介绍时，提到迭代形式的优化方法关键步骤是确定搜索方向和步长。间接方法更为关注搜索方向 $\boldsymbol d_k$ 的确定，其原则使得 $\boldsymbol x_{k+1}=\boldsymbol x_k+\lambda_k \boldsymbol d_k$ 并满足 $f(\boldsymbol x_{k+1})<f(\boldsymbol x_k)$ 。换句话说，在每次迭代中，只要能保证 $f(\boldsymbol x_{k+1})<f(\boldsymbol x_k)$ ，任何方向 $\boldsymbol d_k$ 都是允许的。

那对于某个充分下的 $\lambda_k>0$ ,利用泰勒公式
$f(\boldsymbol x_{k+1}) \approx f(\boldsymbol x_k)+\nabla f(\boldsymbol x_k)^T(\lambda_k \boldsymbol d_k)= f(\boldsymbol x_k)+\lambda_k\nabla f(\boldsymbol x_k)^T \boldsymbol d_k$

显然，只要满足 $\nabla f(\boldsymbol x_k)^T \boldsymbol d_k<0$ ，就能保证 $f(\boldsymbol x_{k+1})<f(\boldsymbol x_k)$ ，这说明搜索方向 $\boldsymbol d_k$ 与目标函数在点 $\boldsymbol x_k$ 处梯度 $\nabla f(\boldsymbol x_k)$ 的方向之间的夹角必大于90°。

确定方向后，利用一维搜索技术进行步长因子的确定，可以是精确的，也可是非精确的。如果有直接的关于步长因子的表达式，直接求得即可。在后续的相关间接方法中，我们主要关心方向的确定，步长因子的确定就方法的不同给出一些经验建议。

最速下降法

最速下降法顾名思义就是寻找使得目标函数在 $\boldsymbol x_k$ 处下降最快的方向，也就是使得 $\nabla f(\boldsymbol x_k)^T \boldsymbol d_k$ 最小， $\nabla f(\boldsymbol x_k)$ 和 $\boldsymbol d_k$ 之间的夹角等于180°，搜索方向取负梯度方向，令 $g(\boldsymbol x) = \nabla f(\boldsymbol x)$ ,则 $\boldsymbol d_k=-g(\boldsymbol x_k)$ 。如果使用一维精确搜索确定步长因子，可以证明前后两次的搜索方向是正交的。
Algorithm 1 Steepest Descent Method

function [x_min,f_min] = SteepestDescentMethod(func,gfunc,x0,options)

if nargin<3
    options.tol = 1e-12;
    options.iterNum = 1000;
    options.bracketMethod = '';
    options.linearSrcMethod = '';
    options.plot2.Flag = 0;
    options.plot2.x = [];
    options.plot2.y = [];
    options.plot2.z = [];
end
tol = options.tol;
iterNum = options.iterNum;

plot2 = options.plot2;
if length(x0)~=2
    plot2.Flag = 0;
end

x_min = x0;
f_min = func(x0);

xk = x0;

if plot2.Flag == 1
    figure,subplot(1,2,1),axis equal, hold on;
    contourf(plot2.x,plot2.y,plot2.z,30,'linestyle','-')
    colormap('jet');
    tempf =func(xk);
end

while(iterNum)
    d = -gfunc(xk);
    lamdaFuncH = @(lamda)(func(xk+lamda.*d));
    [a,b,c] = bracketAdvanceBack(lamdaFuncH,0,0.01);
    lamda = GoldSection(lamdaFuncH,a,c,1e-12);
    xk1 = xk + lamda.*d;
    f =func(xk1);
    if plot2.Flag == 1
        tempf = [tempf,f];
        subplot(1,2,1),plot([xk(1),xk1(1)],[xk(2),xk1(2)],'-o','LineWidth',2);
        subplot(1,2,2),plot(tempf,'-b.','LineWidth',2); grid on;
        axis([0,options.iterNum,0,func(x0)]);
        xlabel('Step');
        ylabel('Objective Function Value');
        pause(0.1)
    end
    xk = xk1;
    iterNum = iterNum - 1;
    if sqrt(sum(abs(gfunc(xk))))<tol||iterNum == 0
        x_min = xk;
        f_min = f;
        break;
    end
end

最速下降法的收敛速度是线性的。梯度是函数的局部性质，从局部上看，在该点附近函数的下降最快，但是总体看则走了许多弯路，因此函数值下降的并不快。梯度法向极小点逼近路劲是锯齿路线，越接近极小点，锯齿越细，前进速度越慢。

图 1 最速下降法示意

最后编辑于：2019.03.17 21:55:21