《无约束优化方法》PPT课件.ppt

《《无约束优化方法》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章无约束优化方法模式法：利用某些点上的函数值构造搜索方向如坐标轮换法、鲍威尔法等求解无约束优化问题minf（X）的数值迭代解法，称为无约束优化方法。方法的基本问题是：选择搜索方向不同的搜索方向，构成不同的无约束优化算法。方法分：导数法和模式法两类导数法：利用梯度和二阶导数构造搜索方向如梯度法、牛顿法、变尺度法、共扼梯度法等4.1梯度法梯度法是一种古老的优化算法，它的迭代方向是由负梯度构成的，也称最速下降法。根据极值的必要条件和复合函数的求导公式，有梯度法的迭代算式是式中，为最优步长因子，由一维搜索确定，即或X0S0S1X*此式表明：相邻

2、两迭代点的梯度是彼此正交的，相邻的搜索方向相互垂直，如图所示。由图可以看出：①向极小点的逼近路径是一条曲折的锯齿形路线，而且越接近极小点，前进速度越慢。②离极小点较远时，一次迭代得到的函数下降量较大。因此，许多收敛性较好的算法，第一步迭代都采用梯度法。（1）给定初始点X0和收敛精度ε，置k=0；（2）计算梯度，并构造搜索方向（3）一维搜索，求新的迭代点（4）收敛判断：若满足则令X*=Xk+1，f（X*）=f（Xk+1）终止计算；否则，令k=k+1，转（2）继续迭代。梯度法的迭代步骤如下：解（1）第一次迭代求令令则有例4-1用梯度法求解无约束

3、最优化问题已知解得因还需继续迭代（2）第二次迭代同理有解得因可知也不是极小点，还应继续进行迭代。此问题的最优解是X*=[4，2]T，f（X*）=－8用梯度法求解时，需要经过相当多次迭代才能得到一个近似的最优解。其中前两次的迭代路线如图所示。X0S0S1X*x1x212123X2X14.2牛顿法对上式求梯度，并设X（k+1）是函数的极小点，则有由此解得牛顿法的搜索方向由目标函数的负梯度和二阶导数矩阵构造。4.2.1基本牛顿法将函数f(X)在点Xk处展成泰勒二次式：令则有由此构成的算法称基本牛顿法，Sk称牛顿方向。⑶对于一般非线性函数，点Xk+

4、1只是原函数的一个近似极小点。故将此点作为下一个迭代Xk+1。⑵用基本牛顿法求解正定二次函数时，无论从哪个初始点出发，计算所得牛顿方向直指极小点，而且步长等于1。⑴对于正定二次函数，Xk+1是精确极小点，方向Sk是直指函数的极小点。分析可知：⑷但是对于非正定函数，由上式得到的点Xk+1，不能始终保持函数的下降性，基本牛顿法有可能失败。如图所示，原因：步长因子总是等于1，令4.2.2阻尼牛顿法改进方法：引入步长因子和一维搜索。由此构成如下阻尼牛顿法。由此建立的算法就是阻尼牛顿法，称阻尼因子牛顿法的特点：⑴构造搜索方向利用了函数的所有的一阶导数

5、和二阶导数，产生的搜索方向直指极小点；⑵对于正定二次函数，从任意初始点出发，一次迭代即可得到极小点。对于一般函数，迭代的次数比其它算法都要少。⑶每次迭代都需要计算函数的二阶导数矩阵及其逆矩阵。计算量大，计算时间长，计算速度较慢。⑷计算中，用差分代替微分。所得梯度和二阶导数矩阵，以及求得的牛顿方向都存在较大误差。解1）用基本牛顿法计算例4-2用牛顿法求解例4-1已知2）用阻尼牛顿法代入原函数对α求导因故最优解是：基本牛顿法不需一维搜索，因此计算速度较快。两种方法都只进行了一次迭代，这是因为标函数是正定二次函数，基本牛顿法的局限性还没有显露出来

6、的缘故。此解与基本牛顿法的计算结果完全相同。可以看出：解得因最优解为代入式泰勒展开式得（2)用坐标变换简化目标函数基本思想：（1）用简单矩阵代替二阶导数矩阵的逆矩阵正定，必存在矩阵U若使(4－12)引入矩阵变换U，令4.2.3变尺度法用U和U-1分别左乘和右乘式(4－12)，有代入前式得由此可见，通过坐标变换可以得到上式中只包含Y的二次项和一次项，采用坐标平移可消去一次项，使其等值线变为同心椭圆（球）。由以上两式构成的下降迭代解法称变尺度法。将上式代入牛顿法的迭代算式得记矩阵，称变尺度矩阵，则有称变尺度方向。其中式中其中，A0=I（单位矩阵

7、）；Ek称校正矩阵经推导，变尺度矩阵可由以下递推公式得到：4.2.4共轭梯度法4.2.4.1共轭方向设H为正定对称矩阵，有一组非零向量满足则称这组向量关于矩阵H共轭，或是H的一组共轭向量。当H为单位矩阵时，即有此时称向量Sn（i=1，2，…，n）相互正交。共轭方向具有以下性质：（1）对于正定二次函数,从任意初始点X0出发，依次沿一组（n个）共轭方向一维搜索，最多n次即可以达到极小点。（2）从任意两点X10和X20出发，分别沿同一方向S0进行一维搜索，得到两个一维极小点X11和X21，则连接此两点所形成的向量与原方向S0关于该函数的二阶导数矩

8、阵相共轭。X10S0S1X*X20S04.2.4.2共轭方向的产生平行搜索法向量组合法。1.平行搜索法见后面的鲍威尔法2.向量组合法（1）基向量组合法取n个基向量ei（i=0，1