第4章 优化设计(无约束优化-间接法)

1、4.4.3 梯度法梯度法是求解多维无约束优化问题的是求解多维无约束优化问题的解析法之一解析法之一。基于基于梯度梯度是函数增大最快的方向，是函数增大最快的方向，而而负梯度负梯度则是函数下降最快的方向。则是函数下降最快的方向。沿沿搜索，使函数值在该点附近下降最快。搜索，使函数值在该点附近下降最快。则则梯度法梯度法就是取迭代点处的就是取迭代点处的函数负梯度方向函数负梯度方向作作为为搜索方向搜索方向，该法又称，该法又称最速下降法最速下降法梯度法的基本思想梯度法的基本思想: :( )( )( 1)( )( ) ( )( )( )( )()()kkkkkkkkkSf XXXSXf X 梯度法的迭代格式梯度

2、法的迭代格式：（4-38） 按按上式上式求得负梯度方向的一个求得负梯度方向的一个极小点极小点 ，作为作为的一个近似的一个近似最优解最优解；若此解尚不满足若此解尚不满足精度要求精度要求，则再以，则再以 作为作为迭迭代起始点代起始点，以，以 处的负梯度方向处的负梯度方向 作为搜索方向，作为搜索方向，求得该方向的求得该方向的极小点极小点 ，如此进行下去，直到如此进行下去，直到求得的解求得的解满足收敛条件满足收敛条件为止。为止。)1( kX(1)()kf X(2)kX)1( kX)1( kX式中式中 为为最优步长最优步长。( )k（1）任取）任取初始点初始点 ，选定收敛精度，选定收敛精度 0，令，令

3、。（2）计算）计算 。（3）若）若 ，则迭代终止，取，则迭代终止，取 ，否则，否则进行步骤（进行步骤（4）。）。（4）用）用一维搜索求一维搜索求 ，得最优步长，得最优步长 。（5）令）令 ， ，返回步，返回步骤（骤（2）。）。 0X0k kXf kXf k*XX kkSXfmin kkkkkkXfXX11 kk( )kX112212()102()42()f Xxxxf Xxxf Xx 解：解：由由梯度的定义梯度的定义，该目标函数该目标函数的的梯度梯度为：为：例例2-A 已知已知一目标函数一目标函数为为22121212()60 104f Xxxxxx x，试求试求在点在点 的梯度。的梯度。( )

4、112( )12122()102102 1 210()42()42 2 11kkxf Xxxxf Xxxf Xx 则则该函数该函数在在点点的梯度的梯度为为( )1, 2TkX梯度法的终止条件梯度法的终止条件：( )|()| kf X ()1()()2()()()() ()kkkknfXxfXfXxfXx2()()1/ 21()|() | () knkiifXfXx梯度法的特点：梯度法的特点：算法简单；算法简单； (2) 前后两次迭代方向前后两次迭代方向正交正交，所以，所以搜索路线搜索路线是是呈直角锯齿形呈直角锯齿形； (3) 开始搜索时，收敛速度较快，但当靠近开始搜索时，收敛速度较快，但当靠近

5、极极小点小点附近，收敛速度越来越慢，这是附近，收敛速度越来越慢，这是梯度法梯度法的较的较大缺点。大缺点。4.4.4 牛顿法牛顿法 和和两种。两种。 也是一种也是一种解析法解析法，它是，它是梯度法梯度法的进一步发展。的进一步发展。该法的搜索方向的构造该法的搜索方向的构造：是根据是根据目标函数目标函数的的负梯度负梯度和和二阶偏导数矩阵二阶偏导数矩阵来构造的。来构造的。牛顿法分为牛顿法分为：其其迭代过程迭代过程是在求目标函数是在求目标函数 的极小值时，先的极小值时，先将它在点将它在点X附近附近作泰勒展开作泰勒展开，并取，并取二次近似函数式二次近似函数式；然后求出这个二次函数的然后求出这个二次函数的极

6、小点极小点，并以，并以该极小点该极小点作作为原目标函数的为原目标函数的极小点极小点X* 的一次的一次；( )kX()f X 它是以它是以二次函数二次函数来逼近来逼近原目标函数原目标函数。若若此解此解不满足精度要求，则可不满足精度要求，则可以此近似解以此近似解作为下一次迭代作为下一次迭代的的初始点初始点，仿照上面的做法，求出，仿照上面的做法，求出二次近似解二次近似解；照此迭代下去，直至所求出的照此迭代下去，直至所求出的近似极小点近似极小点满足精度要求。满足精度要求。该算法的基本思路该算法的基本思路：)(Xf现用现用二维问题二维问题来加以说明，来加以说明，将将目标函数目标函数 在给定点在给定点 作

7、作泰勒展开泰勒展开，并取，并取二次近似式二次近似式：( )kX( )( )( )( )( )( )()()()() ()1 ()()()2kkTkkkkf XXf Xf XXXXXH XXX ()f X为求得为求得二次近似式二次近似式 的的极小点极小点 ，对上式求梯度，并令对上式求梯度，并令)(X*X( )( )( )()()()0kkkXf XH XXX 解之可解之可求得求得：*( )( )1( )()()kkkXXH Xf X式中式中: 为为海森海森（Hessian）矩阵矩阵的逆矩阵。的逆矩阵。( )1()kH X在一般情况下，在一般情况下，不一定是不一定是二次函数二次函数，则所求得的则所

8、求得的极小点极小点 也不一定是也不一定是原目标函数原目标函数 的的真正极小点真正极小点。但由于在但由于在点点附近，函数附近，函数 和和 是近似的，因而是近似的，因而 可作可作为为 的的近似极小点近似极小点。为为求得求得满足精度要求的满足精度要求的近似极小点近似极小点 ，可将，可将 作为下一次迭代的作为下一次迭代的起始点起始点 ，即得，即得 (1)( )( )1( )()()kkkkXXH Xf X()f X*X*X()f X)(kX()f X)1( kX()f X*X)(X（4-39） ( )( )1( )()()kkkSH Xf X 由上由上式式( (4-39) )可知，可知，为为上式就是上

9、式就是。上式中的上式中的搜索方向搜索方向称为称为牛顿方向牛顿方向，可见可见原始牛顿法原始牛顿法的的步长因子步长因子恒取：恒取： ，因此，因此，原始牛顿法原始牛顿法是一种是一种定步长定步长的迭代过程。的迭代过程。)(kS( )1k对于对于二次函数二次函数是非常有效的，迭代一步就可达到是非常有效的，迭代一步就可达到极值点极值点，而这一步根本不需要进行一维搜索。而这一步根本不需要进行一维搜索。对于对于高次函数高次函数，只有当迭代靠近，只有当迭代靠近极值点极值点附近，附近，目标函数目标函数近似近似二次函二次函数数时，才会保证时，才会保证很快收敛很快收敛，否则也可能导致算法失败。，否则也可能导致算法失败

10、。为了克服这一缺点，便将为了克服这一缺点，便将迭代公式迭代公式（4-39）修改为：修改为：(1)( )( )( )1( )()()kkkkkXXH Xf X)(k（4-41）上式为上式为阻尼牛顿法的迭代公式阻尼牛顿法的迭代公式。式中，式中，步长因子步长因子 又称阻尼因子。又称阻尼因子。上式称为上式称为阻尼牛顿法的迭代公式阻尼牛顿法的迭代公式。式中，。式中，步长因步长因子子 又称阻尼因子。又称阻尼因子。为了克服牛顿法缺点，将为了克服牛顿法缺点，将迭代公式迭代公式（4-39）修修改为：改为：)(k（4-41）(1)( )( )( )1( )()()kkkkkXXH Xf X阻尼牛顿法阻尼牛顿法 ，

11、则迭代停止，则迭代停止 ，0，令，令 。如下：如下： 0X0k kXf kXf kX 12kXf kkkXfXfS12 kS kkkkkSXX11 kk（1）给定初始点）给定初始点 ，收敛精度，收敛精度（2）计算）计算，若，若 即为所求，否则进行（即为所求，否则进行（3）。）。（3）计算）计算 及及 。（4）沿）沿 进行一维搜索，确定最优步长进行一维搜索，确定最优步长 。（5）令）令 ，返回（，返回（2）。）。 而且对目标函数的要求严格，除了要求函数而且对目标函数的要求严格，除了要求函数二阶连续可微二阶连续可微外，外，为了保证函数的为了保证函数的稳定下降稳定下降， 必须处处正定，为了能求必须处

12、处正定，为了能求逆阵又要求逆阵又要求 必须必须非奇异非奇异。 阻尼牛顿法阻尼牛顿法保持了牛顿法收敛快的优点，又不要求初始点选保持了牛顿法收敛快的优点，又不要求初始点选得很好，因而在实际得很好，因而在实际应用应用中取得了较好的效果。其中取得了较好的效果。其缺点缺点仍然是仍然是需计算需计算 及其逆阵，及其逆阵，计算相当复杂，程序存储量大计算相当复杂，程序存储量大； kXH kXH kXH4.4.5 变尺度法变尺度法 是在克服了是在克服了 和和 的的缺点缺点基础上而发展起来的基础上而发展起来的一种最有效的解析法一种最有效的解析法。现已得到广泛应用。现已得到广泛应用。利用利用牛顿法的迭代形式牛顿法的迭

13、代形式，但并不直接计算但并不直接计算 ，而是用一个而是用一个对称正定矩阵对称正定矩阵 近似地代替近似地代替 。它在它在迭代过程中迭代过程中不断地改进，最后逼近不断地改进，最后逼近 。这种算法这种算法，省去了，省去了海森矩阵海森矩阵的计算和求逆，的计算和求逆，使之使之计算量计算量大为减少，大为减少，并且还保持了并且还保持了收敛快的优点。收敛快的优点。( )1()kH X( )kA(*)1()H X( )1()kH X在在变尺度法变尺度法 中，较为常用的有：中，较为常用的有：变尺度法变尺度法特点特点： DFP变尺度法变尺度法 BFGS变尺度法变尺度法。变尺度法变尺度法基本思想基本思想：1. DFP

14、变尺度法变尺度法 是最为常用的一种是最为常用的一种变尺度算法变尺度算法。 为：为：(1)( )( )( )( )( )( )( )()kkkkkkkkXXSXAf X(4-42) 式中式中: 是是变尺度矩阵变尺度矩阵，是一，是一nn阶阶对称对称正定矩阵正定矩阵，在迭代过程中，在迭代过程中, ,它是它是逐次形成逐次形成并并不不断修正断修正，即从一次迭代到另一次迭代是变化的，即从一次迭代到另一次迭代是变化的，故称故称变尺度矩阵变尺度矩阵。 ( )kA1. DFP变尺度法变尺度法 由由式式(4-42)，不难看出：不难看出：当当 （单位矩阵）时：（单位矩阵）时：式式 (4-42)变为变为；当当 时：时

15、：式式 (4-42)就变为就变为。( )kAI( )( )1()kkAH X由此可见，由此可见，和和可以看作可以看作变尺度法变尺度法的一种的一种特例特例。变尺度矩阵变尺度矩阵可用下式迭代下式迭代：(1)( )( )kkkAAA式中，式中， 称作称作校正矩阵校正矩阵，在在DFP变尺度法变尺度法中中它它可用可用下式下式来计算：来计算：( )kA( )( )( )( )( )( )( )( )( )( )( )( )kkTkkkTkkkTkkTkkXXAggAAXggAg式中式中:第第 k 次迭代中前后迭代点的次迭代中前后迭代点的向量差向量差 ；前后迭代点的前后迭代点的梯度向量差梯度向量差 。( )

16、(1)( )( )(1)( )()()kkkkkkXXXgf Xf X迭代开始迭代开始（k0）规定）规定： 。(0)HI 上式上式称为称为，由该式可以看出，由该式可以看出，变尺度矩阵变尺度矩阵 的确定的确定取决于取决于在第在第 k 次迭代中的次迭代中的下列信息下列信息：不仅不需求不仅不需求海森矩阵海森矩阵 及其及其求逆矩阵求逆矩阵的计的计算，而且保持了算，而且保持了牛顿法收敛速度快牛顿法收敛速度快和和梯度法计算简梯度法计算简单单的优点。的优点。(1)kA 上次的变尺度矩阵上次的变尺度矩阵 ， 迭代点的向量差迭代点的向量差 迭代点的梯度向量差迭代点的梯度向量差 。)(kA)(kX)( kg)()

