最优化之最速下降法.

主讲人：王俊俊最优化—最速下降法LOGO最速下降法的由来最速下降法的方向选择最速下降法的算法步骤最速下降法的实例最速下降法由Nordri®（）设计提供LOGOLOGO最速下降法的由来由Nordri®（）设计提供考虑无约束问题其中，函数法f(x)具有一阶连续偏导数。人们在处理这类问题时，总希望从某一点出发，选择一个目标函数值下降最快的方向，以利于尽快达到极小点，基于此种愿望，早在1847年法国数学家Cauchy提出了最速下降法。后来，Curry等人作了进一步研究，得出现在众所周知的一种最基本算法。nRxxf,minLOGO2020/5/31最速下降法的由来•其主要思想每次沿负梯度方向进行搜索kx●)(kxf*x●等值线(面)●1kxLOGOLOGO最速下降法的方向选择最速下降法用负梯度为方向作为搜索方向。设f(x)在XK附近连续可微，dk为搜索方向向量，.由泰勒展开式得那么目标函数f(x)在Xk处沿方向dk下降的变化率为由Nordri®（）设计提供kkxfdkkxfg,0,kTkkkkdgxfdxfLOGOLOGO最速下降法的方向选择coslimlim00kkkTkkTkkkkdgdgdgxfdxf其中为gk与dk的夹角。要使得变化率最小，只有当cos值为-1时，才能达到，也即dk应取得负梯度方向。()Jaaka()Ja()JaLOGO2020/5/31•1.选取初始点，容许误差。令k:=1.•2.计算。若，停算，输出Xk作为近似最优解。•3.取方向dk=-gk。•4.由线搜索技术确定步长因子。•5.令，转步长1。最速下降法的步骤nRx010kkxfgkgk,1:,:1kkdxxkkkkLOGO2020/5/31•由式得，即新点xk+1处的梯度是正交的，也就是说，迭代点列所走的路线是锯齿型的，故收敛速度是很慢的。kkxfd01kTkxfxfLOGO2020/5/31步长因子•步4中，步长因子的确定即可以采用精确线搜索又可以采用非精确线搜索。•采用精确线搜索时那么应该满足由此我们可以求出步长因子。kkkkkkdxfdxf0limk0'kTkkkkkddxfdxfddxkLOGO2020/5/31•函数f（x1,x2）=(1-x2)^2+100*(x2-x1^2)^2,它叫罗森布罗克方程。LOGO2020/5/31罗森布罗克方程的三维图•它的全局最优点位于一个长长的、狭窄的、抛物线形状的、扁平的“山谷”中。找到“山谷”并不难，难的是收敛到全局最优解（全局最优解在(1,1)处）。LOGO2020/5/31求使其满足0min()()kkkkkfxpfxpk令1kkkkxxp输出：minkxx结束开始给定初始点，，0nxE0:0k计算()kkpfxkp否是程序图LOGO2020/5/31matlab仿真实例LOGO2020/5/31matlab仿真实例LOGO2020/5/31最速下降法的优缺点•由于沿负梯度方向目标函数的最速下降性，很容易使人们误认为负梯度方向是最理想的搜索方向，最速下降法是一种理想的极小化方法。必须指出的是，某点的负梯度方向，通常只是在该点附近才具有这种最速下降的性质。在一般情况下，当用最速下降法寻找极小点时，其搜索路径呈直角锯齿状，在开头几步，目标函数下降较快；但在接近极小点时，收敛速度长久不理想了。特别适当目标函数的等值线为比较扁平的椭圆时，收敛就更慢了。优点是：程序简单，计算量小；并且对初始点没有特别的要求。(4)xO(2)x(3)xLOGO谢谢各位由Nordri®（）设计提供