最快下降法

最快下降法 最速下降法，就是求梯度。 例如:求f=(x-y)/(x^2+y^2+2)在(-3,-2)处的梯度。 clc;clear x=-3;y=-2 f='(x-y)/(x^2+y^2+2)' fx=diff(f,'x')%对x求偏导数 fy=diff(f,'y')%对y求偏导数 g=[fx fy]%梯度 g=subs(g)%把符号变量转为数值 function [xo,fo] = Opt_Steepest(f,grad,x0,TolX,TolFun,dist0,MaxIter) % 用最速下降法求最优化解 %输入:f为函数名 grad为梯度函数 %x0为解的初值 TolX,TolFun分别为变量和函数的误差阈值 %dist0为初始步长 MaxIter为最大迭代次数 %输出: xo为取最小值的点 fo为最小的函数值 % f0 = f(x(0)) %%%%%%判断输入的变量数，设定一些变量为默认值 if nargin < 7 MaxIter = 100; %最大迭代次数默认为100 end if nargin < 6 dist0 = 10; %初始步长默认为10 end if nargin < 5 TolFun = 1e-8; %函数值误差为1e-8 end if nargin < 4 TolX = 1e-6; %自变量距离误差 end %%%%%第一步，求解的初值的函数值 x = x0; fx0 = feval(f,x0); fx = fx0; dist = dist0; kmax1 = 25; %线性搜索法确定步长的最大搜索次数 warning = 0; %%%%%迭代计算求最优解 for k = 1: MaxIter g = feval(grad,x); g = g/norm(g); %求在x处的梯度方向 %%线性搜索确定步长 dist = dist*2; %令步长为原步长的二倍 fx1 = feval(f,x-dist*2*g); for k1 = 1:kmax1 fx2 = fx1; fx1 = feval(f,x-dist*g); if fx0 > fx1+TolFun & fx1 < fx2 - TolFun %fx0 > fx1 < fx2， den = 4*fx1 - 2*fx0 - 2*fx2;num = den - fx0 + fx2; %二次逼近法 dist = dist*num/den; x = x - dist*g; fx = feval(f,x); %确定下一点 break; else dist = dist/2; end end if k1 >= kmax1 warning = warning + 1; %无法确定最优步长 else warning = 0; end if warning >= 2|(norm(x - x0) < TolX&abs(fx - fx0) < TolFun) break; end x0 = x; fx0 = fx; end xo = x; fo = fx; if k == MaxIter fprintf('Just best in %d iterations',MaxIter); end %xiajiangfa.m 用最速下降法求解最优化问 f1=inline('x(1)^2+4*x(2)^2','x');%目标函数 grad=inline('[2*x(1),8*x(2)]','x');%目标函数的梯度函数 x0=[1 1]; %x0为搜索初始值 TolX=1e-4; %TolX为最优值点间的误差阀值 TolFun=1e-9; %TolFun为函数的误差阀值 MaxIter=2; %MaxIter为最大迭代次数 [xo,fo]=Opt_Steepest(f1,grad,x0,TolX,TolFun,dist0,MaxIter);%xo为最优值点，fo为函数在点xo处的函数值 dist0=0.5; %dist0为初始步长 理论 考虑到函数f(x)在点x^((k) )处沿着方向d的方向导数f_d (x^((k) ) )=?f(x^((k) ) )^T d, 其意义为:f(x)在点x^((k) )处沿着方向d的变化率。当f连续可微时，方向导数为负，说明函数值沿着该方向下降;方向导数越小，明下降越快。因此确定搜索方向d^((k) )的一个想法，就是以f(x)在点x^((k) )点方向导数最小的方向作为搜索方向，即令 d^((k) )=-?f(x^((k) ) ) 因此，把这方法定名为最速下降法。 求解问题〖min〗?(x?R^n )?f(x)，f?C^1。 最速下降法的具体步骤为 选定初始点x^((1) )，和给定精度要求ε>0，令k=1; 若??f(x^((k) ) )?<ε，则停，x^*=x^((k) )，否则令d^((k) )=-?f(x^((k) ) ); 在x^((k) )处沿方向d^((k) )作线性搜索得x^((k+1) )=x^((k) )+α_k d^((k) )，k=k+1，回2。 若在第三步中，不用近似方法做线搜索，而是用精确线搜索，即 α_k=argmin f (x^((k) )+αd^((k) ) ) “argmin f (x)”，表示f(x)的极小点。