第2章优化设计-3

(+1)()()()min()min()kkkkfXfXS11(0,1,2)kkkkXXSk由前数值迭代法可知，求某目标函数的最优值时，迭代过程每一步的格式都是从某一定点出发，沿着某一使目标函数下降的规定方向搜索，以找出此方向的极小点。这一过程是各种最优化方法的一种基本过程。)(kS)1(kX)(kX07:55:022一维优化方法，它不仅可用来解决一维目标函数的求优问题，且常用于多维优化问题在既定方向上寻求最优步长的一维搜索。§2.4多维无约束优化方法本节主要内容§2.4.1梯度法§2.4.2牛顿法§2.4.3变尺度法§2.4.4坐标轮换法§2.4.5鲍威尔法前言nnRXxxxfXf)()(min21，，，求解这类问题的方法，称为无约束优化方法。无约束优化问题的一般数学表达式为：数值迭代法的基本迭代格式为：(1)()()()(0,1,2,)kkKkXXSk式中：X(k)——前一步已取得的设计方案（迭代点）；X(k+1)——新的改进设计方案（新的迭代点）；S(k)——第k次迭代计算的搜索方向；α(k)——第k次迭代计算的步长因子。数值迭代法寻找最优点X*，这里关键要解决二个问题：●一是如何确定迭代步长α(k)；●二是怎样选定搜索方向S(k)；前言各种无约束优化问题的区别：确定搜索方向方法的不同前言无约束优化方法有很多种，但归纳可以分为两大类：■解析法（间接法）■直接法多维无约束优化方法中，根据确定搜索方向所使用的信息和方法的不同，前言直接法通过几个已知点上目标函数值的比较来构造搜索方向Powell法、坐标轮换法间接法利用目标函数的一阶偏导数或二阶偏导数构造搜索方向梯度法、牛顿法、变尺度法2.4.1梯度法（最速下降法）取迭代点处的函数负梯度方向作为每次搜索方向，直至找到极小点，该法又称最速下降法。梯度法的迭代格式：梯度法的基本思想:2.4.1梯度法（最速下降法）(1)min()min()min[()]kkkkkkkfXfXSfXfX当方向sk给定，求最佳步长αk就是求一元函数的最优解：梯度法的终止条件：()||()||kfXTnxXfxXfxXfXf)(,...,)(,)()(2121212)()()()(iikkxXfXf2.4.1梯度法（最速下降法）梯度法的迭代步骤（1）任取初始点，选定收敛精度＞0，令（2）计算。取搜索方向（3）若则迭代终止，取，否则进行步骤（4）。（4）用一维搜索求，得最优步长。（5）令，，返回步骤(2)0X0kkXfk*XXkkSXfminkkkkkXfXX11kkkXf≤ε2.4.1梯度法（最速下降法）2.4.1梯度法（最速下降法）2.4.1梯度法（最速下降法）2.4.1梯度法（最速下降法）例：用梯度法求目标函数的最优解。取初始点迭代精度222125)(xxXf,22TX.005.0解：函数的梯度：2121502)(xxxfxfXf(0)(0)4(),()100.0799100fXfX计算点的梯度及其范数值：)0(X第一次迭代：以为起点沿方向进行一维搜索，)0(X)()0(Xf22)0()0()1002(25)42(min))((minXfXf10410016250016min2最优步长计算方法一，使用函数的性质计算02003072.0)0(0))(()0()0(XfXf2.4.1梯度法（最速下降法）07:55:022019/12/2017最优步长计算方法二，使用黄金分割法计算10410016250016)(2g令用进退法求初始区间，首先假设31,1.0,01eh1602.6)(,1.0104)(,02212111gghgg则由于，所以向后探测。互换的值。21gg2121,,gg以及3605.8)(,1.0--3313ggh此时,,1041232gggg所以，初始为[-0.1,0.1]用黄金分割法求最小值，得到02.0)0(2.4.1梯度法（最速下降法）07:55:022019/12/2018得到第一个迭代点：003072.0919877.1100402003072.022)()0()0()0()1(XfXX,153589.0839754.3)()1(Xf继续如下迭代计算：8428.3)()1(Xf2.4.1梯度法（最速下降法）07:55:022019/12/20192.4.1梯度法（最速下降法）终止迭代，得最优解：0000386.000241185.0)5(*XX000006.0)(*Xf2.4.1梯度法（最速下降法）07:55:022019/12/2021004-1.1600e153589.0839754.3100,4)()()1()0(XfXfT007-4.2530e)()()2()1(XfXfT007-1.1037e)()()3()2(XfXfT009-7.7260e)()()4()3(XfXfT009-6.0011e)()()5()4(XfXfT2.4.1梯度法（最速下降法）07:55:022019/12/20222.4.1梯度法（最速下降法）梯度法的讨论：2.4.1梯度法（最速下降法）步长因子的求解方法：解析法：根据极值点必要条件一维搜索方法：黄金分割法、二次插值法、牛顿法等2.4.1梯度法（最速下降法）2.4.1梯度法（最速下降法）26(1)初始点可任选，每次迭代计算量小，存储量少，程序简单。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢变慢；(2)任意相邻两点的搜索方向正交，它的迭代路径为绕到逼近极小点。当迭代点靠近极小点附近，步长变得很小，收敛速度越来越慢，这是梯度法的较大缺点。梯度法的特点：2.4.1梯度法（最速下降法）例4.6用梯度法求目标函数的最优解。取初始点,11TX.1.0要求进行一步迭代，并判断是否收敛。122212132x)(minxxxxXf2.4.1梯度法（最速下降法）2.4.1梯度法（最速下降法）解：函数的梯度：11212223()4fxxxfXxxfx(0)(0)0(),()55fXfX计算点的梯度及其范数值：)0(X第一次迭代：以为起点沿方向进行一维搜索，)0(X)()0(Xf(0)(0)2min(())min1152(15)3fXfX2min50251最优步长计算方法一，使用函数的性质计算(0)0.250))(()0()0(XfXf2.4.1梯度法（最速下降法）07:55:022019/12/2031得到第一个迭代点：(1)(0)(0)(0)101()0.25150.25XXfX(1)1.25(),0fX需继续进行第二次迭代(1)()1.25fX2.4.1梯度法（最速下降法）2.4.2牛顿法牛顿法可分为二：原始牛顿法和阻尼牛顿法两种。牛顿法是一种古典解析算法，它是梯度法的进一步发展。实际中应用较多的是阻尼牛顿法该法的搜索方向的构造：是根据目标函数的负梯度和二阶偏导数矩阵来构造的。该算法的基本思路：它是以二次函数来逼近原目标函数。2.4.2牛顿法—原始牛顿法34该法的搜索方向的构造：2.4.2牛顿法—原始牛顿法35原始牛顿法的步长因子恒取：，因此，原始牛顿法是一种定步长的迭代过程。12.4.2牛顿法—原始牛顿法07:55:022019/12/20362.4.2牛顿法—原始牛顿法07:55:022019/12/2037例4.6用牛顿法求目标函数的最优解。取初始点迭代精度222125)(xxXf.005.022)0(X解：取初始点22)0(X,02.0005.0)(,50002)(,1004)(1)0()0()0(XHXHXf迭代计算：00)()()0(1)0()0()1(XfXHXX即为的极小点。)1(X)(Xf2.4.2牛顿法—原始牛顿法07:55:022019/12/2038上例说明：牛顿算法对于二次函数是非常有效的，迭代一步就可达到极值点，而这一步根本不需要进行一维搜索。对于高次函数，只要当迭代点靠近极值点附近，目标函数近似二次函数时，才会保证很快收敛。否则可能导致算法失效。因此，对初始点的选取有严格要求。尽管牛顿法收敛快，但初始点不能离极小点太远。否则可能不收敛。只有当迭代靠近极值点附近，目标函数近似二次函数时，才会保证很快收敛。对于正定二次函数，其泰勒展开不是近似的，而是精确的。Hessian矩阵是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。2.4.2牛顿法—原始牛顿法07:55:022019/12/2039牛顿法的性质：优点：牛顿法具有二次收敛性。对于二次正定函数，迭代一次即可得到最优解，对于非二次函数，若函数二次型较强或者迭代点已经进入最优点的较小邻域，则收敛速度也很快。缺点：由于迭代点的位置是按照极值条件确定的，并未沿函数值下降方向搜索，因此，对于非二次函数，有时会使函数值上升，即，从而使计算失败。)()()()1(kkXfXf2.4.2牛顿法—原始牛顿法要求初始点不能离最优点太远07:55:022019/12/2040阻尼牛顿法迭代公式为：步长因子又称阻尼因子，为最优步长因子。)(k牛顿阻尼法保持了牛顿法收敛快的特点，且对初始点无特别要求。虽然计算量多了一些，但实用性更好为了克服这一缺点，便将迭代公式修改为：2.4.2牛顿法—阻尼牛顿法07:55:022019/12/2041阻尼牛顿法的迭代步骤如下：kXfkXfkX12kXfkkkXfXfS12kSkkkkkSXX11kk0X0k（1）给定初始点，收敛精度＞0，令。（2）计算，若＜，则迭代停止，即为所求，否则进行（3）。（3）计算及。（4）沿进行一维搜索，确定最优步长。（5）令，，返回（2）。412.4.2牛顿法—阻尼牛顿法07:55:022019/12/2042阻尼牛顿法流程图2.4.2牛顿法—阻尼牛顿法43优点：保持了牛顿法收敛快的优点，又对初始点没有苛刻的要求缺点：2.4.2牛顿法—阻尼牛顿法07:55:022019/12/20442.4.2牛顿法452.4.3变尺度法变尺度法基本思想：1)只用到一阶偏导数,计算量小;2)迭代初期收敛速度快，但当迭代到最优点附近时收敛慢；梯度法特点462.4.3变尺度法变尺度法基本思想：牛顿法特点1)收敛很快，对二次函数只需要迭代一次便达到最优点，对非二次函数也能较快的迭代到最优点，2)牛顿法要计算海森矩阵以及其逆矩阵，对维数较高的优化问题，其计算工作量和存储量都太大，而对于某些函数可能根本无法计算二阶偏导数及其逆472.4.3变尺度法变尺度法基本思想：为了克服梯度法收敛速度慢、牛顿法计算量大的缺点，又要保持牛顿法收敛快而梯度法计算量下的优点。48变尺度法基本思想：2.4.3变尺度法（拟牛顿法）(1)()()()()()kkkkkXXAfX在迭代过程中不断的修正改变，从而对梯度起到改变尺度的