工优第四章ppt课件.ppt

《工优第四章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章无约束最优化方法本章主要内容：§1最速下降法§2牛顿法§3共轭方向法§4共轭梯度法§5变尺度法——DFP法和BFGS法1目的是找中的一点，使对，均有，称为(1)的全局极小点。无约束最优化问题：求解(1)的计算方法称为无约束最优化方法。2无约束最优化方法应用广泛，理论也比较成熟；可将约束优化问题转化为无约束优化问题来处理；最优化方法中的基本方法---无约束优化方法本章介绍解析法3在以上步骤中，选取步长可选用精确一维搜索或者非精确一维搜索，下降方向的选取正是下面我们要介绍的，下降方向选取的不同，得到不同的算法。线搜索迭代法的步骤4最速下降法是求多元函数极值的最古老的数值算法，早在184

2、7年法国数学家Cauchy提出该算法，后来Curry作了进一步的研究。该方法直观，简单，计算方便，而且后来的一些新的有效的方法大多数是对它的改进，或受它的启发而得到的。最速下降法5从而得到第k+1次迭代点，即步长最速下降法负梯度方向这是函数值减少最快的方向假设f连续可微，由精确一维搜索得到。6最速下降法x(k)x*d(k)=－f(x(k))x(k+1)d(k+1)=－f(x(k+1))瞎子下山：？向，再下降一步。由于他看不到哪里是山谷，不可能沿直接指向山谷的路线走，他只能在当前位置上，靠手杖作局部探索，哪里最陡就往哪里前进一步，然后在新的位置上再用手杖寻找最陡方7最速下降法的迭代格式

3、8算法框图x1,ε>0,k=1

4、

5、▽f(xk)

6、

7、<ε?Yesstop.x*=xkNodk=－▽f(xk)解minf(xk+λdk)s.t.λ>0得xk+1=x(k)+λkdkk=k+1最速下降法框图9例利用最速下降法求解令解：函数的梯度为第1次迭代：取得10令得第2次迭代：11令得第3次迭代：继续迭代可得到函数的近似最优解。12最速下降法的收敛性分析设目标函数f(x)连续可微，且水平集有界，则最速下降法或者在有限迭代步后终止；或者得到点列，它的任何聚点都是f(x)的驻点。在收敛定理的假设下，若f(x)为凸函数，则最速下降法或在有限迭代步后达到最小点；或得到点列，它的任何聚点都是f(x)

8、的全局最小点。收敛性定理：推论：13最速下降法在两个相邻点之间的搜索方向是正交的。最速下降法向极小点逼近是曲折前进的，这种现象称为锯齿现象。除特殊的目标函数和极特殊的初始点外，这种现象都会发生。令利用精确一维搜索，可得由此得出1.相邻两次迭代的方向互相垂直最速下降法的两个特征14最速下降法的两个特征x(0)x(1)x(2)在最速下降法中，利用精确一维搜索求最佳步长，使得相邻两次迭代的搜索方向总是垂直的，从而逼近极小点过程是“之”字形，这样从任何一个初始点开始，都可以很快到达极小点附近，但是越靠近极小点步长越小，移动越慢，导致最速下降法的收敛速度很慢。实际运用中，在可行的计算时间内得不到需

9、要的结果。最速下降法收敛速度慢15对正定二次函数，用最速下降法产生的点列：偶数项点列均在一条直线上，奇数项点列也均在一条直线上，且都过最优点.最速下降法的两个特征16对正定二次函数，用最速下降法产生的点列：偶数项点列均在一条直线上，奇数项点列也均在一条直线上，且都过最优点.则：分析：因为相邻方向正交，17优点：理论明确，程序简单，每次的计算量小，所需的存储量小，对初始点要求不严格。缺点：收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。最速下降法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，远快近慢。最速下降法的优缺点最速下降法不是好的实用算法，但是一些有效算法

10、是通过对它的改进或利用它与其他收敛快的算法结合而得到的，因此它是无约束优化的方法之一。18为了清除最佳步长最速下降法中两个搜索方向正交的不良后果，提出了许多改进的方法，如：(1)选择不同初始点例令最速下降法的改进取初始点第1次迭代得19然后再从开始新的迭代，经过10次迭代，得最优解计算中可以发现，开始几次迭代，步长比较大，函数值下降将较快，但当接近最优点时，步长很小，目标函数值下降很慢。20如果不取初点为而取一步就得到了极小点。可见：造成锯齿现象与初始点的选择有关，但怎样选一个初始点也是一件困难的事。第1次迭代虽然后一初始点较前一初始点离最优点远，但迭代中不含上面出现的锯齿现象。21采用

11、非精确一维搜索求步长,可使相邻两个迭代点处的梯度不正交，从而改变收敛性。对于最速下降法，有时为了减少计算工作量，采用固定步长，称为固定步长最速下降法。但到底取多大，没有统一的标准，取小了，收敛太慢，而取大了，又会漏掉极小点。（2）采用不精确的一维搜索：最速下降法的改进22（3）采用加速梯度法：由于最速下降法在极小点附近成“锯齿”状，因此下降过程中的搜索方向可取下两步继续用最速下降方向即负梯度方向。Shah等人于1964年提出了一种“