《最优化之最速下降法ppt课件.ppt》由会员分享,可在线阅读,更多相关《最优化之最速下降法ppt课件.ppt(16页珍藏版)》请在三一办公上搜索。
1、主讲人:王俊俊,最优化最速下降法,最速下降法,由Nordri()设计提供,LOGO,最速下降法的由来,由Nordri()设计提供,考虑无约束问题其中,函数法f(x)具有一阶连续偏导数。人们在处理这类问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点,基于此种愿望,早在1847年法国数学家Cauchy提出了最速下降法。后来,Curry等人作了进一步研究,得出现在众所周知的一种最基本算法。,2023/1/8,最速下降法的由来,其主要思想 每次沿负梯度方向进行搜索,LOGO,最速下降法的方向选择,最速下降法用负梯度为方向作为搜索方向。设 f(x)在XK附近连续可微,d
2、k为搜索方向向量,.由泰勒展开式得那么目标函数 f(x)在Xk处沿方向dk下降的变化率为,由Nordri()设计提供,LOGO,最速下降法的方向选择,其中 为gk与dk的夹角。要使得变化率最小,只有当cos值为-1时,才能达到,也即dk应取得负梯度方向。,2023/1/8,1.选取初始点,容许误差。令k:=1.2.计算。若,停算,输出Xk作为近似最优解。3.取方向dk=-gk。4.由线搜索技术确定步长因子。5.令,转步长1。,最速下降法的步骤,2023/1/8,由式 得,即新点xk+1处的梯度是正交的,也就是说,迭代点列所走 的路线是锯齿型的,故收敛速度是很慢的。,2023/1/8,步长因子,
3、步4中,步长因子 的确定即可以采用精确线搜索又可以采用非精确线搜索。采用精确线搜索时 那么 应该满足 由此我们可以求出步长因子。,2023/1/8,函数 f(x1,x2)=(1-x2)2+100*(x2-x12)2,它叫罗森布罗克方程。,2023/1/8,罗森布罗克方程的三维图,它的全局最优点位于一个长长的、狭窄的、抛物线形状的、扁平的“山谷”中。找到“山谷”并不难,难的是收敛到全局最优解(全局最优解在(1,1)处)。,2023/1/8,求 使其满足,令,输出:,结束,开始,给定初始点,,计算,否,是,程序图,2023/1/8,matlab仿真实例,2023/1/8,matlab仿真实例,2023/1/8,最速下降法的优缺点,由于沿负梯度方向目标函数的最速下降性,很容易使人们误认为负梯度方向是最理想的搜索方向,最速下降法是一种理想的极小化方法。必须指出的是,某点的负梯度方向,通常只是在该点附近才具有这种最速下降的性质。在一般情况下,当用最速下降法寻找极小点时,其搜索路径呈直角锯齿状,在开头几步,目标函数下降较快;但在接近极小点时,收敛速度长久不理想了。特别适当目标函数的等值线为比较扁平的椭圆时,收敛就更慢了。优点是:程序简单,计算量小;并且对初始点没有特别的要求。,LOGO,谢谢各位,由Nordri()设计提供,