第四章 第四节

nullnull§2.4 无约束优化法 梯度法 牛顿法 共轭方向法 变尺度法 共轭梯度法null一、梯度法 1.基本思想 梯度方向是函数增加最快的方向，而负梯度方向是函数 下降最快的方向； 梯度法以负梯度方向为搜索方向，每次迭代都沿着负梯 度方向一维搜索，直到满足精度要求为止； 因此，梯度法又称为最速下降法。null 设在某次迭代中已取得迭代点 ，从该点出发，取负梯度方向： 式中， 这样，第k+1次迭代计算所得的新点为： 梯度法迭代公式nullnull2.迭代步骤 步骤一 任选初始点 ，计算精度ε，令k=0； 步骤二 计算 点的梯度 及梯度的模 ， 并令 步骤三 判断是否满足精度指标 若 ，则 为近似最优点，迭代停止， 输出最优解 和 若不满足，转下一步null步骤四 以 为出发点，沿负梯度方向求最优步长 ， 即沿 进行一维搜索，求能使函数值下降最多的步 长因子 ； 步骤五 确定新的近似点 ，此点就是下次迭代的出发点， 即 步骤六 令k=k+1转步骤二，直到满足精度要求为止。null给定 、k=0 ？转出k=k+1梯度法的程序框图null3.举例 用梯度法求函数 的极小值， 初始点 ，计算精度 。null(3)因为 ，不满足精度指标，转入第(4）步； (4)从 出发，沿着方向 一维搜索， 将 代入目标函数并求其极小值 式中 为单变量α的一维函数，令null 所以求得一维优化的最优步长 (5)新点 (6)计算目标函数在点 的梯度及梯度的模 由于已满足精度要求，故停止迭代下去，得到最优解为：null二、牛顿法 1.基本思想 设目标函数是连续二阶可微的，将函数在点 按泰勒级数展开，并取到二次项： 将其展开为：null对x求导，其极值点必满足一阶导数为零，所以， 得到 上式与一维搜索公式 比较，则有 搜索方向 ，步长因子null牛顿法的迭代算式其中 称为牛顿方向。null2.迭代步骤 步骤一 给定初始点 ，计算精度ε，令k=0； 步骤二 计算 点的梯度 、二阶导数矩阵 及其逆矩阵 。 步骤三 构造搜索方向null步骤四 沿 方向进行一维搜索，得迭代点 步骤五 收敛判断： 若 ，则 为近似最优点，迭代停止， 输出最优解 和 终止计算。 若不满足，令k=k+1，转第二步继续迭代。null3.举例 用牛顿法求函数 的极小值。null故(3)极小值null 数学分析表明，牛顿法具有很好的局部收敛性质，对二次函数来说，仅一步就达到优化点， 但对一般函数来说，在一定条件下，当初始点的选取充分接近目标函数的极小点时，有很快的收敛速度，但若初始点选取离最小点比较远，就难保证收敛； 牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂的目标函数来说，是较困难的。null三、共轭方向法 椭圆的共轭方向 共轭方向的基本思想 null1.椭圆的共轭方向 如图所示的椭圆中，任意一组平行弦 的中点的连线必位于过椭圆中心O的直线S上，这些平行弦所组成的直线族的方向S1与中点连线方向S互称为共轭方向，即S1与S互为共轭方向。 null 椭圆中的平行弦的极限情况是与椭圆相切的弦S0，根据一维搜索观点，该弦S0与椭圆的切点就是沿S0方向的一维搜索的优化点。 共轭方向的代数含义是： 设有两个向量Si与Sj及n×n阶对称正定矩阵A，若满足 则称两向量Si与Sj对于矩阵A共轭。null2.共轭方向的基本思想 设二元函数 的极值点为 ，将函数在 展开成泰勒级数，并取其二次项，若其海色矩阵为正定矩阵，则其目标函数的等值线的极值点附近是近似的同心椭圆族，根据椭圆的共轭方向，只要沿两个相互平行的方向S1进行一维搜索，找出目标函数沿该两个方向的极小点 ，然后沿与S共轭的方向 进行一维搜索，就可以求得目标函数的优化点，也就是说共轭方向法是以椭圆的共轭方向作为搜索方向的。null 在n维空间中，用数学归纳法可以证明，对n维二次目标函数，从任意点 出发，可以找到n个共轭的向量 。 依次对这些向量分别进行一维搜索，就可以找到n维二次目标函数f(X)的极小点 ， 即应用这种算法通过有限次（即n步），可以得到目标函数的极小点。null 如果一种算法，从理论上讲经过有限步的搜索可以求出二次目标函数的极小点，则称这种算法具有二次收敛性，因此，共轭方向法具有二次收敛性。 基于共轭方向的思想，发展起来了多种共轭方向法，在此介绍比较成熟的三种方法： 变尺度法、共轭梯度法和Powell法。null四、变尺度法 变尺度法是优化方法在最近二十几年来发展起来的最有影响的研究成果之一，它被公认为是求解无约束极值问题的最有效的算法之一，这种方法是在牛顿法基础上发展起来的一种共轭方向法，用得较多的是DFP变尺度法。null1.DFP(Davidon-Fletcher-Powell) 牛顿法虽比梯度法收敛的快，但必须求目标函 数的二阶导数及逆阵，不仅困难且工作量大，因此 在牛顿法基础上Davidon-Fletcher-Powell提出了用 一个近似矩阵 代替求二阶导数及逆阵，而且该 矩阵在每一次迭代中都不同，所以称为变尺度矩阵。null一维搜索中最优步长因子: 变尺度法的搜索方向为: 迭代公式为:null2.迭代步骤 步骤一 取初始点 ，计算精度ε； 步骤二 令k=0, ,I为单位阵，搜索方向； 步骤三 一维搜索 (梯度法）； 步骤四 计算(k+1)步梯度，null步骤五 判别精度指标： 如果 ，则 为极小点；否则转下一步。 步骤六 计算近似矩阵 ，构造新的搜索方向 ； 所以 令k=k+1，转步骤三，直到满足精度要求为止。null3.举例 用变尺度法求函数 的极小值。解： (1)取初始点：null(2)一维搜索 (3)如何求 ？nullnull(4)搜索方向 与牛顿法比较其结果非常接近，从本例中可以看出用近似矩阵代替二阶导数及逆阵是可行的。 null如何判断搜索结束？null五.共轭梯度法 1.基本思想 从初始点 出发，沿着该点负梯度方向一维搜索到 ，如图所示。 然后从 出发，按照与上一次搜索方向 相共轭的方向 进行搜索，也就是 ， A为对称正定矩阵。 根据共轭方向原理，沿着方向一维搜索，就可以直接 达到优化点。 null2.共轭梯度的递推公式 设梯度用g表示，k+1点的梯度 可以由k点的梯度 推算出来； 设目标函数是n维二次函数： 式中A——n×n对称正定矩阵； 梯度为：null现从 出发，沿方向 一维搜索得： 由一维搜索的几何描述可知，搜索方向 是 处等值线的切线，而点 的梯度与该切点切线方向垂直，所以： null 和 的梯度由式 可得 以上两式相减得递推公式为： 当 已知时，可计算 。若目标函数是非二次函数，则可将函数按泰勒级数展开，忽 略三次方以上的项，然后用二次函数来逼近null 3.共轭梯度方向 共轭梯度法的关键是如何构造梯度的共轭方向 。 由图可以看出， 的方向可以看成是 和 的线性组合，即 式中只要求出 ，则可求出： null 由梯度递推公式 两边乘以 得： 因为根据共轭方向的含义： 所以 把 代入 得： 展开该式得：null因为 ，代入： 可得： 则有： null4.迭代步骤(以二维为例) 步骤一 取初始点 ，计算精度ε； 步骤二 计算梯度 ，从 出发，沿方向 一维搜索到 ； 步骤三 由式 计算 ； 由式 计算 ；则 步骤四 从 出发，沿方向 一维搜索，就可以达到 优化点 。 null5.举例 用共轭梯度法求函数 的极小值。 解： (1)第一步是梯度法，取初始点 沿方向 一维搜索得：null(2)计算 点的梯度： 由 计算null(3)计算搜索方向 (4)从 出发，沿着 的方向一维搜索，其最优步长 由此可得： null(5)判断是否达到精度ε=0.01要求： 则 为极小点。 null 从以上可以看出，对同一个目标函数，采用 共轭梯度法只需经过两次迭代便达到极值点，所 以共轭梯度法比梯度法收敛得快很多。 共轭梯度法与梯度法一样，必须求目标函数 的梯度，这对于较复杂的实际问题来说是很 困难的。null【本节思考题】 1.梯度法、牛顿法、变尺度法的搜索方向确定的理论 依据分别是什么？ 2.梯度法、牛顿法、变尺度法之间有什么内在联系？ 3.梯度法、牛顿法、变尺度法各有什么优缺点？null【作业】1.用梯度法求解(做两次迭代)：2.用牛顿法求解：3.用变尺度法求解：