17、(kXH因此，因此，利用利用上式上式求得的求得的校正矩阵校正矩阵 代入代入变尺度矩阵计变尺度矩阵计算公式算公式，可得到，可得到 ：( )( )(k)( )( )(k)(1)( )( )( )( )(k)( )AAATTkkkkkkTTkkkkXXggAAXggg( )kA上式上式常称常称DFP公式公式。通过通过式式(4-42)可可确定确定新的搜索方向新的搜索方向 ，进行，进行第第k+1次迭代次迭代的一维搜索。的一维搜索。 )(kS)0(X(0)()f X为：为：(1)给定给定初始点和收敛精度初始点和收敛精度，维数，维数n；(2)计算计算梯度，取梯度，取A(0) = I (单位矩阵单位矩阵)，置

18、置k =0=0，(3)构造构造搜索方向搜索方向( )( )( )()kkkSAf X )(kS)(k (k)( )( ) ( )( )(X)min(X)kkkkfSfS(1)()kf X(1)()kf X*(1)*(1), ()()kkXXf Xf X(4)沿沿 方向进行方向进行一维搜索一维搜索，求，求最优步长最优步长 ，使，使得到得到新迭代点新迭代点(5)计算计算 ，进行进行收敛判断收敛判断：若若 ，则令，则令 ，停止迭代，停止迭代，输出输出最优解；最优解； 否则，转下一步否则，转下一步(6)；(1)( )( )( )kkkkXXS( )( )( )(1), , ;kkkkXgAA(1)(

19、)(1)(1)(1)(1)()kkkkkkAAASAf X 1kk，见见图图4-22。并令并令 ，转，转步骤步骤(3)。(7)计算计算：构造构造新的新的变尺度矩阵变尺度矩阵和和搜索方向搜索方向：(6)检查检查迭代次数，若迭代次数，若k = n，则令，则令 ，并转入，并转入步骤步骤(2)；若若k n，则转，则转下步下步(7)； (0)(1)kXX图图4-22 DFP变尺度法变尺度法 的计算框图的计算框图DFP变尺度法的优点 变尺度矩阵A(K) ，在开始的几步接近于I，因而类似于梯度法，具有计算量小，函数值下降快的优点； 在最后的几步A(K) 接近于H（ X(K) ）-1,因而类似于牛顿法收敛速度快的优点，但克服了其计算量大的缺点。2. BFGS 变尺度法变尺度法计算实践计算实践表明：表明：由于由于DFP变尺度法变尺度法在计算在计算变尺度矩阵变尺度矩阵的公式中，的公式中，其分母其分母含有近似矩阵含有近似矩阵 A(k)，使之计算中容易引起，使之计算中容易引起数值不稳定数值不稳定，甚