资源描述：
《无约束优化ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四章 无约束问题的最优化方法(一)最速下降法(梯度法)基本思想以迭代点的负梯度方向为搜索方向迭代公式X(k+1)＝X(k)+αk▽F(X(k))(k=0,1,2,…)算法特点迭代过程中，相邻的搜索方向相互垂直，即向极小点的逼近路径是一条曲折的锯齿形路线。对初始点要求不高，最初几步下降快，越来越慢。最速下降法的搜索路径开始是k←0给定X(0)、εk←k+1否结束最速下降法程序框图例用最速下降法求的极小值，设初始点解：目标函数的梯度收敛要求ε1=10-2。在X(0)点的梯度为梯度的模为负梯度方向为新的搜索方向新
2、的搜索方向…新的搜索方向当k=7时(二)牛顿法基本思想在X(k)点用一个二次函数Φ(X)去逼近F(X)，求出Φ(X)的极小点作为原目标函数F(X)的极小点的一次近似值进行迭代计算。迭代公式X(k+1)＝X(k)－[H(X(k)]-1▽F(X(k))(k=0,1,2,…)X(k+1)＝X(k)－αk[H(X(k)]-1▽F(X(k))(k=0,1,2,…)故迭代公式X(k+1)＝X(k)－[H(X(k)]-1▽F(X(k))(k=0,1,2,…)阻尼牛顿法其迭代公式为X(k+1)＝X(k)－αk[H(X(k))
3、]-1▽F(X(k))(k=0,1,2,…)阻尼牛顿法避免了牛顿法可能收敛于极大点或鞍点的不足，具有二次收敛特性，并且即使初始点选择不当，用这种探索方法也会成功。几点说明：⑴当海赛矩阵非正定或奇异时，牛顿法搜索失败或不能进行迭代。⑵计算工作量大，当F(X)不可微时，此算法不能用。开始是k←0给定X(0)、εk←k+1否结束阻尼牛顿法程序框图例用牛顿法求的极小值。设初始点解：只迭代一次就达到了最优点。(三)共轭方向1.共轭方向的概念设A为正定对称矩阵，若有一组非零向量S1，S2，…，Sn满足则称这组向量关于矩阵
4、A共轭。若A为单位矩阵，则有负梯度方向与共轭方向α0S(0)X(1)X(0)α1S(1)S(2)此时称向量Si(i=1，2，…，n)相互正交。共轭是正交的推广，正交是共轭的特例。共轭方向对于构造一种有效的算法非常重要。2.共轭方向的性质对于一般函数，共轭方向具有以下性质：⑴若S(i)(i=1,2,…,n)是以A共轭的n个向量，则对于正定二次函数从任意初始点X(0)出发，依次沿这n个方向进行一维搜索，最多n次即可达到极小点。⑵从任意两个点X1(0)和X2(0)出发，分别沿同一方向S(0)进行一维搜索，得到两个一
5、维极小点X1(1)和X2(1)，则连接此两点构成的向量S(1)＝X2(1)－X1(1)与原方向S(0)关于该函数的二阶导数矩阵相共轭。通过一维搜索确定共轭方向提供共轭向量系的方法有多种，如共轭梯度法、鲍威尔(Powell)法等等。(四)共轭梯度法基本思想利用相邻两点的负梯度构造共轭方向，使其尽快达到最优点。共轭梯度的几何说明算法特点所需的存贮量少，不用计算二阶偏导数矩阵及其逆阵，计算简单，收敛速度快。开始是给定X(0)、εk←k+1否结束是k=n否共轭梯度法程序框图例用共轭梯度法求的极小值。设初始点解：第一次
6、迭代的搜索方向第二次迭代的搜索方向(五)变尺度法基本思想利用牛顿法的迭代形式，构造一个对称正定矩阵A(k)来代替目标函数F(X)的[H(X)]-1，并在迭代过程中使其逐步逼近[H(X)]-1。算法特点简化了牛顿法的计算，且保持了牛顿法收敛快的优点。说明：⑴当A(k)＝I(单位矩阵)时，上式为梯度法的迭代公式；⑵当A(k)＝[H(X)]-1时，上式为牛顿法的迭代公式。在实际应用中，当k=0时，一般令A(0)＝I。因此，变尺度法在最初的几步迭代，与梯度法类似，函数值下降较快；在最后几步迭代，与牛顿法相近，可较快地
7、收敛到极小点。1.构造变尺度矩阵应遵循的原则⑴A(k)必须是对称正定矩阵，以保证算法具有下降性质。⑵A(k)具有简单的递推形式，以保证算法的方便性。A(k+1)=A(k)+E(k)式中E(k)为第k次的校正矩阵。⑶要求迭代产生的搜索方向S(k)=-[A(k)]T▽F(X(k))关于矩阵H(X(k))共轭，以保证算法的二次收敛性。2.变尺度法的一般步骤⑴选定初始点X(0)和收敛精度ε；⑵计算g(0)=▽F(X(0))，选取初始对称正定矩阵A(0)＝I，k←0；⑶计算搜索方向S(k)=－A(k)g(k)；⑷沿S(
8、k)方向进行一维搜索X(k+1)=X(k)+α(k)S(k)，计算g(k+1)=▽F(X(k+1))，ΔX(k)=X(k+1)－X(k)，Δg(k)=g(k+1)－g(k)和E(k)；⑸判断是否满足迭代终止准则，若满足，则X*=X(k+1)，停止计算。否则转⑹；⑹当迭代n次后还没找到极小点，重置A(k)＝I，并以当前设计点为初始点X(0)←X(k)，返回⑵进行下一轮迭代，否则转⑺；⑺计算A(k+1)
