最优化Armijo算法确定步长的最速下降法.docx
- 文档编号:17857617
- 上传时间:2023-08-04
- 格式:DOCX
- 页数:9
- 大小:190.01KB
最优化Armijo算法确定步长的最速下降法.docx
《最优化Armijo算法确定步长的最速下降法.docx》由会员分享,可在线阅读,更多相关《最优化Armijo算法确定步长的最速下降法.docx(9页珍藏版)》请在冰点文库上搜索。
最优化Armijo算法确定步长的最速下降法
长沙理工大学
数学与计算科学学院
实验报告
实验工程名称使用非准确线搜索Armijo算法确定步长的最速下降法
所属课程名称最优化方法
实验类型算法编程
实验日期
班级
学号
姓名
成绩
一、实验概述:
【实验目的】
1.通过实验掌握最速下降法的Matlab算法的根本步骤;
2.通过实验掌握Armijo算法确定步长;
3.掌握最速下降法的思想及迭代步骤。
【实验原理】
1.最速下降法:
最古老的优化方法,十九世纪中叶由Cauchy提出
思想:
每次沿负梯度方向进展搜索
负梯度方向也称为最速下降方向:
举例:
算法步骤:
优点:
最速下降法的收敛性:
全局收敛性:
收敛速度估计:
结论:
最速下降法的收敛速度比拟慢,通常将其用在某些算法的初始阶段求较好的初始点或作为某些算法的间插步.
【实验环境】
Win7;
Matlab7.0
二、实验内容:
【实验方案】
1、求梯度;
2、向梯度相反的方向移动x,其中
为步长。
如果步长足够小,那么可以保证每一次迭代都在减小,但可能导致收敛太慢,如果步长太大,那么不能保证每一次迭代都减少,也不能保证收敛。
3、循环迭代步骤2,直到x的值变化到使得
在两次迭代之间的差值足够小,比方0.00000001,也就是说,直到两次迭代计算出来的
根本没有变化,那么说明此时
已经到达局部最小值了。
4、此时,输出x,这个x就是使得函数
最小时的x的取值。
【实验过程】
梯度下降法的计算过程就是沿梯度下降的方向求解极小值〔也可以沿梯度上升方向求解极大值〕。
其迭代公式为
其中
代表梯度负方向,
表示梯度方向上的搜索步长。
梯度方向我们可以通过对函数求导得到,步长确实定比拟麻烦,太大了的话可能会发散,太小收敛速度又太慢。
一般确定步长的方法是由线性搜索算法来确定,即把下一个点的坐标ak+1看做是的函数,然后求满足f(ak+1)的最小值的即可。
因为一般情况下,梯度向量为0的话说明是到了一个极值点,此时梯度的幅值也为0.而采用梯度下降算法进展最优化求解时,算法迭代的终止条件是梯度向量的幅值接近0即可,可以设置个非常小的常数阈值。
【实验结论】〔结果〕
梯度下降法处理一些复杂的非线性函数会出现问题,例如Rosenbrock函数:
其最小值在
处,函数值为
。
但是此函数具有狭窄弯曲的山谷,最小点就在这些山谷之中,并且谷底很平。
优化过程是之字形的向极小值点靠近,速度非常缓慢。
靠近极小值时收敛速度减慢。
直线搜索时可能会产生一些问题。
可能会“之字形〞地下降。
【实验小结】〔收获体会〕
这次的实验报告,使得我们对这些算法的思想更加了解,在选择线性搜索的方法时,我们深刻体会到各类参数设置对程序效率的重要性,不同的问题要选用适宜的参数来求解,这样使得问题求解及程序运行的效率最高。
通过不断地翻阅课本,剖析程序,我们最后实现了对程序的修改和完善,对提供的问题作出了较好的解答。
总的来说,对无约束最优化的求解,每种方法在解决不同的问题中效果不能都到达最优,所以我们在实际应用中,要根据实际情况选择适宜的方法,争取最大可能的尽快的接近最优。
本次实验不仅使我们根本了解了最优化的实用算法的构造及性能,而且也使得我们对matlab的一些编程技巧更加熟悉,收获很大。
三、指导教师评语及成绩:
评语
评语等级
优
良
中
及格
不及格
1.实验报告按时完成,字迹清楚,文字表达流畅,逻辑性强
2.实验方案设计合理
3.实验过程〔实验步骤详细,记录完整,数据合理,分析透彻〕
4实验结论正确.
成绩:
指导教师签名:
批阅日期:
附录1:
源程序
Armijo算法实现:
[plain]viewplaincopy
functionmk=armijo(fun,xk,rho,sigma,gk)
assert(rho>0&&rho<1);
assert(sigma>0&&sigma<0.5);
mk=0;max_mk=100;
whilemk<=max_mk
x=xk-rho^mk*gk;
iffeval(fun,x)<=feval(fun,xk)-sigma*rho^mk*norm(gk)^2
break;
end
mk=mk+1;
end
return;
最速下降法实现:
[plain]viewplaincopy
function[opt_x,opt_f,k]=grad_descent(fun_obj,fun_grad,x0)
max_iter=5000;%maxnumberofiterations
EPS=1e-5;%thresholdofgradientnorm
%Armijoparameters
rho=0.5;sigma=0.2;
%initialization
k=0;xk=x0;
whilek k=k+1; gk=feval(fun_grad,xk);%gradientvector dk=-1*gk;%searchdirection ifnorm(dk) break; end yk=feval(fun_obj,xk); fprintf('#iter=%5d,xk=%.5f,F=%.5f\n',k,xk,yk); mk=armijo(fun_obj,xk,rho,sigma,gk); xk=xk+rho^mk*dk; end fprintf('----------------------\n'); ifk==max_iter fprintf('ProblemNotsolved! \n'); else fprintf('Problemsolved! \n'); end %recordresults opt_x=xk; opt_f=feval(fun_obj,xk); return; 附录2: 实验报告填写说明 1.实验工程名称: 要求与实验教学大纲一致。 2.实验目的: 目的要明确,要抓住重点,符合实验教学大纲要求。 3.实验原理: 简要说明本实验工程所涉及的理论知识。 4.实验环境: 实验用的软、硬件环境。 5.实验方案〔思路、步骤和方法等〕: 这是实验报告极其重要的内容。 概括整个实验过程。 对于验证性实验,要写明依据何种原理、操作方法进展实验,要写明需要经过哪几个步骤来实现其操作。 对于设计性和综合性实验,在上述内容根底上还应该画出流程图、设计思路和设计方法,再配以相应的文字说明。 对于创新性实验,还应注明其创新点、特色。 6.实验过程〔实验中涉及的记录、数据、分析〕: 写明具体实验方案的具体实施步骤,包括实验过程中的记录、数据和相应的分析。 7.实验结论〔结果〕: 根据实验过程中得到的结果,做出结论。 8.实验小结: 本次实验心得体会、思考和建议。 9.指导教师评语及成绩: 指导教师依据学生的实际报告内容,给出本次实验报告的评价。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 Armijo 算法 确定 步长 下降