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

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

按上式求得负梯度方向的一个极小点，作为原问题的一个近似最优解；若此解尚不满足精度要求，则再以作为迭代起始点，以处的负梯度方向作为搜索方向，求得该方向的极小点，如此进行下去，直到求得的解满足收敛条件为止。式中为最优步长。（1）任取初始点，选定收敛精度＞0，令。（2）计算。（3）若≤，则迭代终止，取，否则进行步骤（4）。（4）用一维搜索求，得最优步长。（5）令，，返回步骤（2）。梯度法的迭代步骤

解：由梯度的定义，该目标函数的梯度为：例2-A

已知一目标函数为，试求在点的梯度。则该函数在点

的梯度为梯度法的终止条件：

梯度法的特点：

(1)算法简单；

(2)前后两次迭代方向正交，所以搜索路线是呈直角锯齿形；

(3)开始搜索时，收敛速度较快，但当靠近极小点附近，收敛速度越来越慢，这是梯度法的较大缺点。4.4.4牛顿法

原始牛顿法和阻尼牛顿法两种。

牛顿法也是一种解析法，它是梯度法的进一步发展。该法的搜索方向的构造：是根据目标函数的负梯度和二阶偏导数矩阵来构造的。牛顿法分为：其迭代过程是在求目标函数

的极小值时，先将它在点X附近作泰勒展开，并取二次近似函数式；然后求出这个二次函数的极小点，并以该极小点作为原目标函数的极小点X*的一次近似解；

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

在给定点作泰勒展开，并取二次近似式：为求得二次近似式的极小点

，对上式求梯度，并令解之可求得：式中:为海森（Hessian）矩阵的逆矩阵。

在一般情况下，

不一定是二次函数，则所求得的极小点也不一定是原目标函数的真正极小点。

但由于在点附近，函数和是近似的，因而可作为的近似极小点。

为求得满足精度要求的近似极小点

，可将作为下一次迭代的起始点，即得（4-39）

由上式(4-39)可知，牛顿法的搜索方向为上式就是原始牛顿法的迭代公式。上式中的搜索方向称为牛顿方向，可见原始牛顿法的步长因子恒取：，因此，原始牛顿法是一种定步长的迭代过程。

牛顿算法对于二次函数是非常有效的，迭代一步就可达到极值点，而这一步根本不需要进行一维搜索。对于高次函数，只有当迭代靠近极值点附近，目标函数近似二次函数时，才会保证很快收敛，否则也可能导致算法失败。为了克服这一缺点，便将迭代公式（4-39）修改为：

（4-41）上式为阻尼牛顿法的迭代公式。式中，步长因子又称阻尼因子。上式称为阻尼牛顿法的迭代公式。式中，步长因子又称阻尼因子。为了克服牛顿法缺点，将迭代公式（4-39）修改为：

（4-41）阻尼牛顿法

，则迭代停止，＞0，令。修正牛顿法的迭代步骤如下：（1）给定初始点，收敛精度（2）计算，若

＜

即为所求，否则进行（3）。（3）计算

及。（4）沿

进行一维搜索，确定最优步长。（5）令，，返回（2）。

而且对目标函数的要求严格，除了要求函数二阶连续可微外，为了保证函数的稳定下降，必须处处正定，为了能求逆阵又要求必须非奇异。

阻尼牛顿法保持了牛顿法收敛快的优点，又不要求初始点选得很好，因而在实际应用中取得了较好的效果。其缺点仍然是需计算及其逆阵，计算相当复杂，程序存储量大；4.4.5变尺度法

是在克服了梯度法收敛慢

和牛顿法计算量大

的缺点基础上而发展起来的一种最有效的解析法。现已得到广泛应用。利用牛顿法的迭代形式，但并不直接计算，而是用一个对称正定矩阵近似地代替。它在迭代过程中不断地改进，最后逼近。这种算法，省去了海森矩阵的计算和求逆，使之计算量大为减少，并且还保持了牛顿法收敛快的优点。变尺度法：在变尺度法

中，较为常用的有：变尺度法特点：●

DFP变尺度法●

BFGS变尺度法。变尺度法基本思想：1.DFP变尺度法

DFP变尺度法是最为常用的一种变尺度算法。

该算法的迭代公式为：(4-42)

式中:是变尺度矩阵，是一n×n阶对称正定矩阵，在迭代过程中,它是逐次形成并不断修正，即从一次迭代到另一次迭代是变化的，故称变尺度矩阵。

1.DFP变尺度法

由式(4-42)，不难看出：当（单位矩阵）时：式(4-42)变为梯度法的迭代公式；当时：式(4-42)就变为牛顿法的迭代公式。

由此可见，梯度法和牛顿法可以看作变尺度法的一种特例。变尺度矩阵可用下式迭代：式中，称作校正矩阵，在DFP变尺度法中它可用下式来计算：式中:第k次迭代中前后迭代点的向量差；前后迭代点的梯度向量差。迭代开始（k＝0）规定：。

上式称为DFP公式，由该式可以看出，变尺度矩阵的确定取决于在第k次迭代中的下列信息：不仅不需求海森矩阵及其求逆矩阵的计算，而且保持了牛顿法收敛速度快和梯度法计算简单的优点。●

上次的变尺度矩阵

，●

迭代点的向量差●迭代点的梯度向量差。因此，DFP变尺度法：

利用上式求得的校正矩阵代入变尺度矩阵计算公式，可得到变尺度矩阵的DFP递推公式：上式常称DFP公式。通过式(4-42)可确定新的搜索方向，进行第k+1次迭代的一维搜索。

DFP变尺度法的迭代步骤为：(1)给定初始点和收敛精度ε，维数n；(2)计算梯度，取A(0)=I(单位矩阵)，置k=0，(3)构造搜索方向(4)沿方向进行一维搜索，求最优步长，使得到新迭代点(5)计算，进行收敛判断：

若，则令，停止迭代，输出最优解；否则，转下一步(6)；DFP变尺度法的计算框图，见图4-22。并令，转步骤(3)。(7)计算：构造新的变尺度矩阵和搜索方向：

(6)检查迭代次数，若k=n，则令

，并转入步骤(2)；若k<n，则转下步(7)；

图4-22DFP变尺度法的计算框图DFP变尺度法的优点变尺度矩阵A(K)，在开始的几步接近于I，因而类似于梯度法，具有计算量小，函数值下降快的优点；在最后的几步A(K)接近于[H（X(K)）]-1,因而类似于牛顿法收敛速度快的优点，但克服了其计算量大的缺点。2.BFGS变尺度法

计算实践表明：由于DFP变尺度法在计算变尺度矩阵的公式中，

其分母含有近似矩阵A(k)，使之计算中容易引起数值不稳定，甚至有可能得到奇异矩阵A(k)。

BFGS变尺度法与DFP变尺度法的迭代步骤相同，不同之点，只是校正矩阵的计算公式不一样。

BFGS变尺度法的变尺度矩阵迭代公式仍为

为了克服DFP变尺度法计算稳定性不够理想的缺点，Broydon

等人在DFP法的基础上提出了另一种变尺度法称为BFGS变尺度法。但其中的校正矩阵的计算公式为

上式中，所使用的基本