基于精确线搜索的最速下降法及实例

基本思想

对于给定的一个无约束优化问题
$\min \limits_{x\in\mathbb{R}^n} \quad f(x)$x∈Rnmin​f(x)
选择搜索方向为 $p_k=-\nabla f(x_k)$pk​=−∇f(xk​) ， 步长为 $\alpha_k$αk​ 是如下子问题
$\min \limits_{\alpha_k>0}\quad f(x_k+\alpha_k p_k)$αk​>0min​f(xk​+αk​pk​) 的解。

一个简单的例子及程序

考虑这样一个函数$f(x)=5x_1^2+\frac{1}{2}x_2^2,$f(x)=5x12​+21​x22​,
设其初值为$[0.1,1]^T$[0.1,1]T, 进度为 $1e-6$1e−6,
其优化程序为
下面展示一些 内联代码片。

function x = SteepestDescent(f,x0,eps)
%% Steepest Descent Method
%f:objective function
%x0:initial value
%eps:accuracy
if nargin<1
    f = @(x1,x2)5*x1^2+0.5*x2^2;
    x0 = [0.1;1];
    eps = 1e-6;
end
maxiter= 10000;
x = x0;
syms x1 x2 l;
grad = jacobian(f,[x1 x2]);
i=0;
while i<maxiter
    g = subs(grad,[x1 x2],[x(1) x(2)]);
    g = g';
    if norm(g)<= eps
        disp(i);
        break;
    end
    p = -g;
    h = l.*p+x;
    phi = subs(f,[x1 x2],[h(1) h(2)]);
    df = diff(phi);
    p = solve(df);
    x = subs(h,p);
    i = i+1;
end
x = vpa(x);
end

理论最优解为$[0,0],$[0,0], 但实验结果显示其收敛速度很慢， 经过71 次迭代，$\Vert x\Vert \leq eps,$∥x∥≤eps, 故我们要使用非精确的线搜索来解决此类问题。